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

博文

TTU论文《A non-canonical example to support that P≠NP》刊出

已有 3858 次阅读 2011-12-5 22:32 |系统分类:科研笔记|关键词:non-canonical,example,,P,is,not,equal,to,NP,,DTM,,Transactions,of,Tianjin,University,,NTM,,P≠NP| equal, not, example, non-canonical, DTM

TTU论文《A non-canonical example to support that P is not equal to NP》已经刊出
 
       俺在2011-06-05《TTU 拟录用论文致谢》里预告发表的英文论文“A non-canonical example to support that P is not equal to NP”,今天接到 27400281(Transactions of Tianjin University,TTU,EI核心期刊)编辑部电话,可以领取纸质期刊了。
       期待15个月的英文论文终于刊出了,2011, 17(6): 446-449。
 
Volume 17, Number 6, 446-449, DOI: 10.1007/s12209-011-1593-5

A non-canonical example to support P is not equal to NP 

SpringerLinkhttp://www.springerlink.com/content/q544u0gp2mv60642/

EI Compendex Web:  20120714762933

http://www.engineeringvillage2.org/controller/servlet/Controller?SEARCHID=121b59a13617775973M434fprod4data2&CID=quickSearchDetailedFormat&DOCINDEX=1&database=1&format=quickSearchDetailedFormat


真诚感谢有关的老师、专家、领导(因为专家、领导都是老师)!

   
       该文Abstract:
       The more unambiguous statement of the P versus NP problem and the judgement of its hardness, are the key ways to find the full proof of the P versus NP
problem. There are two sub-problems in the P versus NP problem. The first problem is classifications of different mathematical problems (languages), and the second is the distinction between a non-deterministic Turing machine (NTM) and a deterministic Turing machine (DTM). The process of an NTM can be a power set of the corresponding DTM, which proves that the states of an NTM can be a power set of the corresponding DTM. If combining this viewpoint with Cantor’s theorem, it is shown that an NTM is not equipotent to a DTM. This means that “generating the power set P(A) of a set A” is a non-canonical example to support that P is not equal to NP.
 
一个模糊的图片如下:


       该文主要观点:
       (1)由于逻辑证明是二值的,所以对于区分“指数”、“多项式”这类量的差异的“P对NP”问题,二者是不配套或者不协调的。这是“P对NP”问题困难性的主要来源。
       (2)“生成某集合的幂集”,确定型图灵机DTM必须使用指数时间;相反非确定型图灵机NTM可以用多项式时间。由于该例子不是传统复杂性的类型,所以是Non-canonical的例子
。该例子强烈暗示“对于DTM,P不等于NP(P≠NP)”,尽管没有证明它。
 
       除了原来的Acknowledgments没能刊出外,原稿的Remarks也由于格式问题,没能刊出。现附录如下:

       “The process of a NTM can be the power set of a DTM”, the main idea for this paper, was reported orally by the author in his report “From the hierarchy of NP to the classification of supercomputer” in the Student Academic Symposium of Graduate School to Celebrate the 100th Anniversary of the Founding of Tianjin University, October, 1995. The key viewpoints of his oral report can be seen in his Chinese paper “conception of the second class computer”, which published in the Journal of China Academy of Electronics and Information Technology, 2011, 6(4): 368-374.

       “The 3-SAT can have a nonplanar graphic structure, but 2-SAT has definitely a planar graphic structure” was reported orally also, which has no relation to the viewpoints of this paper.

       “The classification of supercomputer” in the report was published in the journal of “Philosophy Research” in 1999, (4). Our paper names “The second class mathematics (intelligence mathematics) to simulate human intelligence and its philosophical research”, which is in Chinese characters. Our viewpoints in Philosophy Research paper are the generalization of “PNP”, they are not repetitions to this paper.

   
真诚欢迎您的批评!假如您觉得还值得批评!
谢谢!
 
相关链接:
[1] 《TTU 拟录用论文致谢
http://bbs.sciencenet.cn/home.php?mod=space&uid=107667&do=blog&id=451952
 
[2] 《A FULL PROOF to the P versus NP problem
 


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

上一篇:科学家出重要成果年龄变大
下一篇:“四大天象”将至,敬请本网摄影高手关注

6 曾新林 高建国 张树风 鲍得海 邹晓辉 crossludo

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

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

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

GMT+8, 2018-12-18 23:08

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部