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

My report and papers on

"the P versus NP problem" (P vs NP)

Abbreviations:

NDTM, non-deterministic Turing machine;
DTM, deterministic Turing machine;
NPC, NP-complete;
NPI, NP-Intermediate;
CH, continuum hypothesis;
TSP, traveling salesman problem.

The 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, because "Any proof is relative, since it is based on certain unprovable
assumptions." http://eom.springer.de/P/p075420.htm (Encyclopaedia of Mathematics, Edited by Michiel Hazewinkel, an updated and annotated translation of the Soviet "Mathematical encyclopaedia")

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 NTM or DTM.

The keys of two  sufficient proofs of  "P ≠NP for a DTM":

(1) 2SAT is a planar graph; 3SAT can be a non-planar graph, since it can have the Kuratowski graph K3,3.
(2) Non-canonically, a maximal NDTM is the power set of DTM. If the "Axiom of power set" in ZFC (Zermelo–Fraenkel set theory with the axiom of choice) is accepted, then P ≠NP for a DTM.

My relative report and papers:

[1] 从NP结构到超级计算机分类理论[R]. 天津大学百年校庆研究生院学术报告会（一等奖论文）, 和天津大学百年校庆自动化系学术报告会,  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类数学（智能数学）”方法的哲学研究[J]. 哲学研究, 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] 密码学与非确定型图灵机[J]. 中国电子科学研究院学报, 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] 第二类计算机构想[J]. 中国电子科学研究院学报, 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)

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

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

[1] “P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案：
[2] Vinay Deolalikar宣称自己证明了“P!= NP”（P 不等于 NP）：http://bbs.sciencenet.cn/forum.php?mod=viewthread&tid=106360

http://blog.sciencenet.cn/blog-107667-483639.html

## 相关博文

GMT+8, 2021-4-14 22:29