博文

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

已有 6421 次阅读 2011-12-5 22:32 |系统分类:科研笔记| 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。

Transactions of Tianjin University

Volume 17, Number 6, 446-449, DOI: 10.1007/s12209-011-1593-5

Zhengling Yang

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

SpringerLink：http://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 “P≠NP”, they are not repetitions to this paper.

真诚欢迎您的批评！假如您觉得还值得批评！
谢谢！