[FOM] Why NP is not P

[Lew Gordeew]

  In previous posting of Nov 03 we referred to
[G]:

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

where proposition NP = P was reduced to a combinatorial principle, whose
negation (call it CP) thus infers that NP = P fails, and hence NP != P holds
[G: Claim 32]. Since the precise description of CP is rather involved, most
transparent instances of CP were briefly discussed, too [G: Claims 26, 28,
30]. Here we loosely address the combinatorial background.

Recall school algebra. Consider the expansion operation 'expand' whose
primary application is to distribute products over sums. Example:

expand(((x + y) * (z + u) + (a + b) * (c + d)) * (v + w)) = xzv + xzw + xuv
+ xuw + yzv + yzw + yuv + yuw + acv + acw + adv + adw + bcv + bcw + bdv +
bdw

Clearly 'expand' is analogous to the familiar boolean/borel DNF-expansion.
For example, we have (where x_ and y_ denote the negation of x and y,
respectively):

1. expand(((x + y) * (z + x) + (a + x) * (c + x_)) * (v + y_)) = xzv + xzy_
+ xxv + xxy_ + yzv + yzy_ + xyv + xyy_ + acv +acy_ + ax_v + ax_y_ + xcv +
xcy_ + xx_v + xx_y_

In boolean/borel case we can upgrade 'expand' to 'expandc' that removes all
inconsistent (zero-) clauses:

2. expandc(((x + y) * (z + x) + (a + x) * (c + x_)) * (v + y_)) = xzv + xzy_
+ xxv + xxy_ + yzv + xyv + acv + acy_ + ax_v + ax_y_ + xcv + xcy_

Furthermore, we consider a modified "positive" expansion 'expandcp' that
removes all remaining negative literals:

3. expandcp(((x + y) * (z + x) + (a + x) * (c + x_)) * (v + y_)) = xzv + xz
+ xxv + xx + yzv + xyv + acv + ac + av + a + xcv + xc

Finally, we define the corresponding operation 'base' by applying the
remaining boolean laws - this yields:

4. base(((x + y) * (z + x) + (a + x) * (c + x_)) * (v + y_)) = x + yzv + a

Now consider minimal inversions of 'base'. We ask how "small" can be input
polynomial P such that base(P) = B for a given "big" basic expansion
B. Intuitively, if B is very involved, then P can't be very small. Actually
we specify "small" and "big" as being (space-) polynomial and
exponential in a given parameter n, respectively.

Back to CP, our most transparent instances are in the following form, for a
given precisely defined "big" basic expansion (called Sigma_2-base) Bn.

Proposition. Let c > 0 be fixed. There is no polynomial P satisfying base(P)
= Bn, whose weight is smaller than n^c, provided that n is big enough.

CP itself is a slight modification thereof. Formalization of the proofs
(work in progress) will hardly require strong set-theoretical assumptions
like those used in Harvey Friedman's combinatorics.

-- 
Geschenkt: 3 Monate GMX ProMail + 3 Top-Spielfilme auf DVD
++ Jetzt kostenlos testen http://www.gmx.net/de/go/mail ++