博文
TTU论文《A non-canonical example to support that P≠NP》刊出
||
期待15个月的英文论文终于刊出了，2011, 17(6): 446-449。
A non-canonical example to support P is not equal to NP
SpringerLink：http://www.springerlink.com/content/q544u0gp2mv60642/
EI Compendex Web: 20120714762933
真诚感谢有关的老师、专家、领导（因为专家、领导都是老师）！
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的例子
除了原来的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.
谢谢！
http://bbs.sciencenet.cn/home.php?mod=space&uid=107667&do=blog&id=451952
[2] 《A FULL PROOF to the P versus NP problem》
or: http://blog.tech110.net/index.php?uid-11851-action-viewspace-itemid-61623
or: http://bbs.sciencenet.cn/forum.php?mod=viewthread&tid=523235
[3] 《“P对NP”难题研究的形转换新思路》
http://idea.cas.cn/viewdoc.action?docid=1275
[4] 《“P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案》
http://bbs.sciencenet.cn/forum.php?mod=viewthread&tid=266338
https://blog.sciencenet.cn/blog-107667-515297.html
上一篇：科学家出重要成果年龄变大
下一篇：“四大天象”将至，敬请本网摄影高手关注