Back to Search Start Over

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

Authors :
Yang, Zhengling
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