Back to Search Start Over

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

Authors :
Zhengling Yang
Source :
Transactions of Tianjin University. 17:446-449
Publication Year :
2011
Publisher :
Springer Science and Business Media LLC, 2011.

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.

Details

ISSN :
19958196 and 10064982
Volume :
17
Database :
OpenAIRE
Journal :
Transactions of Tianjin University
Accession number :
edsair.doi...........a0060549a1390a14f1af50c1e677288f
Full Text :
https://doi.org/10.1007/s12209-011-1593-5