ON THE SOLUTION OF THE 3 RD CLAY MILLENNIUM PROBLEM. A SHORT AND ELEGANT PROOF THAT P ≠ NP IN THE CONTEXT OF DETERMINISTIC TURING MACHINES AND ZERMELO- FRANKEL SET THEORY

International audienceIn 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 simple 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 3 rd 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