Stack Exchange是全球最大的问答网站之一（注），其中的“Computer Science”版面有很多关于算法理论诸问题的讨论，我们加入了其中一个质疑NP流行定义问题的讨论，摘出部分对话与大家分享，希望有兴趣的网友也能参加！这是网址： http://cs.stackexchange.com/questions/1887/why-isnt-this-undecidable-problem-in-np ，和 讨论的完整版： stackExchange1.pdf 此外，我们准备将科学网博客中关于NP的讨论介绍给国际同行，最近也有友人询问博文的英语版，推荐给在美国读计算机理论课程遇到困难的孩子看。所以，我们希望将这里的博文双语化，若有网友能协助一起工作，将感谢不尽！ ＊＊＊＊＊＊ BlueRaja - Danny Pflughoeft提问 ：Why isn't this undecidable problem in NP?（为什么这个不可判定问题不在NP类里？） Clearly there aren't any undecidable problems in NP. However, according to Wikipedia: NP is the set of all decision problems for which the instances where the answer is yes have verifiable in polynomial time by a deterministic Turing machine. A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time. Now consider the following problem: Given a Diophantine equation, does it have any integer solutions? Given a solution, it's easy to verify in polynomial time that it really is a solution: just plug the numbers into the equation. Thus, the problem is in NP. However, solving this problem is famously known to be undecidable! (Similarly, it seems the halting problem should be in NP, since the yes-solution of this program halts at the N-th step can be verified in N steps.) Obviously there's something wrong with my understanding, but what is it? Yu Li（柳渝） ：We think that the dilemma you raised about Diophantine equation is very significant, because it reveals something abnormal in the current definition of NP : - A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time. Concerning the definition of NP, it can be traced to the 60’s, where a great number of applicable and significant problems were discovered for which no polynomial algorithms could be found to solve them, in order to recognize these problems from those problems solvable in Polynomial time (P), the concept of NP was put out. However, the current definition of NP as verifiable in polynomial time confuses NP with P, because a problem in P is also verifiable in polynomial time. In another word, such definition leads to the loss of the essence of NP, « nondeterminisme ». Consequently, it causes serious ambiguities in understanding NP, for example, your dilemma : by nature the problem of Diophantine equation is undecidable; but by the definition of NP, it is decidable, … In our opinion, the difficulty in solving « P versus NP » lies firstly at cognition level, so if we hope to get an insight into « P versus NP », we need at first to question : What is NP? David Richerby ：This seems to be an opinion piece about the definition of NP, not an answer to the question. The definition of NP is just fine. It doesn't confuse P with NP; rather, it acknowledges that P is a subset of NP. To me, it would be very unnatural if P were not a subset of NP. NP is a class of problems that can be solved within certain resource bounds. That necessarily includes a whole bunch of easy problems (P) that can be solved without coming close to the limit of the resources available. Yu Li（柳渝） ：P and NP have the common property of « certificate verifiable in polynomial time » , but this property is not the essence of NP. If this property is used to define NP, then P is a subset of NP, and NP has P as its subset (decidable) and itself (undecidable). Therefore, one would wonder whether NP is decidable or undecidable? Just like the above dilemma : whether is Diophantine equation undecidable or decidable? So my answer is to suggest to investigate this dilemma from the view of the definition of NP: verifiable, undecidable is unverifiable！ 注： －维基对Stack Exchange的简介： Stack Exchange是一系列问答网站，每一个网站包含不同领域的问题。这些网站参考Stack Overflow，一个关于程序设计的问答网站，也是Stack Exchange的第一个成员。如同Stack Overflow，这些网站使用声望奖励系统，用户对问题和答案进行投票，并影响用户声望。声望系统使这些网站可以自我控制。 －介绍Stack Exchange缘起的文章：全球最大的问答网站之一，Stack Exchange如何养成（ http://www.huxiu.com/article/112013/1.html ） －分析Stack Exchange成功经验的文章：StackExchange和它的游戏规则（ http://andnot.farbox.com/post/ke-yan-bi-ji/stackexchangehe-ta-de-you-xi-gui-ze ）
标签: Stack
