[FOM] Proof-sketch: Why NP is not P

[Lew Gordeew]

Proof-sketch: Why NP is not P

Abstract

The way is shown how to prove that NP is not P; it is not the proof 
proper yet, but what remains to be done is technical, though 
non-trivial, work along the lines of traditional combinatorics.

The underlying logic scheme is obvious - we assume that NP is P 
(actually in the weak form 'TAU is P/poly', where TAU is the familiar 
co-NP complete propositional tautology problem) and try to derive a 
contradiction by the appropriate chain of inferences. This chain 
consists of the four main inferences A, B, C, D which, loosely speaking, 
embed the discrete assumption 'TAU is P/poly' first into the real 
multi-dimensional continuum and then back into discrete combinatorics. 
These inferences are as follows.

(A) The assumption is reduced to an algebraic sentence (SA) stating that 
for suffiicently large n, there are "small" borel polynomials (P_n) 
having "regular" n^2-dim linear atoms and the same n^2-dim real zero-set 
(Z_n) as a fixed "large" polynomial that characterizes the n^2-variable 
restriction of TAU.

(B) SA is reduced to an analogous sentence (SB) stating that the 
appropriate "regular-positive-consistent" Sigma_2-form of Pn has the 
same zero-set Z_n.

(C) SB is reduced to a topological sentence (SC) stating that the 
corresponding Sigma_2-decomposition of Z_n covers the canonical 
Sigma_2-base of Z_n.

(D) SC is reduced to a combinatorial sentence (SD) about the structure 
of the Sigma_2-base in question that can be refuted by straightforward 
combinatorial arguments - thus leading to a desired contradiction.

L. Gordeev,
WSI f. Informatik
Tuebingen University
gordeew at informatik.uni-tuebingen.de

Full paper available in

http://www-ls.informatik.uni-tuebingen.de/logik/gordeew/publikationen/ProofSketch.pdf