On the solution of the 3rd Clay Millennium problem. A short and elegant proof that P ≠ NP in the context of deterministic turing machines and Zermelo-Frankel set theory.

Main Author: Konstantinos Kyritsis
Format: Paper
Language: English
Published: 2017
Subjects:
Online Access: http://cris.teiep.gr/jspui/handle/123456789/1482
id cris-123456789-1482
recordtype dspacecris
spelling cris-123456789-14822018-02-08T10:56:36Z On the solution of the 3rd Clay Millennium problem. A short and elegant proof that P ≠ NP in the context of deterministic turing machines and Zermelo-Frankel set theory. Konstantinos Kyritsis Computational Complexity Υπολογιστική πολυπλοκότητα 3rd Clay Millennium problem Exptime-complete problems NP-complexity P-complexity In this paper we try to handle the confusing situation in the literature of having plenty many proofs published in respectable journals with referees, some of them of 100 or more pages, that prove contradictory things like P ≠ NP, P =NP, or suggestions that both are non-provable. Obviously not all of them can be correct. We try to clear the situation by providing a very short but decisive proof that P ≠ NP, so short that anyone familiar with the area, would discover any flaw or error if it existed. We provide a proof in the context of the ZF 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 becoming able to accept. 2017-06-16 Paper http://cris.teiep.gr/jspui/handle/123456789/1482 978-618-82980-0-2 en 8 1st International conference on quantitative, social, biomedical and economic issues 2017, June 29-30, Stanley hotel, Karaiskaki square, Metaxourgio, Athens, Greece
institution T.E.I. of Epirus
collection DSpace CRIS
language English
topic Computational Complexity
Υπολογιστική πολυπλοκότητα
3rd Clay Millennium problem
Exptime-complete problems
NP-complexity
P-complexity
spellingShingle Computational Complexity
Υπολογιστική πολυπλοκότητα
3rd Clay Millennium problem
Exptime-complete problems
NP-complexity
P-complexity
Konstantinos Kyritsis
On the solution of the 3rd Clay Millennium problem. A short and elegant proof that P ≠ NP in the context of deterministic turing machines and Zermelo-Frankel set theory.
abstract In this paper we try to handle the confusing situation in the literature of having plenty many proofs published in respectable journals with referees, some of them of 100 or more pages, that prove contradictory things like P ≠ NP, P =NP, or suggestions that both are non-provable. Obviously not all of them can be correct. We try to clear the situation by providing a very short but decisive proof that P ≠ NP, so short that anyone familiar with the area, would discover any flaw or error if it existed. We provide a proof in the context of the ZF 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 becoming able to accept.
format Paper
author Konstantinos Kyritsis
author-letter Konstantinos Kyritsis
title On the solution of the 3rd Clay Millennium problem. A short and elegant proof that P ≠ NP in the context of deterministic turing machines and Zermelo-Frankel set theory.
title_short On the solution of the 3rd Clay Millennium problem. A short and elegant proof that P ≠ NP in the context of deterministic turing machines and Zermelo-Frankel set theory.
title_full On the solution of the 3rd Clay Millennium problem. A short and elegant proof that P ≠ NP in the context of deterministic turing machines and Zermelo-Frankel set theory.
title_fullStr On the solution of the 3rd Clay Millennium problem. A short and elegant proof that P ≠ NP in the context of deterministic turing machines and Zermelo-Frankel set theory.
title_full_unstemmed On the solution of the 3rd Clay Millennium problem. A short and elegant proof that P ≠ NP in the context of deterministic turing machines and Zermelo-Frankel set theory.
title_sort on the solution of the 3rd clay millennium problem. a short and elegant proof that p ≠ np in the context of deterministic turing machines and zermelo-frankel set theory.
publishDate 2017
url http://cris.teiep.gr/jspui/handle/123456789/1482
isbn 978-618-82980-0-2
physical 8
conferencename 1st International conference on quantitative, social, biomedical and economic issues 2017, June 29-30, Stanley hotel, Karaiskaki square, Metaxourgio, Athens, Greece
_version_ 1646089608875737088
score 11.370737