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

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

Keywords

P versus NP / computational complexity theory / Cantor’s theorem / power set / continuum hypothesis

References

[1] Cook S. The P versus NP Problem. Official Problem Description[EB/OL]. http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf, 2000.

[2] Encyclopaedia of China: Electronics and Computer[M]. Encyclopaedia of China Publishing House, Beijing, 1986 (in Chinese).

[3] The Clay Mathematics Institute. P vs NP Problem [EB/OL]., http://www.,claymath.,org/millennium/P_vs_NP/, 2000.

[4] Smale S. Mathematical problems for the next century[J]. Mathematical Intelligencer, 1998, 20(2): 7-15.

[5] Seife C. What are the limits of conventional computing?[J]. Science, 2005, 309(5731): 96

[6] Gasarch W. I. The P=?NP poll[J]. SIGACT News, 2002, 33(2): 34-47.

[7] Allender E. A status report on the P versus NP question[J]. Advances in Computers, 2009, 77, 117-147.

[8] Fortnow L. The status of the P versus NP problem[J]. Communications of the ACM, 2009, 52(9): 78-86.

[9] Cook S. The importance of the P versus NP question[J]. Journal of the ACM, 2003, 50(1): 27-29.

[10] Gassner C. Oracles and relativizations of the P =? NP question for several structures[J]. Journal of Universal Computer Science, 2009, 15(6): 1186-1205.

[11] Manea F., Margenstern M., Mitrana V., et al. A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors[J]. Theory of Computing Systems, 2010, 46(2): 174-192.

[12] Mukund M. NP-Completeness not the same as separating P from NP[J]. Communications of the ACM, 2009, 52(4): 9

[13] Kuratowski K., Mostowski A. Set Theory[M]. 1976, Amsterdam: North-Holland Publishing Company.

[14] Hazewinkel M. Encyclopaedia of Mathematics: An Updated and Annotated Translation of the Soviet “Mathematical Encyclopaedia”[M]. 2001, Dordrecht: Kluwer Academic Publishers.

[15] Hopcroft J. E., Motwani R. M., Ullman J. D. Introduction to Automata Theory, Languages and Computation[M]. 2006, 3 edition, New Jersey: Addison Wesley.

[16] Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. 1979, New York: W. H. Freeman.

[17] Nondeterministic, Turing, Machine[EB/OL]., http://mathworld.wolfram.com/NondeterministicTuringMachine.html, 2011.

[18] Chaitin G. J. Information-theoretic computational complexity [J]. IEEE Transactions on Information Theory, 1974, 20(1): 10-15.

[19] Encyclopaedia of China: Mathematics[M]. Encyclopaedia of China Publishing House, Beijing, 1988 (in Chinese).