求真分享 http://blog.sciencenet.cn/u/zlyang 求真务实

博文

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

已有 4199 次阅读 2011-9-6 23:55 |个人分类:基础数学-逻辑-物理|系统分类:科研笔记|关键词:the,P,versus,NP,problem,,,(P,vs,NP)| The, Problem, versus

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
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.

支持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



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

上一篇:[讨论] 名家摄影欣赏
下一篇:傻拍:诡异的云与UFO

3 黄兴滨 高建国 俞立

该博文允许注册用户评论 请点击登录 评论 (5 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2018-11-16 15:47

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部