What is it about?
My paper gives a direct finite answer to the problem "P vs NP" in the Millennium Prize Problems.
Featured Image
Why is it important?
My paper "A non-canonical example to support P is not equal to NP" proved: (1) According to "the axiom of power set" in ZF, a NTM is equipotent to the power set of its corresponding DTM. (2) The existence of NPI is an embodiment of continuum hypothesis in the infinite versions, which is considered as independent to ZFC. NPI (NP-Intermediate) is the set of languages (problems) neither in P nor in NP-complete, if P ≠ NP. Here, P vs NP = P versus NP problem, NTM = non-deterministic Turing machine, DTM = TM = deterministic Turing machine, ZF = Zermelo–Fraenkel set theory, ZFC = Zermelo–Fraenkel set theory with the axiom of choice, NPI = NP-Intermediate. Reference: [1] P vs NP, The Millennium Prize Problems, Clay Mathematics Institute https://www.claymath.org/millennium/p-vs-np/ [2] Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1979. [3] ZFC, Zermelo–Fraenkel set theory with the axiom of choice. Encyclopedia of Mathematics. https://encyclopediaofmath.org/wiki/ZFC
Perspectives
Conclusions on the full proof of "P vs NP": "P versus NP "is actually a synthesis of three more specific problems: ① for a NTM, P = NP; ② for a DTM, P ≠ NP; ③ If there is no necessary specific about the theoretical computer model used, it is independent.
Dr Zheng-Ling YANG
Tianjin University
Read the Original
This page is a summary of: A non-canonical example to support P is not equal to NP, Transactions of Tianjin University, December 2011, Springer Science + Business Media,
DOI: 10.1007/s12209-011-1593-5.
You can read the full text:
Contributors
The following have contributed to this page
