||
柳渝:是的,我期待一个与常识认知一致的NP定义,但并不排除直觉:
“除了明显的直觉和必要的推理外,人们没有其他方法可以了解真相。” -笛卡尔
您解释NP的形式化定义:
- 定义1: NP是不确定性图灵机多项式时间可判定的问题。
问题是这里的“不确定性图灵机”在现实中不存在,如您所解释,“这等于是赋予了机器无限的并行能力,使它可以并行测试所有解决方案的能力”;在Cook定理(1971年论文)中则指“神喻机”。
实际上,NP的非形式定义(NP是其解可以容易验证的问题)也可以进一步形式化:
- 定义2: NP是图灵机多项式时间可验证(解)的问题。
然而,NP的这二个定义似乎所指不同:定义1将NP与P“分开”,但是基于现实中不存在的(想象的)“不确定性图灵机”;定义2虽然基于现实的“图灵机”,但又将NP与P混淆了。
于常识认知,不同定义之间的区别在于抽象的程度和表达的方式不同,应该具有一致性,即所指应该是同一事物。
所以,我的问题是:
1,NP的定义是否存在着问题?
2,NP的定义是否与人们认知P vs NP问题困难有关(如您视频的留言所说,几乎所有学习计算复杂性理论的人理解P vs NP都有困难)?
Passe-Science:您说“定义1将NP与P’分开’,但是基于’imaginaire (想象的)’的不确定性图灵机;定义2虽然基于’现实’的图灵机,但又将NP与P混淆了。”
对于“ imaginaire (想象)”一词有点值得怀疑,因为所有数学都是抽象模型,甚至数字1,确定性图灵机和不确定性图灵机也都是抽象模型。
至于说“算法的复杂性”,从定义上讲是一种无限的行为,因此也是一个抽象模型等等。但是,仅是为了说明,我不会在意义或缺乏意义,某些数学模型是真实或不是真实的,做太多论述。
简单回应您的段落,有几件事存在混淆:
1)“判定问题”整体而言,例如“找到一个过程来回答任何图任意图是否为3色”,处于无穷实例集,在这个层次上我们可以说算法的复杂性。
2)在实例层次上,即给定一个图, “此图G是3色的吗?”
3)针对给定的实例和一个候选解,问:“此图的3-着色是有效的吗?” 如果要在这种情况下谈论复杂性,我们将对所有可能的图实例+候选着色进行推理。
而且,您采用NP的“定义2”,它与P类的定义完全不同,因为它们不在同一层次。
P是可以在多项式时间内“解决”的判定问题类(即我们仅向算法提供问题实例,在此为图G,算法必须在多项式时间内回答这个问题是3色的)。
NP是可以在多项式时间内“验证”的判定问题类。 (但尚未解决,也就是说,我们为算法提供了问题的实例,例如给定的图和着色方案,算法的工作只是判定3-着色的有效性,而不是对“3-着色能力”的判断)。
因此,对于P类和NP类,在两种情况下确实存在多项式复杂度的概念,但并不是针对同一件事物。
您说“定义1将NP与P分开”。定义1和2在数学上是等价的,因此,如果定义似乎“分隔”某些东西(或您对定义1的结论),则定义2会做相同的事情。
定义1是表达在不确定性图灵机上多项式时间的“可求解性”,定义2是表达在确定性图灵机上以多项式时间的“可验证性”。而且,正如我在上文中所述,在二种情况的“多项式”不是做相同的事情。
更清楚吗?
参考文献:
对话原文见【1】https://www.youtube.com/watch?v=8TrIW-4kfRg
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 09:19
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社