||
柳渝:P vs NP问题问“NP=P?”,实际上是问“NP-complete=P?”,所以P vs NP问题指向NP-complete。
由于人们未能确定NP-complete的特有属性,所以把焦点从NP-complete转移到NP,NP被定义为:
- 定义1: NP是不确定性图灵机多项式时间可判定的问题。
- 定义2: NP是图灵机多项式时间可验证的问题。
从“形式”上看,NP包含P和NP-complete;但是若从“内容”上看,却并非如此。因为NP的“可验证,可判定”的属性也由P共享,而NP-complete是新事物,其特定属性未能形式化表达,所以“可验证,可判定”不能成为NP-complete的特定属性,换句话说,NP-complete的特定属性从NP中消失了。
NP导致的结果是,让NP-complete在NP中成为类似“黑箱子”的东西,这样一来,欲在NP中寻找NP-complete就是一项“不可能的任务”。就像我要在一栋楼里找老王,你却告诉我老王住在老郭隔壁,而我根本不认知老郭,当然就不可能找到老王!
在这种情况下,我们是否应该反思:在NP中找NP-complete(NP=P?),会不会是“盲人摸象”,。。。
Passe-science:我逐条地回答:
- P vs NP问题问“NP=P?”,实际上是问“NP-complete=P?”,所以P vs NP问题指向NP-complete。
从数学上讲,这二个问题是一回事:P与NP不同,当且仅当P与NP-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
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 14:32
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社