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
Online Access: http://cris.teiep.gr/jspui/handle/123456789/1482
Conference: 1st International conference on quantitative, social, biomedical and economic issues 2017, June 29-30, Stanley hotel, Karaiskaki square, Metaxourgio, Athens, Greece
Physical Description: 8
ISBN: 978-618-82980-0-2
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.