汉语是联合国官方正式使用的6种同等有效语言之一。请不要歧视汉语！

Chinese is one of the six equally effective official languages of the United Nations. Not to discriminate against Chinese, please!

   

[请教] P对NP：请郝克刚教授等专家指教（一）

（一般背景知识汇报，无穷化版本下的“P对NP”）

求教心切，由于种种原因，下文里面错误难免。

请您不吝批评与指教！衷心感谢！

主要相关数学分支：公理集合论，图论，概率论；以及理论计算机科学。

     

 

一、术语的缩写、相关数学知识简介

       NDTM（NTM），non-deterministic Turing machine，非确定型图灵机；DTM（TM），deterministic Turing machine，确定型图灵机；NPC，NP-complete，NP-完全；NPI，NP-Intermediate，NP里不属于P类且不属于NP-完全问题，早期指“人们不知道是属于P类还是属于NP-完全类，还有待于证明其归属”；CH，continuum hypothesis，连续统假设；TSP，traveling salesman problem，旅行推销员问题；SAT，Boolean satisfiability problem, Boolean逻辑可满足性，是由Cook证明的第一个NPC问题。

 

       ZF，Zermelo–Fraenkel set theory，策梅洛-弗伦克尔公理系统；ZFC，Zermelo–Fraenkel set theory with the axiom of choice，承认选择公理的策梅洛-弗伦克尔公理系统；NBG或GB，NBG of Neumann–Gödel–Bernays，冯·诺伊曼、P.贝尔奈斯、K.哥德尔集合论公理系统。

 

       a，可数无穷基数；c，连续统的基数（全体实数集的基数）；f，全体几何曲线集合的基数。

 

       CH的基本含义：The hypothesis, due to G. Cantor (1878), stating that every infinite subset of the continuum R is either equivalent to the set of natural numbers or to R itself.

    目前已知“连续统假设在ZF（或GB）中是不可判定的，它即不能被证明，也不能被否证。”换言之，在著名的集合论公理系统中，都不足以解决连续统假设。这正是人们不断地寻求新公理系统的主要原因。人们总希望能找到科学的为大家所能接受的公理系统，并且得以解决著名的未解决的问题。

    “Formal unsolvability is understood in the sense that there does not exist a formal derivation in the Zermelo–Fraenkel system ZF either for the continuum hypothesis or for its negation.”

 

    阿列夫Aleph是个有争议的问题。据说有人认为阿列夫₂与连续统的基数相等，还有人认为阿列夫_可数无穷仍然小于连续统的基数。所以，我不采用阿列夫来研究“P对NP”，而是采用数学意义更为直观明确的Cantor无穷级数第二序列（a, c, f, h, i, 等等）来表述。在1997年《百科知识》、1999年《哲学研究》等文章里开始使用。

   

二、本人相关背景简介

    我是一名普通的基础课教师，天生的笨傻。每年能用于真正“科研”的时间，十分有限。为了完成岗位职责，要花去大量的时间。上帝啊！我太累了！我没有时间！

    因此推出“P对NP”完全证明的个人观点，肯定是十分艰难和缓慢的。本文博文作为正式的介绍材料之一。期待有关专家指导俺修改之！

 

       1993年暑假，某天夜里后半夜，想到在“有穷情况”下的P和NP关系。这个发现，是以生命为代价换来的！

    大约到1995年初，真傻又做出“无穷版本”下的P和NP关系：是一个著名数学问题的特定解释。

        2011年3月，给出概率意义下的有穷直接证明。

 

本人专业背景简介 

  我目前是天津大学（985大学）在岗的“模式识别与智能系统”和“软件工程”2个专业的硕士生导师，工学博士学位。曾经开设硕士生选修课《人工智能专题》多年，以史忠植先生的《高级人工智能》为主要参考书。从2002年开始主讲硕士生选修课《模糊理论及应用》至今。

  我1988年硕士入学后不久，就听说了“P对NP”问题。该问题的核心，数次被两位教授重复。一位教授开设硕士生《数据结构与算法》多年，俺跟该教授上过这门课；该教授在1980年代，就指导过东欧来天津大学的访问学者。另一位教授在图论方面有较深的造诣，曾经对两个经典问题做出世界最好结果。由于未征求这两位教授的意见，此处只能隐去他们的姓名，以避免可能对他们产生的某种不必的负面影响。

  其中的图论教授，数次向我们讲解“P对NP”的核心，并推荐了名著《GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. New York: W. H. Freeman, 1979.》。我从系资料室（现更名为学院资料室）借阅该书的汉译本20余年。由本学院上届领导批准，几年前将该书赠送给我。感谢这位好心的领导！礼轻情意重！

 

  因此，“P对NP”是属于我专业背景的科学问题（数学-计算机科学）。

 

 

三、对“P对NP”核心的个人理解

3.1 “P对NP”定义的核心

        P是DTM（确定型图灵机）在多项式时间内的可判定问题类。

    这里的“问题类”，常被记为“语言类”。“可判定”是可计算性、计算复杂性里面使用的术语。可判定的一个通俗理解，就是可以求解，可以得到正确的答案。典型的P问题，有常见的排序sorting，数值矩阵的乘法。

        NP是DTM（确定型图灵机）在多项式时间内的可验证问题类。

        NP是NDTM（NTM，非确定型图灵机）在多项式时间内的可判定问题类。

 

DTM与NDTM关系的一个直观解释：

    非确定型图灵机是一种能够同时进行多路计算的“并行”的图灵机，并且限制这些并行的图灵机之间不能相互通讯。

        A nondeterministic Turing machine is a "parallel" Turing machine that can take many computational paths simultaneously, with the restriction that the parallel Turing machines cannot communicate.

 

3.2 “P对NP”的有关主流看法

    显然，P包含在NP里面。是否所有的P都是NP，是“P对NP”的表述方式之一。

        NP里面最难的称为NPC（NP完备的）。NP里面的任何问题，都可以在多项式时间内归约为NPC。

    如果NPC找到了多项式时间求解算法，则证明P=NP。

    如果证明NPC必须使用指数时间，则证明P¹NP（P不等于NP，也有人记为P！=NP）。

    如果P¹NP，则可能存在“不是P，又不是NPC”的中间类型NPI。找到一个NPI，则等效于证明P¹NP。

        NPC的例子很多。第一个NPC是SAT，常见的自然问题有TSP等。

    到目前为止，“P对NP”未见主流承认的答案。

 

        Clearly, is contained in . However, it is not known whether or not the containment is proper. The problem of whether or not equals (?) can justly be called the most celebrated open problem in the theory of computation. The significance of this question is due to the fact that many practically important problems are known to be in , whereas it is not known whether or not they are in . In fact, all known deterministic algorithms for these problems are exponential as far as time is concerned. Thus, a proof of would make all of these problems tractable.

 

        Most exponential time algorithms are marely variations on exhaustive search, whereas polynomial time algorithms generally are possible only through the gain of some deeper insight into the structure of a problem.

    大多数指数时间算法只是穷举搜索的变种，而多项式时间算法通常只有在对问题的结构有了某些比较深入的理解之后才有可能给出。

 

    现有的研究与证明方法主要有三大类：对角化diagonalization、电路复杂性circuit complexity、证明复杂性proof complexity。但国际学术界普遍的看法是这些方法都不能得到彻底的结果。一般认为，“不同数学领域的意外结合”、“P或NP新特征的使用”、“新的电路复杂性下界证明方法”以及“对角化的新变形”等是可能获得新结果的途径。

 

3.3 对“P对NP”的一些个人看法

    由于“重复发表”、“首次发表”等现行科技规范问题，这里只能就我的某些看法想有关老师汇报。其余的看法，希望能在“有同行评审的期刊”发表。敬请您的指教！

 

（1）“P对NP”的难度（为什么该问题如此难？）

    ① 由NP定义可知“对于NDTM，P=NP”，因此“对于DTM，  P¹NP”才是研究的重点。这十分类似希尔伯特第四问题，“P对NP”问题描述的不确定性，误导了人们的研究。造成了“P对NP”研究额外的困难性。缺少对DTM和NDTM结构差异的充分使用，是导致“对于DTM，P¹NP”长期缺乏明确结论的原因之一。

    ② 目前的以及历史上出现的各种主流研究方法，都集中在P或NP问题类的数量性质研究上。从问题类角度看，由于NPC类、P类只是在DTM上计算“速度”的差异，只是一种“量”的区分，而不像“可计算性”是一种质的区分，这是引起“P对NP”困难性的原因之二。因为证明所采用的“逻辑”，通常是成立、不成立两种明确状态（质）划分的。

    ③ 如果能证明对于DTM，P不等于NP，则无穷版本下的NPI就是Cantor原本意义下连续统假设的关系。预计可以得出不接受连续统假设的结论。

 

（2）“P对NP”完全证明的结论

    “P对NP”实际上是三个更具体问题的合成：

    ① 在NDTM中P等于NP；For a NDTM, P=NP;

    ② 在DTM中P不等于NP；For a DTM, P¹NP;

    ③ 没有关于所采用的理论计算机模型的必要说明，则具有独立性。

 

    从形式语言的表示看，郝克刚老师《纠正对NP 问题的错误理解（3）-- 对一位网友文章的评论》（http://blog.sciencenet.cn/home.php?mod=space&uid=506146&do=blog&id=530828）表述是很准确的。

    这里仍然采用“没有……必要说明”，基本意图是想提供多的信息：命题对公理系统的独立性，除了该命题对证明所采用的公理系统“独立”外（直观“独立”的意思），公理系统的信息量不够，也可能造成独立。例如实系数一元二次方程，当根的判别式小于0时，在实数域是没有解的。这是由公理系统信息量不够引起独立的直观类比或解释。

    参见1974年的Chaitin定理。一般认为，Chaitin的三条定理，是对Kurt Friedrich Gödel 的哥德尔第一不完全定理（Gödel's first incompleteness theorem）的信息论意义下的具体化。（Gödel incompleteness theorem 在《苏联数学百科全书 Encyclopedia of Mathematics》扩展版，http://www.encyclopediaofmath.org/index.php/G%C3%B6del_incompleteness_theorem。Kurt Gödel在《Stanford Encyclopedia of Philosophy》，http://plato.stanford.edu/entries/goedel/）

  

（3）“P对NP”完全证明结论的三类证明

    ① 有穷形式下形转化的直接证明；

    ② 无穷形式/版本下的证明，直接否证Cantor原本意义下的“连续统假设”；

    ③ 概率形式、有穷形式下的直接证明。

 

    其中“③ 概率形式、有穷形式下的直接证明”，还未公开过。计划争取英文文章。在2011年初夏，以文字形式，向党组织汇报过（党员创优活动的汇报，一个笔记本。恳请党组织保留该笔记本一些时间，感谢党的指导与关怀！）。

 

    上面的“① 有穷形式下形转化的直接证明；② 无穷形式/版本下的证明，直接否证Cantor原本意义下的‘连续统假设’”，1995年以《从NP结构到超级计算机分类理论》为题目，在天津大学百年校庆研究生院研究生学术报告会（1995年10月初）公开讲解过。可惜没有录音或录像，希望有人愿意证明我讲过。

 

    “① 有穷形式下形转化的直接证明”的细节，计划争取英文文章。

    因此，本博文主要汇报“② 无穷形式/版本下的证明，直接否证Cantor原本意义下的‘连续统假设’”。

 

（4）无穷形式/版本下的证明，直接否证Cantor原本意义下的“连续统假设”

    该证明发表在2011年TTU的《A non-canonical example to support that P is not equal to NP》，其核心在2008年《密码学与非确定型图灵机》里扼要介绍过。

 

    “无穷形式/版本”的基本意思，是将DTM、NDTM的运行时间取为无穷大（可数无穷步。接受“实无穷”，令字母表、状态数为可数无穷即可，这很自然；坚定的“潜无穷”论者可能提出怀疑。）。DTM此时只有一个新状态、一共生成a个状态；而NDTM此时产生|Q-F|^a新状态，以及指数界数目的总状态。

    直观地说：限制NDTM的转移函数每次只产生一个转移状态，则该最小的NDTM就退化为一个DTM。所以，容易证明，DTM至多用指数时间就可以模拟一个对应的NDTM。这等价于“P包含在NP里面”。

    如果证明“DTM必须用指数时间就才能模拟一个对应的NDTM”，则从某种意义上讲，就等价地证明的“P不等于NP”。而这并不容易，所以2011年TTU的文章采用“支持P不等于NP”的说法（A non-canonical example to support that P is not equal to NP）。

    演绎证明的实质，是将“公理”包含的信息，以某种方式显示出来，所以“演绎证明的结论是前提蕴含的”。假如不是前提蕴含的，就是“独立的”。

 

    假如找到NPI，则在其无穷化版本下，等价于否证Cantor原本意义下的连续统假设。

    目前众所周知的康托三分集（Cantor ternary set），显然与连续统假设（continuum hypothesis）的研究有直接的关系。

 

（5）关于“P对NP”的独立性

    ① 如果没有明确是用DTM或NDTM求解，则“P对NP”具有独立性。

    这是说“P对NP”对“用DTM或NDTM求解”独立，而不是对现有的公理集合论系统（ZF、NGB等）独立。

    这类似：实系数一元二次方程，当根的判别式小于0时，在实数域无解；在复数域有解。

    又如，1975年Baker、Gill和Solovay报道的“存在不同的计算模型A、B，使得P^A=NP^A、P^B¹NP^B分别成立。”

 

    ② 承认“对DTM，P不等于NP”，则无穷版本下的NPI，就是的Cantor原本意义下的连续统假设CH。无穷版本下NPI的存在性，对目前现有的公理集合论系统（ZF、NBG等）独立。

    所以1975年 Ladner 证明“如果P¹NP，则 NPI=(NP - P) 不是空集”以及1993年 Zimand 证明如果NP - P不空则很大（If not empty, NP - P is topologically large），都不能给出确定的结果。

    假如P不等于NP，则NPI对应一种介于多项式和指数之间的时间增长方式。由于Cantor没有构造出这样的增长方式，所以才在1878年提出连续统假设：连续统子集的基数，要么是自然数，要么还是连续统的基数。康托三分集的基数还是连续统的基数c；可以从连续线段中抽取有穷或无穷个离散点（自然数集的基数，有穷基数，或可数无穷基数a）。

 

四、请教

4.1 关于真傻的叙述

    （1）以上关于无穷化版本下的“P对NP”问题的看法是否介绍清楚？

    （2）关于“P对NP”问题难度的解释，《A non-canonical example to support that P is not equal to NP》的介绍是否清楚？

 

4.2 创新性小结与说明
         我的方法基本没有创新：属于“不同数学领域的意外结合”和“P或NP新特征的使用”，并没有超出主流的预期。
         主要创新：
        （1）提出“完全证明Full proof”作为数学证明的新标准；
        （2）建立无穷版本下的NPI与Cantor原本意义下连续统假设的关系。
        其它的都是主流预期的，没什么让人耳目一新的。惭愧！

   

4.3 有关的问题请教

    （1） “2TSP是P，3TSP是NPC”的证明，还有在SCI、EI期刊发表的可能性吗？

    （2）“P对NP”相关问题对ZF的独立性，是否有进一步研究的必要和可能？

 

 

真诚期待有关专家的批评与指教。

衷心感谢！

 

主要参考文献：

[1]      COOK S. The P versus NP Problem, official problem description, [EB/OL]. http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf

[2]      ALLENDER E. A status report on the P Versus NP question [J]. Advances in Computers, 2009, 77: 117-147.

[3]      FORTNOW L. The Status of the P versus NP Problem [J]. Communications of the ACM, 2009, 52(9): 78-86.

[4]      SIPSER M. The history and status of the P versus NP question [C]. Proceedings of the 24th Annual ACM Symposium on the theory of Computing’ 92 (Canada) , 1992, pp 603–618.

[5]      COOK S. The importance of the P versus NP question [J]. Journal of the ACM, 2003, (50)1: 27-29.

[6]      HAZEWINKEL M. Encyclopaedia of mathematics: an updated and annotated translation of the Soviet “Mathematical encyclopaedia”[M]. Dordrecht: Kluwer Academic Publishers, 2001.

[7]      HOPCROFT J E, MOTWANI R M, ULLMAN J D. Introduction to automata theory, languages, and computation (Third edition) [M]. New Jersey: Addison Wesley, 2006.

[8]      GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. New York: W. H. Freeman, 1979.

[9]      Nondeterministic Turing Machine [EB/OL]. http://mathworld.wolfram.com/NondeterministicTuringMachine.html

[10]  CHAITIN G J. Information-theoretic computational complexity [J]. IEEE Transactions on Information Theory, 1974, 20(1): 10-15.

[11]  中国大百科全书•数学[M]. 北京: 中国大百科全书出版社, 1988.

[12]  BAKER T, GILL J, SOLOVAY R. Relativizations of the P =? NP question [J]. SIAM Journal on Computing, 1975, 4(4): 431-442.

[13]  LADNER R E. On the structure of polynomial time reducibility [J]. Journal of the ACM, 1975, 22(1): 155-171.

[14]  ZIMAND M. If not empty, NP - P is topologically large [J]. Theoretical Computer Science, 1993, 119: 293-310.

[15]  Weisstein, Eric W. "Nondeterministic Turing Machine." From MathWorld--A Wolfram Web Resource[EB/OL]. http://mathworld.wolfram.com/NondeterministicTuringMachine.html

[16]  杨正瓴. 从NP结构到超级计算机分类理论 [R]. 天津大学百年校庆研究生院研究生学术报告会（一等奖论文），和天津大学百年校庆自动化系学术报告会，1995年10月.

[17]  杨正瓴. 人脑有多复杂？[J]. 百科知识，1997，7（总第216期）：pp39 – 40.

[18]  杨正瓴. 人脑复杂性的估计及其哲学意义[M]，《中国新时期社会科学成果荟萃》，1999，第1卷p296。卢继传 主编，中国经济出版社，北京，ISBN 7 – 5017 – 4100 – X/G. 374，（第2编，哲学，第4章，自然辩证法）.

[19]  杨正瓴，林孔元. 人类智能模拟的“第2类数学（智能数学）”方法的哲学研究 [J]. 哲学研究，1999, (4): 44-50.

[20]  杨正瓴. 密码学与非确定型图灵机 [J]. 中国电子科学研究院学报, 2008, 3(6): 558-562.

[21]  杨正瓴. 第二类计算机构想 [J]. 中国电子科学研究院学报, 2011, 6(4): 368-374.

[22]  YANG Zhengling (杨正瓴). A non-canonical example to support that P is not equal to NP [J]. Transactions of Tianjin University, 2011, 17(6): 446-449.

  

相关链接：

[1] 郝克刚教授《纠正对NP 问题的错误理解（3）-- 对一位网友文章的评论》
http://blog.sciencenet.cn/home.php?mod=space&uid=506146&do=blog&id=530828

[2] 徐建良教授《P对NP -- 与杨正瓴老师商榷》
http://blog.sciencenet.cn/./home.php?mod=space&uid=66861&do=blog&id=551309

 

 

[6] 《A FULL PROOF to the P versus NP problem》
http://bbs.sciencenet.cn/home.php?mod=space&uid=107667&do=blog&id=486692

里面有一些全文可以下载。您有兴趣，可以直接跟我要相关的论文全文。

[7] 《[讨论] “P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案》
http://bbs.sciencenet.cn/forum.php?mod=viewthread&tid=266338

[8] 《[讨论] Vinay Deolalikar宣称自己证明了“P!= NP”（P 不等于 NP）》
http://bbs.sciencenet.cn/forum.php?mod=viewthread&tid=106360