博文

A FULL PROOF to the P versus NP problem

已有 24560 次阅读 2011-9-15 17:50 |个人分类:基础数学-逻辑-物理|系统分类:科研笔记| versus, FULL

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

A FULL PROOF to the P versus NP problem
“P对NP（P versus NP, P vs NP）”问题的一个“完全证明”

1 相关背景简介

（1）“P对NP（P versus NP, P vs NP）”问题的描述

“The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is also accepted by some (deterministic) algorithm in polynomial time.”

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

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

The Clay Mathematics Institute的原始描述：

http://www.claymath.org/millennium/P_vs_NP/.

（2）什么是“完全证明” What is a “Full Proof”？

The Mathematical proofs of a proposition must give the following three cases:

(1) The proposition is valid, under some certain axiomatic systems;

(2) The proposition is not valid, under other axiomatic systems;

(3) The proposition can not be proved/decided, without the necessary designating axiomatic systems.

A Full Proof requires that the three cases are all identified definitely.

详见：《什么是“完全的数学证明”？》，http://bbs.sciencenet.cn/forum.php?mod=viewthread&tid=83926

2 未来的可能做法

根据学术规范，通常情况下，以下重复发表不属于一稿两(多)投：

1) 在专业学术会议上做过口头报告，或者以摘要或会议板报形式报道过的研究结果，但不包括以会议文集或类似出版物形式公开发表过的全文；

2) 对首次发表的内容充实了x%以上新数据的学术论文；

3) 有关学术会议或科学发现的新闻报道，但此类报道不应通过附加更多的资料或图表而使内容描述过于详尽；

4) 重要会议的纪要、有关组织达成的共识性文件再次发表；

5) 论文以不同或同一种文字在一种期刊的国际版本上再次发表；

6) 在非英文的本国期刊上发表的属于重大发现的研究论文在国际英文学术期刊再次发表；

7) 在内部资料发表后在公开刊物上再次发表。

本帖主要学术观点，以及《第二类计算机构想》等都是汉语的，根据以上规范：计划将来形成英文的详细论证，再投英文的国际期刊。

3 1995年报告要点回顾

记DTM为确定型图灵机（deterministic Turing machine）；NDTM为“非确定型图灵机”（non-deterministic Turing machine）。

（1）“P对NP”不能被直接证明。它实际上是3个问题的合成：

① 对于NDTM，P=NP；

② 对于DTM，P≠NP；

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

（2）对于DTM，P≠NP，是通常研究的核心。

从数学研究的整体方法看，“P对NP”是属于“数”的范围。既然在“数”的方法下没有获得明确答案，就应该转移到“形”的方法进行研究。对于第一个NPC，即布尔可满足性问题（Boolean Satisfiability Problem，SAT），不难发现，在图论模型下，2SAT一定是平面图，3SAT以及4SAT则可能包含Kuratowski图K_3,3，是立体图。而5SAT可能包含Kuratowski图K₅和K_3,3，也是立体图。

（3）在无穷化版本下，NPI的存在性，就是“连续统假设CH”：可数无穷基数a和连续统基数c之间是否存在一个其它的无穷基数。

4 其后的认识

（1）用旅行推销员问题（Travelling Salesman Problem，TSP），可以比用SAT更直观地说明“P对NP”的关系。所有顶点度数为2的TSP，称为2TSP。显然，2TSP只能是一个回路，或者若干不相交的回路。因此2TSP是平面图。相反，3TSP或更高的各TSP，可能包含与K₅或K_3,3同胚的子图，不是平面图。

（2）无穷版本下的NDTM（非确定型图灵机），可以不是平面图。

计划用英文投稿。

（3）概率意义下的“对于DTM，P≠NP”，即“对于DTM，P≠NP几乎处处（almost everywhere，a. e.）成立。”

计划用英文投稿。

5 “P对NP”完全证明的要点总结

（1）完全证明的结论

①对于NDTM，P=NP；

②对于DTM，P≠NP；

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

（2）对DTM，P≠NP的3类证明

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

2TSP是平面图。相反，3TSP或更高的各TSP，可能包含与K₅或K_3,3同胚的子图，不是平面图。

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

字母表等为可数无穷时，DTM仍为可数无穷；相反，NDTM为连续统。

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

暂时不能公开，计划用英文投稿。

6 相关报告与论文

《My report and papers on "the P versus NP problem" (P vs NP)》

http://bbs.sciencenet.cn/home.php?mod=space&uid=107667&do=blog&id=483639

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

From the hierarchy of NP to a classification of supercomputer. The Student Academic Symposium of Graduated School to Celebrate the 100th Anniversary of the Founding of Tianjin University, October, 1995. (An oral report in Chinese)

[2] 人类智能模拟的“第2类数学（智能数学）”方法的哲学研究. 哲学研究, 1999, 4: 44-50.
Philosophical research on "the second class mathematics (intelligent mathematics)" for simulations of human intelligence. Philosophical Research, 1999, 4: 44-50. (in Chinese)

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

Cryptology and non-deterministic Turing machine. Journal of China Academy of Electronics and Information Technology, 2008, 3(6): 558-562. (in Chinese)

[4] 第二类计算机构想. 中国电子科学研究院学报, 2011, 6(4): 368-374.
Conception of the second class computer. Journal of China Academy of Electronics and Information Technology, 2011, 6(4): 368-374. (in Chinese)

里面有1995年报告（[1]）的主要观点概述。

[5] A non-canonical example to support that P is not equal to NP. Transactions of Tianjin University, 2011, 17(6): accepted.

支持P不等于NP的一个非规范例子（英文稿）.

YANG Zhengling (杨正瓴). A non-canonical example to support that P is not equal to NP. Transactions of Tianjin University, 2011, 17(6): 446-449. 现在已经刊出，2011-12-05后记。

[6] “P对NP”难题研究的形转换新思路，中科院在线《科学智慧火花》，2011-08-30，http://idea.cas.cn/viewdoc.action?docid=1275 。

———————————— 附录 ————————————

《第二类计算机构想. 中国电子科学研究院学报, 2011, 6(4): 368-374》
内容截取如下：