博文
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)
杨正瓴, Zheng-Ling YANG, YANG Zhengling
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
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.
支持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。
拟投英文稿2个，正在写作。
相关链接：
真傻对“P对NP（P versus NP, P vs NP）”问题的思考，请看：
[1] “P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案：http://bbs.sciencenet.cn/forum.php?mod=viewthread&tid=266338
[2] Vinay Deolalikar宣称自己证明了“P!= NP”（P 不等于 NP）：http://bbs.sciencenet.cn/forum.php?mod=viewthread&tid=106360
https://blog.sciencenet.cn/blog-107667-483639.html
上一篇：[讨论] 名家摄影欣赏
下一篇：傻拍：诡异的云与UFO
