[FOM] Proof-sketch: Why NP is not P
2472-810 at onlinehome.de
Wed Nov 3 03:00:35 EST 2004
Proof-sketch: Why NP is not P
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.
WSI f. Informatik
gordeew at informatik.uni-tuebingen.de
Full paper available in
More information about the FOM