||
A non-canonical example to support P is not equal to NP
SpringerLink:http://www.springerlink.com/content/q544u0gp2mv60642/
EI Compendex Web: 20120714762933
真诚感谢有关的老师、专家、领导(因为专家、领导都是老师)!
该文主要观点:
(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.
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-8 06:30
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社