纠正对NP 问题的错误理解（2）

-- 对网友评论的回复

郝克刚 2011-12-26

我2011-12-24的博文“纠正对NP 问题的错误理解”发出后，收到网友的评论。看来还有必要对NP 问题的错误理解，再做些澄清和解释。我们先看网友评论的原文：

【geneculture  2011-12-25 12:57

确定性计算机面对的是多项式时间内可计算的问题，同时，也是多项式时间内可处理的问题。
非确定性计算机面对的是非多项式时间内可计算的问题，同时，也是非多项式时间内可处理的问题。但是这并不排除一旦其解找到后，它是多项式时间内可检验的问题，同时也不排除没有找到解之前，它是非多项式时间内可检验的问题。
所以，当“P=NP”与“P≠NP”不可判定的时候，它究竟是“交”和“并”无法确定（此时可否把它视为既“不交”又“不并”而相对独立的呢？）！。

(2011-12-25 12:36)：仅就形式而论，除非“N可有可无”否则就不能说“P=NP”与“P≠NP”同时成立（因为由此必然推出“悖论”）。
(2011-12-25 12:32)："区分显而易见（P 问题可视为其一类特例）和非显而易见（NP 问题也可视为其另一类特例）两类情形，进而掌握由P到NP的理解与由NP到P的表达两个转化过程成立的条件（即N可有可无）。"

提示：
不错，P和NP是仅就计算机的可计算性以及计算复杂性而言的专门问题。但是，对其上位的“自然人+计算机”而构成的“协同智能计算系统”而言，它就可归结为“显而易见”与“非显而易见”的特例。 http://blog.sciencenet.cn/home.php?mod=space&uid=94143&do=blog&id=520680    】

 

1，         关于P问题和NP问题的概念

 

显然这位网友一开始就把概念搞混了。确定的机器和非确定的机器都可以面对在多项式时间内计算问题，也可以面对超出多项式时间的计算问题。没有理由硬说“确定性计算机面对的是多项式时间内可计算的问题，”“非确定性计算机面对的是非多项式时间内可计算的问题。”

做学术研究是严肃的，首先必须对其中的概念搞清楚，正确理解，然后才能谈得上研究和应用。我们现在要澄清的是对NP问题的错误理解。

要正确的理解一个学术概念，纠正一些错误的理解，有时是三言两语讲不通的，需要静下心来认真读点书或资料。P vs NP问题既然是悬赏100万美元奖励的世纪七大难题之一，对问题的陈述自然是必须要有个规范的版本。这就是：

Stephen Cook. The P versus NP problem. In The millennium prize problems, pages 87–104. Clay Math. Inst., Cambridge, MA, 2006.

这本书的电子版可以很容易在百科文库网站免费下载：

http://wenku.baidu.com/view/3644978ad0d233d4b14e69d7.html

我们引其中一段定义：

Now we define the class P of languages by P = {L | L = L(M) for some Turing machine M that runs in polynomial time}.

The notation NP stands for “nondeterministic polynomial time”, since originally NP was defined in terms of nondeterministic machines (that is, machines that have more than one possible move from a given configuration).

对P和NP的定义写得相当清楚。P代表在多项式时间界限下，确定的图灵机器所接受的语言类，NP代表在多项式时间界限下，非确定的图灵机器所接受的语言类。

图灵机器所接受的语言同我们说的解决问题是什么关系呢？我们来做些解释。图灵机器所接受的语言就是图灵机器所接受的字的集合。以命题逻辑公式的可满足性问题为例，问题的解是构造一个算法，对给出的任意一个逻辑公式（如P∧Q，P∧┐P等），算法都能回答出它是可满足的（即对公式中命题变量赋于某值后能使公式为真）还是不可满足的。例如P∧Q是可满足的，P∧┐P就是不可满足的。已经证明对这个问题可以构造一个非确定的图灵机器T 和一个多项式函数f，凡是可满足的公式（字），均可被此机器在f(l)步内接受（l是公式长度），其它不可满足的公式将被此机器在f(l)步内拒绝。此机器所接受的语言就是所有可满足的公式的集合。

所以说命题逻辑公式的可满足性问题是NP问题。也就是说是非确定的图灵机器在多项式时间内解决的问题。现在不知道的是：是否存在一个确定的图灵机器能在多项式时间内解决此问题（即是否属于P）。因为此问题已证明是NP完全（NPC）问题，所以只要证明它属于P，则所有NP问题都属于P，即P=NP，反之只要证明它不属于P，则P≠NP。

如果把网友评语的前两句话试着改成如下的陈述，我想就对了。

P问题是确定性计算机在多项式时间内可计算的问题，同时也是确定性计算机在多项式时间内可处理的问题。

NP问题是非确定性计算机在多项式时间内可计算的问题，同时也是非确定性计算机在多项式时间内可处理的问题。一个NP问题如果用确定性计算机计算，一般需要超过多项式时间。但是这并不排除能找到一个确定性计算机可在多项式时间内解决此问题，如果能找到，就证明了此NP问题是P问题（如果此NP问题是NPC问题，你就证明了P=NP）。当然在没有找到之前，它仍然只是NP问题。如果你能证明对此NP问题根本不可能找到确定性计算机在多项式时间内解决此问题，那你就找到了一个反例证明了P≠NP。

2，        P和NP的包含关系

按照定义，P是所有P问题的集合，NP是所有NP问题的集合。由于确定的图灵机是非确定图灵机的特例，所以所有的P问题都是NP问题，也就是说已知P 被包含在NP中。于是P 与NP的交集就是P，P 与NP的并集就是NP

现在的问题是不知道P 和NP是否相同，如果你能证明NP包含在P中，即证明所有的NP问题都是P问题（有了Cook的工作，只需要证明有一个NPC问题是P问题即可），你就证明了P =NP。反之如果你能找到一个NP问题证明它不是P问题，你就证明了P ≠NP。

3，        关于不可判定问题

我们要注意，前面讲的P问题，NP问题，以及命题逻辑公式的可满足性问题等都不是单个的要求回答一个Yes 或No的问题，而是面对一类问题（包含很多单个问题），要找一个统一的算法（图灵机器）来，此算法能对此类问题中的每个单个问题回答Yes 或No。如果对算法的时间复杂度要求是多项式，则是P问题，NP问题，如果没有时间复杂度的要求，就是一般的可判定问题。有趣的是在没有时间复杂度的要求下确定的图灵机和非确定图灵机可判定的问题类是等同的。

已经证明是不可判定的问题很多，例如曾证明了图灵机的停机问题是不可判定的。还证明了许多逻辑系统以外的实际数学问题是不可判定的。如证明了有名的希尔伯特第十问题是不可判定的，即不存在这样的算法，它能判定一个任意的丢番图方程(Diophantine Equation)是否有整数解。所谓丢番图方程就是整系数代数多项式方程，如x²+y²=z²，xⁿ+yⁿ=zⁿ等。聪明的俄国年轻人马蒂亚塞维奇 (Yuri Matiyasevich,) 1970年（23岁）成功地证明了罗宾逊猜想，最终解决了希尔伯特第十问题，证明它是不可判定的。所谓不可判定是指不存在一个统一的算法，对任给的丢番图方程判定它是否有整数解。这并不排除对于某些单个的丢番图方程证明它有整数解或无整数解。如x²+y²=z² 中国古代就已知勾3股4弦5是它的一组解。xⁿ+yⁿ=zⁿ在n>2时没有非零整数解(费尔马猜想)，提出后隔了三百多年(1995)终于得到证明。

从以上分析可知P vs NP是需要直接回答Yes 或No的问题，不属于需要找出统一算法的可判定或不可判定问题的范畴。我们现在还不知道是否P = NP，不能就说它不可判定。“不知道”和“不可判定”不是一回事。

4，        概念的字面意思和定义

在人类社会活动的初期，建立的概念不多，通过概念的字面大家就可得到共识。但是当人类社会发展到现在，特别是各种各样的学科创建的概念成千上万，不可能通过概念的字面就能得到大家的共识。这就要靠概念的定义来统一大家的共识。通过概念的定义有了共识，有了共同的语言，大家才能进行学术交流和讨论。单靠字面意思已经不能表达概念的确切内涵。例如数学上的群、环、域等概念，你如果没有学过抽象代数，单凭字面是无法把握这些概念的含义的，从字面上理解的牛群、人群，花环、光环和数学上的群、环、域等概念风马牛不相及。

我们前面提到的概念都有它严格的明确的定义，不是随便说说的。如：字(字母表上的字符串)，语言(字的集合)，确定的图灵机，非确定的图灵机，接受的字，接受的语言，多项式时间限制，P问题NP问题，P，NP等。在我们用到这些概念时，大家都有关于这些概念定义的共识，这是我们进行严肃学术讨论、交流的基础。

在网友的这个评论中我们可以看到有些概念如“显而易见”、“非显而易见”、“N可有可无”并没有给出确切的定义，我们怎么认同你说的“显而易见（P 问题可视为其一类特例）和非显而易见（NP 问题也可视为其另一类特例）”。 “显而易见”、“非显而易见”单从字面上讲是个非常模糊的概念，究竟什么是“显”，什么是“易”，在这些没有讲清楚以前，我们怎么去认可P 问题NP 问题可视为它们的特例？研究和讨论不能建筑在这些没有（被大家认可的）确切的定义的概念之上，没有共识就无法交流和讨论。