Back to Search
Start Over
A non-canonical example to support P is not equal to NP
- 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