不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

与法国朋友漫谈P vs NP(7)

已有 1646 次阅读 2020-5-28 14:13 |个人分类:不确定性问题和算法讨论|系统分类:科普集锦

柳渝:P vs NP问题问“NP=P,实际上是问NP-complete=P,所以P vs NP问题指向NP-complete


由于人们未能确定NP-complete的特有属性,所以把焦点从NP-complete转移到NPNP被定义为:

- 定义1: NP是不确定性图灵机多项式时间可判定的问题。

- 定义2: NP是图灵机多项式时间可验证的问题。


形式上看,NP包含PNP-complete;但是若从内容上看,却并非如此。因为NP可验证,可判定的属性也由P共享,而NP-complete是新事物,其特定属性未能形式化表达,所以可验证,可判定不能成为NP-complete的特定属性,换句话说,NP-complete的特定属性从NP中消失了。


NP导致的结果是,让NP-completeNP中成为类似黑箱子的东西,这样一来,欲在NP中寻找NP-complete就是一项“不可能的任务”。就像我要在一栋楼里找老王,你却告诉我老王住在老郭隔壁,而我根本不认知老郭,当然就不可能找到老王!


在这种情况下,我们是否应该反思:在NP中找NP-completeNP=P?),会不会是盲人摸象,。。。


Passe-science我逐条地回答:

- P vs NP问题问“NP=P,实际上是问NP-complete=P,所以P vs NP问题指向NP-complete


从数学上讲,这二个问题是一回事:PNP不同,当且仅当PNP-complete不同。


- 因为NP-complete是新事物,其特定属性未能形式化表达。


如果这些特定属性被形式化表达出来了,则能够普遍表达NP中的任何其他问题。一个问题要能成为NP-complete问题,NP中的任何问题必须能够在多项式时间内归约为此问题。这是一个很强的特定属性,形式化准确地定义了所讨论的集合。


我补充说,在现阶段我们永远不能提供可以严格说明的属性,因为我们还没有解决了P vs NP这个猜想。如果事实是P = NP,那么P = NP = NP-complete,因此将永远没有任何标准可以决定它们之间的关系,在这种情况下,NP-complete将不存在特定属性。


但是就目前而言,也可以相反看,我在上文中向您描述的特定属性,您也无法向我证明它不是NP-complete的特定属性。如果您可以的话,您就解决了猜想。


参考文献:

对话原文见【1】https://www.youtube.com/watch?v=8TrIW-4kfRg



http://blog.sciencenet.cn/blog-2322490-1235337.html

上一篇:与法国朋友漫谈P vs NP(6)
下一篇:数字“三” - 中西文化阐释(1)

1 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-12-1 00:37

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部