我与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。

柳渝：

你以后会慢慢明白我，我们並没有否定Ｐ 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的本质没有半点关系“。请解释，我不懂你说的。请参照我上面的问题。