最近和几个网友展开了富有成效的关于“P vs NP”的讨论，我把讨论的主要内容整理成文与大家分享，希望对此议题感兴趣的网友能对其中所蕴含的认知方面的基本问题有所思考。

借此讨论我们进一步阐释我们NP理论工作的基本观点：我们不是反对P和NP术语，而是看到了在使用这些术语中所隐藏的人的认知错误，我们追本溯源，找到这些概念的真正内涵。我们不是想去发明一些新的概念、术语，只是通过对P和NP的真正意义的清理，解决这个领域中几十年来人为的世纪难题。我们相信只有在中国文化思想的眼光中才能透过层层迷雾，看清P vs NP的真实面目，使中国人能在世界理性思维中得到应有的地位。

＊＊＊＊＊＊

一，对话（2017/11/15）

柳渝：

@黄岱永 你说到“但也涉及到一些原则问题，如NP问题等以及对图灵机的深入思考，这一块还有一些基本的理论问题需要解决。”我们刚发了一篇与此相关的文章进一步讨论此问题（英语博文：解析“多项式时间可验证” － NP定义的歧义性），与大家分享。

黄岱永：

－形式语言不容许自然语言这样的“多义性”，这是科学的严格性和逻辑的一致性所要求的，即所谓的“客观性”。所以，若无意识将自然语言的“多义性”带入科学领域，就会出现“歧义性”，导致概念偷换，从而产生难以察觉的认知偏差，NP概念的困难原因之一正出于此。（摘自上面博文）

这个确实是，稍不注意，就陷入语义歧义困境，而常不自知。

－但是在计算复杂性理论中，NP却是一个严格的概念，不容许日常语言中那样的“多义性”。追本溯源，NP欲指“与P相对的NP”，即“P指易解的问题，而NP指难解的问题”，这样的“相对性（P versus NP）”决定了NP概念的定义。但在现有的理论框架下，NP流行定义之一是基于“多项式时间可验证”，指NP问题的猜测解可在多项式时间验证，由于“多项式时间可验证”是P的一个性质，故P问题就变成了NP问题！是有“P包含在NP”中，然而“此NP非彼NP也”，换句话说，由此在计算复杂性理论中就引入了“歧义性”。（摘自上面博文）

貌似有点直觉，P，NP问题可能还涉及到层次问题，在同一个层次里，经典的P，NP问题显然是原问题；不在同一个层次里呢？比如说三维世界的传统的推销员问题在四维世界里，如何存在或不存在吗？可解吗？如神经网络的升维与降维一般，P，NP的意义的演变和价值何在？anyway，这是一个有意义的问题吗？

Y君：

@柳渝 更重要的问题是，即使我们完全同意你的意见，有两种意义的NP，但是我们更关心复杂性的程度。那么，1，两种意义下的NP，那一种复杂性更高？2，这种分开理解了的NP，对我们解决P vs NP是否有积极促进？3，如果有，请解释。我以为，最重要的还是3。谢谢！

二，对话（2017/11/16）

@Y君你问：

更重要的问题是，即使我们完全同意你的意见，有两种意义的NP，但是我们更关心复杂性的程度。那么，

1，两种意义下的NP，那一种复杂性更高？

2，这种分开理解了的NP，对我们解决P vs NP是否有积极促进？

3，如果有，请解释。

我以为，最重要的还是3。

@Y君，我认为你的提问主要涉及二个问题：

一，是否有二个NP？

二，如果有二个NP，对我们解决P vs NP有什么影响？

我想先问：

现在有多少人认为可以有二个NP，这二个NP是什么？或认为只能有一个NP，这一个NP又是什么？

NP针对一类问题，本身就带有很强的抽象性，近来我意识到，若这样的讨论不密切结合具体实例，很容易把人绕晕。所以为直观理解起见，可以考虑大家熟知的、容易联系实际的二个问题：

1，最短路径问题：给定一系列城市和城市之间的距离，求解从一座城市s到另一座城市t的最短路径。

2，旅行商问题（TSP）：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

黄岱永：

在@柳渝 老师和@Y君 老师的深入讨论中，柳老师提出了下列看法：

－再来看作为理论问题的NP vs P，NP是怎么定义的？NP是“多项式时间可验证的”，此性质P也具有，因此”P问题是NP问题的特例，P包含在NP中”！由此可见， P vs NP变成了一个“悖论”（注）（NP与P不同，NP与P又相同）！而正是NP流行定义将P vs NP引进自我纠缠的“悖论”（注）怪圈的，。。。

我作了一个简单的梳理：

P是“（1）能判定在多项式时间内求解，（2）且在多项式时间内可验证。（既然已判定自然能求解）”.....定义：a ；记为{a}

NP是“（1）不能判定是否能在多项式时间内求解，（2）但能在多项式时间内验证所求解。”        ......定义：b ；记为{b}

把NP（1）中的不能判定分成两种情况讨论：能判定与不能判定。

因此NP也可记为  “（1-1）能判定在多项式时间内求解”，（2）（自然）也能在多项式时间内验证所求解。”转化为P.....定义：b-1；记为{b-1}

              “（1-2）不能判定在多项式时间内求解”，（2）但能在多项式时间内验证所求解。”回到NP....定义：b-2 ；记为{b-2}

              “（1-2-1）能判定在多项式时间内求解”，（2）也能在多项式时间内验证所求解。”回到P....定义：b-2-1；记为{b-2-1}

              “（1-2-2）不能判定在多项式时间内求解”，（2）但能在多项式时间内验证所求解。”回到NP....定义：b-2-2；记为{b-2-2}

                .....

              “ (1-i-1)能判定在多项式时间内求解”，（2）也能在多项式时间内验证所求解。”回到P....定义：b-i-1；记为{b-i-1}  (1＜i＜∞)

              “ （1-i-2）不能判定在多项式时间内求解”，（2）但能在多项式时间内验证所求解。”回到NP....定义：b-i-2；记为{b-i-2}(1＜i＜∞)

               .....

也就是说对于P,NP问题，按上述定义分解（定义编号）

（1）当{b-1}={a}时，P问题等于NP问题；

（2）当{b-2}={b} 有 {b-1，b-2}∈b ∪{b-2}={b}（集合自身产生了作为自身的循环子集，悖论出现）P、NP问题不可证。

柳渝：

@黄岱永 同意！这正是NP不一致的二个定义引起的“悖论”（注）：“不包含P的NP”与“包含P的NP”。

注：指矛盾的悖论关系，区别于自我否定意义的悖论。

三，对话（2017/11/17）

黄岱永：

P，NP问题的内涵实在太丰富了。

柳渝：

P，NP问题与AI的“可解释性”问题密切相关，意义重大。

黄岱永：

@柳渝 是的，而且联想到”可解释性问题”与证明，不但对AI（机器逻辑），对人而言也够烧脑了。

Y君：

@柳渝 ，这样说，对问题没有任何帮助，至少是没有实质帮助。问题是：我有一个问题，可以用非确定性的算法解，其难度为多项式时间，现在我问，这个问题可以用确定性的算法，其难度为多项式时间，来解吗？做更精确的定义，能够帮助解答这个问题吗？

柳渝：

请解释一下“什么是非确定性的算法”？

Y君：

根据流行的定义，就是说算法运行中有某些点，在其处，可以有多项选择，如果选择对了，算法得到结果，如果选错了，算法得不到结果。但是并没有办法知道选什么才对。因此有所谓的神喻之说。

柳渝：

指的是Nondeterministic Turing Machine吗？(https://en.wikipedia.org/wiki/Non-deterministic_Turing_machine)

Y君：

是的。

柳渝：

“非确定性的算法（注）”的实质就是“穷举法”，穷举法可用于求解问题规模不大的NP问题和P问题，比如：“最短路径问题”或“旅行商问题”，换句话说，“可以用非确定性的算法解，其难度为多项式时间”，这句话对所面对的问题的性质没有任何揭示。那么，你说的“这个问题”到底是一个什么样的问题？

Y君：

@柳渝 ，很同意“非确定性”最终可以归结到穷举或者反馈（注）。但是，回到我们的讨论焦点：一个问题如果可以用非确定性图灵机解决，问是否这个问题一定可以用确定性图灵机解决？我们说的，都是多项式长度图灵机。那么，对某个特定的问题，当然两种情况，可以或者不可以。的确有很多问题是可以的。但是P vs NP的焦点在：是否有这样一个问题，使得不可以？

因此，我们的问题再明确不过了，有没有？如果你能找出一个问题，的确没有，P vs NP就解决了。如果你能证明的确有，也解决了。

我说是否明确？是否对？

注：作为P性质的穷举法可以应用于非P的NP，但只能求得近以解。

柳渝：

首先，若对所要解决的问题的性质不清楚，对“多项式时间确定性的算法”的性质也不清楚，如何能回答“这个问题可以用确定性的算法，其难度为多项式时间，来解吗？”这样的问题？

“我们的问题再明确不过了”，不对，我们的问题目前一点也不明确。

一个人若对工具不清楚，对要完成的任务也不清楚，他如何能回答：是否能用此工具完成该任务？

黄岱永：

@纽约老熊 分为两个问题来看，也许更清楚些。（1）可“解释性方面”的语义问题，涉及到“P,NP问题”流行的数学定义的问题；（2）从算法角度来看：“在多项式时间内能否找到有效算法”是能否在多项式时间内判定“在多项式时间内能找到有效算法”的问题。换成您上述的说法，多项式时间内产生的“神谕”！相对的来看，这里实际上产生了两个算法层次。

Y君：

仅通过定义就能解决极大的难题，那就太好了。不过，我的确不清楚@柳渝 的看法，和她心中的难点。

黄岱永：

仅通过定义当然不行。

柳渝：

@黄岱永对于流行的Nondeterministic Turing Machine，其本质是Deterministic Turing Machine：

“Every nondeterministic Turing machine has an equivalent deterministic Turing machine”－Sipser书中Theorem 3.16

也就是说，此Nondeterministic Turing Machine已经不再是“神谕机”了。

@纽约老熊 这并不仅仅是我自己心中的难点，这是P vs NP的难点。

Y君：

我们换一种说法吧。假设我有一个程序，在中间有一些点，运行到这些点时，需要停下来问我怎么办，我有一些选择，如果选择对了，程序会得到正确结果。现在我问，是否存在另外一个程序，使得不需要我的选择，也能得到正确结果？

你怎么回答这个问题。这个问题明确吗？

我认为这和NP是等价的。

柳渝：

@纽约老熊 你是说：有些程序不需要你的干预就能得到正确结果，而有些程序不行？

程序是解决问题的，那么，为什么不问这些不需要你干预的程序具有什么性质？其针对的问题又具有什么性质？

Y君：

@柳渝 ，你在转移问题。我仍然不清楚你的思想是什么。我的问题已经非常清楚了。是否我们可以停下来，听听@黄岱永 的意见？

柳渝：

好的。从这二天我们关于Nondeterministic Turing Machine与NP的对话中，多少可以看出“什么是NP？”并不是如想像的那么简单。

Y君：

但是也没有那么困扰。你的看法我很同意，那就是，至少有些NP问题，如求Hamilton回路的问题，具备这样的特点，在求解过程中，不能通过某种简单的函数确定是否正确，必须要获得反馈后（或者神谕）才能决定。而这种特性，事实上是这些问题复杂的根源。这个观点很对。但是仍然还是那个NP问题，是否有需要神谕的问题，找不到不用神谕就能解决的方法？这是重大问题。这个重大问题，即使你对NP的定义再怎么挖，还是在那里。

再简短一下，用神谕能解决的问题，是否不用神谕也能解决？这就是P vs NP。

如果谁能找到这样一个问题，的确可以用神谕解出来，但是肯定不用神谕就解不了，那么P vs NP就获解了。我们要考虑的是，怎样构造这样的一个问题。对吧？

我想请问@柳渝 ，你认为，你的思考是否有助于构造前述的问题？如果是，前详释。

黄岱永：

“我们换一种说法吧。假设我有一个程序，在中间有一些点，运行到这些点时，需要停下来问我怎么办，我有一些选择，如果选择对了，程序会得到正确结果。现在我问，是否存在另外一个程序，使得不需要我的选择，也能得到正确结果？”

我觉得熊老师的上述问题不是相当明确（我理解起好像有点歧义）。但大概来说的话，就歧义分别讨论的话。在Non-deterministic Turing  machine框架下，这涉及到的算法应该牵涉两个层次的问题，等同于NP问题和停机问题！

说明如下：

设在节点M可运行n个程序P，记为{P(i)∣P∈M,i=1.2,...n},当运行到A时 ，选择一个P(i）

（1）：P(i）是我们需要的算法（程序），运行停止；

（2）：P(i）不是我们需要的程序，程序继续运行到N....;那么在M处是否有运行（或不运行仅猜测，歧义之处）存在P(j)（j=1,2，...,n j≠i） ，可能就是我们需要的算法（程序）？

我们不妨构造树T，M是一个分支点。这里熊老师的“不需要我的选择”有点歧义，是指（a）：仅猜测判定P(j)中是否有需要的算法（并不进行实际的运算）；（b）：在节点M继续进行不需要我们选择的实际的运算，那么， 显然，将有在节点M的下个已选择节点N继续进行选择性的运算和同时在M进行非人为的选择性计算，这将产生更多的分叉路径。

对于（a）我们可证等效于NP；（略）

对于（b）问题有点复杂。实际上，这里需要有两个层次的算法，第一层次 A(i）是人为的选择性算法；A(j）是非人为的机器选择算法（或随机或某 种规则下），它们沿不同的分叉路径各自运行。显然对于每个人为选择的 下个节点都可能再一次产生出P'(i)和P'(j）（j≠i）......循环。

第二层是否存在一个判定程序（算法），来有效识别我们需要的算法P(i）并停止程序？我猜测这是一个停机问题。

Y君：

@黄岱永 ，我的那个说法，其实仅是帮助理解的通俗说法，如果要精确，还是应该回到教科书上。

黄岱永：

@Y君 确实，数学问题仅语言描述有时有点难。

Y君：

所谓的Oracle神谕，其实不神秘，就是我通俗解释的那样，当然要精确，回到教科书吧。

问题是，@柳渝 她提出对教科书不同的意见，我想搞清楚她为什么要这样想，有什么好的前景。

黄岱永：

柳老师专门研究这个的，有些新想法也自然。她科学网的博客上，有些比较系统的东西。很多问题群里说不太清楚。

Y君：

她的一个想法，我很赞同，就是前面讲到的，Oracle神谕其实就是对穷举的一个精确数学定义。这个来源是清楚的。但是究竟怎么帮助我们，就不清楚了。

@黄岱永 恰好相反，在群里问，她才把这个问题说清楚了，看她的文章，我没有获得这个问题的清晰看法。因此，继续问，是好的。我想她恐怕同意。没有我的追问，有的东西清晰不起来。希望她同意。

柳渝：

@Y君 @黄岱永 当然同意，很高兴大家能一起讨论！但是这不是一个简单的问题，需要时间。这个问题探讨的意义不仅仅是在最后的答案中，更重要的意义是在此过程中。你们先聊。

黄岱永：

@柳渝 特别是您上面强调的Nondeterministic Turing Machine，这个在神经网络的基础构建里也有很强的指导性，继续学习中……

Y君：

@黄岱永 @柳渝 ，谢谢。我认为，现在的技术方式，使得我们可以做很多以前只能在一个房顶下才能做的事情。我们远在天涯，但是可以集合在一起讨论很有趣的学术问题。非常好。没有讨论，思想无法清晰也无法成型。以前，只有在同一教研室，同一课题组，才有机会讨论。但是那就太狭隘了。因此，谢谢大家，我很珍惜。

黄岱永：

@柳渝 @Y君 确实，在讨论中受益匪浅，天涯一方，但信息瞬间即至，”协同计算”魅力无穷。

四，对话（2017/11/18）

柳渝：

@Y君 你昨天说我转移了话题，确实我把话题从“P vs NP”转移到了“什么是NP？”。

我为什么要这样转移？因为当前“P vs NP”是问：既然NP包含P，那么NP是否等于P？其中“包含P的NP”是由NDTM来定义的，而现有的NDTM的本质是TM，换句话说，现有的NP实际上就是P，即NP＝P。

我们说这种情况，就是NP现有的概念中”不确定性消失了“，或现有的“P vs NP”是矛盾的悖论关系。

然而，人们都知道真正的NP与P是不同的，比如“旅行商问题”与“最短路径问题”就有本质的不同。所以，算法理论的首要任务是要找回那个真正的NP，而不是在现有的理论框架中问：既然NP包含P，那么NP是否等于P？

Y君：

@柳渝 ，谢谢解释。那么我是否可以这样理解你的想法：现有的NP定义，其实把真正应该探究的掩盖了。对吗？好，我们且同意此点。

那么，进一步，你也说其实的确有不同于P的类，我愿意听你对这个类的定义。

再进一步，提问，根据你的定义，你是否可以证明这个类和P不同？

柳渝：

@Y君 对，这个NP就是“不确定性问题（Nondeterministic Problem）”，与P（Deterministic Problem）相对，由于“不确定性”导致“不可判定”（如旅行商问题，丢番图问题等等），表现为“指数时间复杂度”，在可计算性理论中被称为“判定问题”，已经被图灵证明为“不可判定（不存在算法精确求解）”。换句话说，NP／＝P！

Y君：

@柳渝 ，你这样做，对原来的问题，基本上没有帮助嘛。原来的问题，才是大家关心的。那么，你这样修改定义，起什么作用呢？

柳渝：

@Y君 我没有修改原问题，只不过还原问题。“NP／＝P”的意义就是，所有解决NP问题的算法都是最优近似方法，这其实就是现实。

Y君：

你是说，如旅行商等问题，肯定没有多项式长度的解，而且你可以证明？

黄岱永：

显然不是这个意思。如果能证明，那就不存在这个问题了，直接得出结论就是了。

柳渝：

@Y君 “多项式长度的解”是什么意思？

@黄岱永（号淼鑫）对！“不可判定”就是“不可证明”，只能通过人的认知得出“旅行商问题只能近似求解”。

Y君：

@柳渝 ，对不起，我应该尽量精确。多项式长度，我是说图灵机用的时间是多项式长度。但是，你没有解决任何问题。

不得不说，我越来越糊涂了。你做了这么多讨论，你究竟达成了什么？

柳渝：

@Y君 指出现有的NP理论中的NP概念存在着严重的认知偏差，导致存在着“NP＝P”的企望，而对于真正具有“不确定性”本质的NP来说，NP／＝P。

@Y君，我知道，这样的工作太“离经叛道”了，还有待进一步深入，我们一直在研究中。今天是你问到了，我才这样说的。我们先暂时放到一边，以后有机会再慢慢说。

Y君：

@柳渝 ，离经叛道是好事。但是问题在那里，你是否可以帮助解决。这才是我关心的。

你说的认知偏差我们完全可以放开。我问：你说，“对真正具有“不确定性”本质的NP来说，NP／＝P”，你是否有这样的NP？如果有，请证明给我们看为什么它不是P。