Le Centre National de la Recherche Scientifique – Paris

In the link below, my prsentation there:

Best,

Rafee Kamouna.

http://www.4shared.com/office/IezDgtsi/P_vs_NP_-_Presentation_4.html

P = NP iff P != NP

The P vs. NP Problem, see: http://www.claymath.org/millennium.

The Kleene-Rosser Paradox ==> P = NP  iff  P != NP

P = NP  iff  P != NP, A Turing Machine that Diagonalizes Against Itself

Mathematics is Inconsistent: at http://www.4shared.com/office/OpzjDoKb/3_Papers.html

As the lambda calculus is equivalent to Turing machines. By direct encoding of the lambda calculus paradox, you obtain it on Turing machines.

This proof was syntactic, the same result can be reached independently via semantics.

The line of argumentation of Cook’s proof of CNF SAT being NP-complete is as follows:

 ”Let A be a language in NP accepted by a non-deterministic Turing machine M. Fix an input x, we will create a 3CNF formula \phi that will be satisfiable if and only if there is a proper tableau for M and x”

1. Let w be the encoding of the Kleene-Rosser paradox, thus e^-1(w)=Not e^-1(w), where e is an encoding function.
2. M accepts w.
3. SAT is NP-complete, Cook’s theorem.
4. There must exists \phi(w):\phi(w) is satisfiable.
5. Then \phi(w) is satisfiable iff M accepts w iff e^-1(w)=Not e^-1(w)
6. M accepts w is “True”.
7. Then: \phi(w) is satisfiable iff e^-1(w)=Not e^-1(w) – Logical Contradiction.
8. Then There must be no \phi(w) which is satisfiable.
9. Then SAT is (NOT) NP-complete.