Back to Search
Start Over
A non-canonical example to support P is not equal to NP.
- Source :
- Transactions of Tianjin University; Dec2011, Vol. 17 Issue 6, p446-449, 4p
- Publication Year :
- 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10064982
- Volume :
- 17
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- Transactions of Tianjin University
- Publication Type :
- Academic Journal
- Accession number :
- 69653228
- Full Text :
- https://doi.org/10.1007/s12209-011-1593-5