||
柳渝:我用“ imaginaire (想象)”一词指如您所说“有些微妙”的NDTM,确实容易产生歧义。实际上,大致存在三种对NDTM的解释:
- NDTM具有无限的并行能力;
- NDTM可用TM在指数时间模拟;
- Oracle(Cook原始关于NDTM的定义)。
我们暂时把基于“有些微妙”的NDTM的“定义1”放在旁边,再考察一下基于TM的“定义2”。
在人们的常识认知中,NP与P是不同的。但是当人们希望对NP做深入的了解时,“定义2”告诉人们:NP是图灵机多项式时间可验证解的问题类,由于P也是其解可以容易验证的问题类,所以NP包括P。注意,NP与P的关系从“相对关系”变成了“包含关系”。
所以,我问:这样的NP定义是否存在着问题?我现在试用一个比喻来说明我的质疑:
柳渝认识“牛”,但是没见过“马”,一天她见到一群牛和一群“马”在一起吃草,于是问您:
柳渝(指着马)问:这是什么?
Passe-Science:这是“马”。
柳渝:什么是“马”?
Passe-Science:“马”是有颜色的动物。
现在Passe-Science问柳渝:您知道什么是“马”了吗?
柳渝只能回答:我不知道,因为牛也是有颜色的动物。
Passe-Science:我明白了混淆所在。根据定义,P包含在NP中是完全容许的。从结构上讲,无论哪种定义(定义1或定义2),P总是包含在NP中的。
如果问题是P,那么很明显,它可以在不确定性图灵机(定义1,因此也是NP)上多项式时间内求解,也可以在多项式时间内验证(定义2,因此也是NP)。
从来没有一个(P与NP)“对立”关系的定义,没有任何尝试能将NP定义为与P“不相交”的集,它们一直是包含关系,我们正在尝试的是研究这种包含关系是严格的,还是实际上相等的,NP中是否存在不在P中的元素。
关于“不相交”,应该是对“NP完全类”而言的,但显然我们不确定(因为是整个问题)NP中的“NP完全问题”在某种程度上是“最难”或“至少一样难”。如果我们有不同NP的P,那么P和NP-Complete之间是分离的。
参考文献:
对话原文见【1】https://www.youtube.com/watch?v=8TrIW-4kfRg
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 09:28
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社