||
与法国朋友漫谈P vs NP缘起于Youtube上一个很受欢迎的法语普及P vs NP的视频【1】,所以我直接和此视频制作者Passe-Science对话。我将对话译成中文分享:
柳渝:我提一个问题:
您举了3个NP问题的例子:3-图染色问题,背包问题,合取范式可满足问题(SAT问题)。
于常识认知中,我们知道NP与P是不同的,因为与P相反,NP现在只有指数时间的精确求解的穷举法,和多项式时间的近似算法。然而,NP被定义成“其解可以容易验证的问题”,但是,P也是其解可以容易验证的问题。
那么,这个“其解可以容易验证”的性质如何能捕捉到在直觉上与P不同的NP的本质?
Passe-Science : 我不肯定完全理解了您的问题,但我认为我基本明白了。
大致说,您是想知道我们如何能够“严格”定义NP类和P类。 (不依靠直觉,直觉形式上不严谨)
因此,当我们进入严格的框架时,我们这里仅研究所谓的“判定”问题,即以答案为“是或否”的形式表述。
例如,“我可以用3种颜色为这张图着色吗?” (而不是询问如何用算法进行操作)。
在所有判定问题中,我们定义2个类:
P类:诸如通用图灵机(这是计算机的严格形式化)上的可编码算法之类的问题,以多项式复杂度回答该问题。
NP类:对于不确定性多项式,询问是否存在多项式时间的不确定性图灵机算法。
第二个严格定义有些微妙,粗略地讲,这等于是赋予了机器无限的并行能力,使它可以并行测试所有解决方案的能力。因此,我们有了2个严格的,不同的定义来定义这两个类。但可能这二个定义尽管不同,却定义了一个对象(如果P = NP)。
然后是一个NP完全类,这是一个令人惊讶的事实:我们可以证明NP类中存在特定问题,可以在多项式时间内归约任何其他NP问题。 NP-完全类不是空的,在开始时这一点是不明显的,是Cook-Levin定理给出了NP-完全问题的第一个例子。
然后,一旦有了这个例子,此后就很容易证明其他问题是NP完全的,只要证明我们可以将它们归约为该特定例子,我们已经归约了一些例子。(这就是我在视频中所做的)。
如果我没有回答您的问题,请随时澄清。
参考文献:
对话原文见【1】https://www.youtube.com/watch?v=8TrIW-4kfRg
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 08:53
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社