IJPAM: Volume 120, No. 3 (2018)

Title

THE SOLUTION OF THE 3RD CLAY
MILLENNIUM PROBLEM. A SHORT PROOF THAT
$P\neq NP=EXPTIME$ IN THE CONTEXT OF
ZERMELO-FRANKEL SET THEORY

Authors

Konstantinos Kyritsis
Department of Accounting-Finance
University of Applied Sciences (TEI) of Epirus
GREECE

Abstract

In this paper I provide a very short but decisive proof that $P\neq NP$, and $NP=EXPTIME$ in the context of the Zermelo-Frankel set theory and deterministic Turing machines. We discuss also the subtle implications of considering the $P$ versus $NP$ problem, in different axiomatic theories. The results of the current paper definitely solve the 3rd Clay Millennium problem $P$ versus $NP$, in a simple and transparent away that the general scientific community, but also the experts of the area, can follow, understand and therefore become able to accept.

History

Received: October 30, 2017
Revised: February 12, 2018
Published: January 14, 2019

AMS Classification, Key Words

AMS Subject Classification: 68Q15
Key Words and Phrases: 3rd Clay millennium Problem, $EXPTIME$-complete problems, $NP$-complexity, $P$-complexity

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
Conway J.H., On numbers and games, Academic press (1976). http://dx.doi.org/10.1090/psapm/043/1095538

2
Cook, Stephen A., A hierarchy for nondeterministic time complexity, Proceedings of the fourth annual ACM symposium on Theory of computing, STOC '72, Denver, Colorado, USA, ACM., 187-192. http://dx.doi.org/10.1145/800152.804913

3
Cook, Stephen, The $P$ versus $NP$ Problem (PDF), Clay Mathematics Institute site, (2000).

4
Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, Englewood Cliffs, New Jersey (1981)

5
Hartmanis, J., Stearns, R. E. (1 May 1965), On the computational complexity of algorithms, Transactions of the American Mathematical Society, American Mathematical Society, 117, 285-306. http://dx.doi.org/10.1090/S0002-9947-1965-0170805-7

6
Kyritsis C., On the solution of the 3rd Clay Millennium problem. A short and elegant proof that $P\neq NP$ in the context of deterministic Turing machines and Zermelo-Frankel set theory, Proceedings of the first ICQSBEI 2017 conference, Athens, Greece, 170-181.

7
Luca Trevisan, Notes on Hierarchy Theorems, U.C. Berkeley.

8
John C. Martin, Introduction to Languages and the Theory of Computation (2nd ed.) McGraw-Hill, (1997).

9
Papadimitriou Christos, Computational Complexity, Addison-Wesley, (1994).

10
Stanislav, Žák, A Turing machine time hierarchy, Theoretical Computer Science, Elsevier Science B.V., 26, 3 (1983), 327-333.

11
Ivanov Viktor V., A short proof that $NP$ is not $P$, International Journal of Pure and Applied Mathematics IJPAM (2014), 81-88. http://dx.doi.org/10.12732/ijpam.v94i1.9

12
Yannakakis M., Expressing combinatorial optimization problems by linear programs, Proceedings of STOC 1988, (1998), 223-228. http://dx.doi.org/10.1145/62212.62232

How to Cite?

DOI: 10.12732/ijpam.v120i3.17 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2018
Volume: 120
Issue: 3
Pages: 497 - 510


$P\neq NP=EXPTIME$ IN THE CONTEXT OF ZERMELO-FRANKEL SET THEORY%22&as_occt=any&as_epq=&as_oq=&as_eq=&as_publication=&as_ylo=&as_yhi=&as_sdtAAP=1&as_sdtp=1" title="Click to search Google Scholar for this entry" rel="nofollow">Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).