|||
我与Y君围绕着“P vs NP”继续讨论,逐渐将讨论的焦点集中在由NDTM定义的NP上,Y君提出一个“密码锁问题”,大家通过判断“密码锁”是P还是NP来考察NP的定义。
继续分享我们的部分对话:
一,对话(2017/11/22)
Y君:
看了你的最新博文。感到你是在这个地方有问题:
你说:追本溯源,NP欲指“与P相对的NP”,即“P指易解的问题,而NP指难解的问题”,这样的“相对性(P versus NP)”决定了NP概念的定义。
我认为这里有重大理解的偏差。固然,NP是难解的问题。但是这个难解需要严格证明。很多问题,看起来难解,但是未必真的难解,很可能在若干时间后,就成为不难解的了。
P vs NP困难,不在于理解,而在于,我给你一个问题,的确看起来非常难解,是NP,但是我们不能确定它是否真是NP,它很可能是P。
这样的看起来是NP但是P的问题很多,看起来难,到最后,并不难。
那么,是否可以有一个问题,看起来难,而且的确难?你可以证明对这个问题没有容易的解。如果你找到了这个问题,而且你提供了严格的数学证明。但是必须要有数学证明。否则无论你怎样解释,都没有用。
柳渝:
“是否可以有一个问题,看起来难,而且的确难?你可以证明对这个问题没有容易的解。如果你找到了这个问题,而且你提供了严格的数学证明”,如我所说,图灵他们已经证明了。
“P vs NP”实际上隐含着非常纠缠的层次:
1,是否存在一个“能行的”形式化方法(P算法)判断任何一个具体问题是NP问题还是P问题?
这实际上就是“判定问题(Entscheidungsproblem)”,图灵已经对此给出了否定性的回答:“判定问题”是“不可判定的”,其真正意义是说:不存在能判断任何一个问题是P问题还是NP问题的形式化方法。
图灵是通过设计一个特殊问题,然后无法构造出P算法,来否定性回答“判定问题”的。
2,是否存在一个具体问题没有多项式时间复杂度算法(P算法)求解?
(1)图灵设计的那个特殊问题;
(2)我跟你说起的“丢番图问题”,就是一个看起来难而且的确难,但不存在P算法的问题(丢番图问题的解决)。
二,对话(2017/11/26)
柳渝:
我先说明一点,我们的NP理论工作在讨论NP时首先把NP与P分开,这只是认知NP的第一步,并不是就肯定NP/=P,完全有可能待进一步认知后,发现NP=P。但是若一开始就用P的属性(多项式时间可验证)来定义NP,NP就与P混在一起了,根本谈不上进一步认知NP,也就是说,在认知的开始就已经肯定了NP与P没有区别(NP=P)!
Y君:
你说:“我先说明一点,我们的NP理论工作在讨论NP时首先把NP与P分开,并不是就肯定NP/=P,这只是认知NP的第一步”,这个完全没有问题。我们没有必要采用现在的通常定义,即P时间可以验证,而采用这个定义:用P时间,在NDTM上找到解。
这个定义是当初Cook的定义。但是,问题仍然存在,并不因为我们改变定义而消失。问题是:是否存在这样一个问题W,我们知道可以用P时间,NDTM可以找到解,但是我们能证明,不能用P时间,TM找到解。
我们必须要提出W问题,而且严格证明不能用P时间,TM能找到解。我关心:1,你是否明确了这个问题W?2,你是否有严格证明,而不是说明?
这个问题延续了几十年,学界都不能解决,我认为,不是那种可以靠重新解释就能解决的问题。必须要有新工具,新思想。
我看了你的文字,感到你的一个基本想法很对,那就是在这个领域中去找W:问题的答案需要反馈。但是这仅是思路,而不是直接的答案。答案还需要严格证明。
三,对话(2017/11/27)
柳渝:
你说“用P时间,在NDTM上找到解”,但NDTM根本就是一笔糊涂账!
读读我们讲这个NDTM的新博文:英语博文:NDTM的两个来源初析-NDTM的歧义性
-作为一种思想实验,不妨说“NP是NDTM(神喻机)在多项式时间内可以判定解的存在的问题”,但这只是借此表达“NP是TM在多项式时间内不可以判定解的存在的问题”,而不是“NP是NDTM(TM)在多项式时间内可以判定解的存在的问题”!换句话说,NP定义中的NDTM出现了歧义性。
你说“我们必须要提出W问题,而且严格证明不能用P时间,TM能找到解。”这个问题就是“丢番图问题”,可是计算机工作者从来没有深入研究此问题,而把它留给了数学家。
“这个问题延续了几十年,这个学界都不能解决,我认为,不是那种可以靠重新解释就能解决的问题。必须要有新工具,新思想。”这个“新工具,新思想”,就是彻底清算现有理论的混乱,清理好了,问题自然就解决了,。。。
Y君:
我不认为会那么简单。如果真是仅靠梳理思路,就能解决这样的问题,那才是超过神谕的事情。不过,我们继续仔细谈。
或者这样讲,如果按照你的思路做了,大家也都认同你了,是否可以对按照现在的流行定义理解的P vs NP有帮助?即,帮助找到一个问题W,它可以在P之内验证但是确定不能在P之内解。这才是科学社区关心的。你的梳理应该有助于此才好。
柳渝:
这个问题W就是“丢番图问题”,但需要结合图灵的“判定问题”的工作。
你看看Stackexchange 上关于这个问题的讨论(关于“丢番图方程的两难问题”的英语讨论(1)),就可以感觉出问题有多么严重。一般人们(包括你和Stackexchange 上提问题的人)都认为丢番图问题是NP,且与3-sat等价,但是按现有理论看,丢番图问题与NP一点关系都没有!
Y君:
我以为自圆其说的理论应该是有严格定义的,然后再在其基础上,仔细讨论。现在你批评了很多,但是你应该拿出你的严格定义来。我目前还没有看到,对吗?
然后我们看你的定义和现在流行的定义的差别和联系。现在你的这些表述,在我看来很糊涂和含混。我想,对我如此,对其他人恐怕更甚。
柳渝:
我们的理论,或者说图灵那些前辈的理论(只是他那个年代还没提出NP这个术语)就是:NP就是“不可判定问题”,即NP是TM多项式时间不可判定,也即不可(精确)求解而只能近似求解的问题。
Y君:
我不知道是否说清楚了。你的定义没有问题。但是1,你的证明要随着你的定义展开。我没有看到。2,你的定义对大家关心的问题是否有帮助?你说了很多,但是我认为没有帮助。如果你认为把几十年的努力全部否定叫做帮助,那我也不能说什么了。现在的这个P vs NP是有价值的问题。你不能否定。
是否可以这样表述:一个问题W,我有一个神谕机,可以在多项式时间内,解开W,是否一定有一个TM,可以在多项式时间内,也能解开W。
柳渝:
你以后会慢慢明白我,我们並没有否定P vs NP的意义,也没有否定计算复杂性领域中的实际成果,但我们希望这些工作建立在正确的理论基础上,並为人机伦理关系理论奠定基础。
Y君:
现在我们来看这样的一个问题:我从N维布尔向量开始,前行K步,每一步都是将该步的向量变成下一步的向量,但是每一步都有两种选择。只有每一步都对了,我才能得到正确的答案。神谕机就是非常好的描述每一步都对了这个事情。那么我问,当我有一个神谕机时,我是否可以找到一个不用神谕机,而且可以在N的多项式时间内也找到正确答案?
这样一个问题,有没有错?是否清晰?有没有其他问题使得含混和模糊?都是把该步的向量变成下一步的向量。
四,对话(2017/11/28)
柳渝:
你说的是一般对NDTM的定义,所谓的“多选择”,这又是一个让人混淆的概念。
Y君:
请就问题论之。我说的那个W,是否定义清晰?
柳渝:
实际上无法是P问题还是NP问题在求解过程中都面临着“多选择”,比如求解“从s到t二点之间最短路径”的dijstra算法,在未到达t结点时,计算必须保留不同的选择。
你的那个W定义清楚,但是错误的。就像流行的多项式可验证定义,很清楚,但是错误的。
Y君:
请讲为什么是错的。
柳渝:
先分析你的表述1:一个问题W,我有一个神谕机,可以在多项式时间内,解开W,是否一定有一个TM,可以在多项式时间内,也能解开W。
记:
A:一个问题W,我有一个神谕机,可以在多项式时间内,解开W。
B:有一个TM,可以在多项式时间内,也能解开W。
现在你问:if A, then B?
实际上,你是问:能否从A推导出B,即(A->B)?
分析:
1,A中的神谕机是一个“黑箱”,此“黑箱”没有给出关于问题w是P还是NP的任何信息,换句话说,“黑箱”不能在A与B之间建立起任何联系,故A->B作为命题不成立。
2,A中的神谕机是一个假设,更不能作为推理的前提使用:A=true,问B=true?
所以从逻辑推理的角度,你提出的表述1没有成立的理由。
Y君:
对的,我认为这个表述是对的:一个问题W,我有一个神谕机,可以在多项式时间内,解开W,是否一定有一个TM,可以在多项式时间内,也能解开W?
但是你这句话我认为不对:实际上,你是问:能否从A推导出B,即(A->B)?
为什么呢?因为我的问题并不是:如A成立,是否一定B成立?而是,如果对W有一个比较困难的解,是否有容易的解?这个区别很明确。
另外,我想明确表示,这个问题W,其实就是你多次说过的那类问题,即需要反馈结果的问题。因此,神谕机的存在,仅说明这种需要反馈。其实,所谓的神谕,其实就是穷举的结果,即如果我做过了穷举,我自然有了神谕。
这样有问题吗?如果没有,那么神谕就不是黑箱,而是说明一种确定的状况,即我可以穷举求解。
因此,表述也可以这样:一个问题W,我在预先穷举之后,可以在多项式时间内,解开W,是否一定有一个TM(即不需要预先穷举),可以在多项式时间内,也能解开W?
其实这个表述也不够好,我来再改进一下:一个问题W,我在预先穷举之后,可以在多项式时间内,解开W,进而我问,对这样的问题,我是否可以改进,使得不需要预先穷举,就可以在多项式时间内,也能解开W?
那么,如果说,对任何问题一定可以改进,就是NP=P。如果说,有某个问题,一定做不到这种改进,就是NP/=P。
我认为,虽然讲法不同,但是现行的NP定义,就是这样的。在我看来,并没有不合理处。
五,对话(2017/11/29)
Y君:
我们再说一个更简单的问题W:假设我有一个密码锁,上面有N个键,每个键可选0或1,如果我有密码,我解开这个锁需要N步,这个密码就是神谕。所以,有了神谕,打开锁的复杂度是多项式。我问,如果没有密码,我是否还是可以多项式时间内打开这把锁?
这样的问题,是否就是P vs NP?
柳渝:
我在考虑你的密码锁。
知道“有N个键且每个键可选0或1的密码锁”就是P,因为可穷举搜索,你能有多长的位数,图灵机就会有多大的空间搜索能力,这就是最简单的在一维数组中搜索某种元素的最简单的P算法!
Y君:
你说,““穷举法”不过是一个一维数组简单的搜索而己,是P算法,与NP的本质没有半点关系“。请解释,我不懂你说的。请参照我上面的问题。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-2 02:32
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社