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

-- 对一位网友文章的评论

郝克刚 2012-01-21

2011-12-26的博文“纠正对NP 问题的错误理解（2）”发出后，收到网友zlyang的留言，希望我对他的文章做些评论。：

【  zlyang  2012-1-6 10:23

《A FULL PROOF to the P versus NP problem》
http://bbs.sciencenet.cn/home.php?mod=space&uid=107667&do=blog&id=486692
您愿意批评一下吗？假如值得您批评的话。论文附在博文后面。
谢谢！ 】

看了博文和有关文章后，觉得作者只是提出了一些粗略的想法和提纲，并没有给出具体和详细的论述和证明。有些内容也没有给出完整的定义，不能确切把握文章的含义，所以不好乱加评论，只能根据我的理解谈谈看法。

不敢谈“批评”，提点意见，共同讨论，共同切磋。

1，         关于证明的相对性

文中提到的证明的相对性，无疑是正确的。任何命题的证明都是相对于进行此证明所用的系统的。之所以有时在具体证明时不提及证明所用的系统，往往是由于所用的系统是隐含的，是普通的逻辑系统（如一阶谓词逻辑）和相应领域的大家公认的公理系统。只有在有问题或必要的时候才提及所用的证明系统。

2，        证明结果的三种可能性

在给定一个命题p和一个证明系统S时，有下述三种可能的结果，三者必居其一：

1）         能证明：在系统S中，可推导出p为真，记作 S┝ p

2）         能证明：在系统S中，可推导出p为假，记作 S┝ ┐p

3）         能证明：在系统S中，既推导不出p为真，也推导不出p为假。

对于前两种可能性比较好理解，对于第三种可能性有些不太好理解，因为不常见。哥德尔不完全性定理就是第三种可能性的一个典型的例子。著名的德国数学家哥德尔1931年证明了如下定理：任何一个形式系统，只要它包括了简单的初等算术且系统是一致的，就是不完全的。也就是说证明了在这个系统中可以构造一个命题，系统既推导不出此命题为真也推导不出此命题为假。

对于第三种情况，也是需要给出证明的。通常采用的方法是构造一个 “悖论”，用反证法来证。即构造一个命题，假定系统可推导出此命题为真，就可推导出它为假，假定可推导出此命题为假，就可推导出它为真，从而出现矛盾。一个无矛盾系统称为一致性系统，是不允许出现矛盾的，从而得证。

3，        对“完全证明”的看法

文章的作者对“完全证明”是这样说明的

【一个“完全证明”是指，证明一个命题，需要同时给出下面的三种情况：

①在某个指定的逻辑系统或数学系统，该命题成立。即被证明。

②在另外某个指定的逻辑系统或数学系统，该命题不成立。即被否证。

③如果没有指明所采用的逻辑系统或数学系统，该命题既不成立，也不不成立。即独立性。】

首先，我理解所谓“同时给出下面的三种情况”是指分别给出它们的证明。而③没有指明所采用的逻辑系统或数学系统，从而无法给出“该命题既不成立，也不不成立”的证明，所谓独立性也是指该命题独立于给定的公理系统。没有指明所采用的逻辑系统和数学系统，就谈不上独立不独立的问题。所以这样的“完全证明”③是永远给不出来的。

其次，只有某些特定的命题同时给出①②两种情况的证明是有需要和有意义的。如三角形的内角之和等于180度，可以在欧氏几何的公理系统中证明为真，在任何非欧几何的公理系统中证明为假。

但是并不是所有的命题都需要同时给出①②两种情况的证明。例如命题2+3=5可以在自然数公理系统中证明为真，对此命题没有必要硬去构造一个奇怪的公理系统，使此命题在此系统中证明为假。尽管从理论上说不是完全没有可能，这样的“完全证明”究竟有何需要，有何意义？大多数命题只需要在适当的系统中证明为真或证明为假即可，没有必要硬去构造两个公理系统，使此命题在一个系统中为真在另一个系统中为假，甚至再构造第三个系统，使其既推导不出为真，又推导不出为假，才算得到“完全证明”。如果每个命题都要“完全证明”，肯定垃圾公理系统就会堆积如山，后患无穷，实在没有必要。

4，         对 “P vs NP问题的一个完全证明”的看法

文章的作者宣称对“P vs NP”问题给了（或者准备给，计划给？-我未搞清楚）一个“完全证明”。 作者宣称的结论是：

【完全证明的结论

①对于NDTM，P^A=NP^A；

②对于DTM，P^B≠NP^B；

③“P对NP”具有独立性，如果不指明在那种计算机理论里进行研究。】

这里作者说明了，NDTM代表非确定的图灵机， DTM代表确定的图灵机。但是没有说明P^A，NP^A，P^B，NP^B分别代表什么？

该不是作者说的是T. Baker 等1975年提出的相对的P=NP问题吧！ P^x表示带有指示器(oracle) x的确定查询机器(query)在多项式时间界限内接受的语言类，用NP^x表示相应于非确定的查询机器的语言类。Baker 等证明了存在着集合A使P^A=NP^A，存在集合B使P^B≠NP^B。

在网友zlyang另一个英文版本中又这样写着：

【The essence of  "the P versus NP problem":

① P = NP for a NDTM;
② P ≠NP for a DTM;
③ The “P vs NP problem” can not be proved/decided, without the necessary designating of a NDTM or DTM.】

要知道Cook引入的带有指示器的查询机器同图灵机是不同的概念，P^x同P以及NP^x同NP都是不同的概念，不能把P^A=NP^A同P=NP混为一谈，也不能把P^B≠NP^B同P≠NP混为一谈。

说相对于NDTM 有P^A=NP^A，，相对于DTM 有P^B≠NP^B更是不合逻辑。要知道P对应的是DTM，NP对应的是NDTM。

至于“P对NP”具有独立性，确实有人这么猜想过。他的意思是既然在常规的逻辑和数学系统中很难证明P=NP，也很难证明P≠NP，那么有没有可能“P对NP”问题独立于常规的逻辑和数学系统。也就是说在常规的逻辑和数学系统中证明不了P=NP，也证明不了P≠NP。

我记着30年前，在我写的一篇综述文章："NP完全问题及有关理论研究"（《计算机科学》，1980年1期）有这样一段话（第42页）  http://mainpage.nwu.edu.cn/hkg/docs/epaper/1980NPCproblem.pdf

北京大学吴允曾教授将P=NP问题与著名的连续统假设  作了对比，指出它们之间有着惊人的相似性，而连续统假设已由哥德尔(Codel)和柯恩(Cohen)在30年代后期和60年代初期证明是独立于通常的集合论公理的。如果也能证明P=NP是独立于集合论公理的话，那将是非常有趣的。这不仅在计算机科学中是有意义的，而且具有重要哲学涵义。

不过这只是一种思路和设想，需要最后给出严格的证明才行。30年过去了，这方面仍然没有看到任何进展的迹象。