[FOM] Why NP is not P: Basic combinatorial argument

[Lew Gordeew]

In a posting of Nov 03 I referred to [G]: http://tinyurl.com/5nn29
where proposition NP = P is reduced to a combinatorial principle, whose
negation (call it CP) thus infers that NP = P fails, and hence NP != P
holds [G: Claim 32 (p. 17)]. This note is to illuminate the underlying
combinatorial argument.

Consider the most transparent "proper positive normal subcase Pi_2" of
CP [G: pp. 14-15]. Loosely speaking, we have to show that the length of
any Pi_2-decomposition (call it Dn) of the n^2-dim real set Zn [G: 2.1.2
(p. 2)] is exponential in n. To this end, we take the corresponding
uniquely determined n^2-dim Sigma_2-base Bn [G: 2.1.6 (pp. 2-3)] and show
that the desired lower bound for Dn is determined by a complex structure of
Bn. Speaking in boolean mode, our problem is to show that a given "complex"
positive DNF is not equivalent to any "short" positive CNF.

In the sequel we call elements of Bn "basic n^2-dim sets", and for any
set A contained in n^(2*2) [G: 2.1.3 (p. 2)] we call A+ [G: 2.1.4 (p.
2)] the "closure of A". Thus A is a subset (not necessarily proper) of
A+, and A+ is contained in n^(2*2). Now the argument is as follows.

First consider the canonical n^2-dim Pi_2-decomposition of Zn (call it
DCn) that is given by the shape of Phi_n [G: 2.1.1 (p. 2)], and denote
by PDCn the Cartesian set-product of all sets from DCn.

For example, let n = 3. Then in a chosen minimal tuple-encoding of
3^(2*2), DC3 is the following collection of 3-element sets:

{1, 2, 7}, {1, 4, 8}, {1, 6, 9}, {2, 3, 16}, {3, 4, 17}, {3, 6, 18}, {2, 5,
25}, {4, 5, 26}, {5, 6, 27}, {7, 10, 11}, {8, 10, 13}, {9, 10, 15}, {11, 12,
16}, {12, 13, 17}, {12, 15, 18}, {11, 14, 25}, {13, 14, 26}, {14, 15, 27},
{7, 19, 20}, {8, 19, 22}, {9, 19, 24}, {16, 20, 21}, {17, 21, 22}, {18, 21,
24}, {20, 23, 25}, {22, 23, 26}, {23, 24, 27}

B3 contains 129 sets which are exposed in Appendix below.

Furthermore, by the basic property of Sigma_2-bases [G: Theorem 2 (p. 5)],
we note that PDCn covers Bn. To put it more precisely, the following two
conditions hold:

1C) every n^2-dim basic set S is the closure of a set A from PDCn,
2C) the closure of every set from PDCn contains a basic n^2-dim set.

For example, consider a 32-dim basic set S = {1, 3, 5, 10, 12, 14, 19, 21,
23} of minimal length 32 = 9 (check Appendix below) corresponding to a valid
(3,3)-dim matrix [[1, -1, 0], [1, -1, 0], [1, -1, 0]]. By 1C), suppose S =
A+ be the closure of some A from PDC3. Now A intersects every set from DC3,
which actually imples that S = A. Moreover, it is readily seen that S is
obtained by collapsing the list L = [1, 1, 1, 3, 3, 3, 5, 5, 5, 10, 10, 10,
12, 12, 12, 14, 14, 14, 19, 19, 19, 21, 21, 21, 23, 23, 23] of the ordinary
Cartesian product of DC3. Observe that every element of S occurs exactly 3
times in L. Since S has 9 elements, this confirms that the length of L, and
hence DC3, is not smaller than 9*3 = 27.

Generally, we have the following easy

PROPOSITION 1. Every minimal n^2-dim basic set S has n2 elements, and
every minimal A whose closure is S has 2n-1 elements. Moreover, every
element of S occurs in exactly n^(n-2) distinct elements of DCn, while
no two distinct elements of S occur in one and the same  element of DCn.
Hence DCn has at least n^2*n^(n-2) = n^n elements (in fact #(DCn) = n^n).

But what if we replace DCn by an arbitrary n^2-dim Pi_2-decomposition,
Dn, of Zn? Denote by PDn the Cartesian set-product of all sets from Dn.
By [G: Theorem 2 (p. 5)], we have:

1) every n^2-dim basic set S is the closure of a set A from PDn,
2) the closure of every set from PDn contains a basic n^2-dim set.

In the case n = 3, these conditions infer that the length of D3 is not
smaller than 5*3 = 15. To obtain this, we take S as above and first
observe that any A whose closure is S has at least 2*3-1 = 5 elements.
Secondly, without loss of generality we can assume that every 3^2-dim
basic set intersects every set from D3; this infers that every set from
D3 contains elements outside S. Thirdly, we observe that replacing any
chosen element of A by less than 3 pairwise different elements outside S
won't extend any 3^2-dim basic set. By 2), this provides us with the
desired lower bound 5*3 = 15 on the length of D3. This lower-bound
passage in a suitable iterated form is crucial for the desired proof
that the length of Dn has exponential growth in n, as given by the following

PROPOSITION 2. For any n>2 and any n^2-dim Pi_2-decomposition, Dn, of
Zn, the length of Dn is not smaller than (2n-1)*((2n-1)/n)^(n/2).

Appendix. B3 is the following collection (with respect to the chosen
minimal tuple-encoding form of 3^(2*2)):

{1, 3, 5, 11, 13, 15, 19, 21, 23}, {2, 4, 6, 11, 13, 15, 16, 17, 18, 19,
23}, {2, 3, 6, 8, 11, 12, 15, 20, 21, 24, 26}, {1, 4, 5, 6, 10, 13, 14, 15,
16, 19, 22, 23, 24}, {2, 5, 6, 8, 11, 14, 15, 17, 20, 23, 24}, {4, 6, 7, 10,
12, 14, 16, 19, 21, 23, 25}, {2, 4, 9, 11, 13, 18, 20, 22, 27}, {1, 11,
13, 15, 16, 17, 18, 19, 25, 26, 27}, {5, 7, 8, 9, 11, 13, 15, 16, 17, 18,
23}, {1, 3, 5, 11, 13, 15, 20, 22, 24}, {1, 3, 5, 7, 8, 15, 16, 17, 24, 25,
26}, {2, 4, 6, 11, 13, 15, 19, 21, 25, 26, 27}, {1, 3, 5, 8, 11, 15, 17, 20,
24, 26}, {1, 5, 11, 13, 15, 16, 17, 18, 20, 22, 24}, {1, 2, 3, 10, 11, 12,
19, 20, 21, 26, 27}, {5, 7, 8, 9, 14, 16, 17, 18, 20, 22, 24}, {2, 4, 6, 11,
13, 15, 20, 22, 24}, {1, 2, 3, 6, 10, 11, 12, 15, 19, 20, 21, 24, 26}, {3,
4, 5, 6, 7, 12, 13, 14, 15, 21, 22, 23, 24}, {2, 4, 6, 10, 12, 14, 19, 21,
23}, {2, 6, 8, 10, 12, 14, 17, 20, 24, 26}, {3, 4, 6, 7, 12, 13, 15, 21, 22,
24, 25}, {4, 6, 7, 13, 15, 16, 19, 21, 23, 25}, {2, 6, 8, 11, 15, 17, 20,
24, 26}, {1, 10, 16, 17, 18, 20, 22, 24, 25, 26, 27}, {2, 4, 6, 7, 8, 9, 11,
13, 15, 16, 17, 18, 23}, {2, 6, 8, 11, 15, 17, 19, 21, 23, 26}, {6, 7, 8,
10, 12, 14, 16, 17, 24, 25, 26}, {1, 2, 5, 10, 11, 14, 17, 18, 19, 20, 23},
{4, 6, 7, 13, 15, 16, 22, 24, 25}, {2, 4, 6, 10, 12, 14, 20, 22, 24}, {2, 4,
6, 10, 12, 20, 22, 24, 25, 26, 27}, {2, 4, 6, 7, 8, 9, 14, 16, 17, 18, 20,
22, 24}, {1, 3, 5, 8, 10, 12, 14, 17, 20, 24, 26}, {2, 4, 6, 11, 13, 15, 16,
17, 18, 19, 25, 26, 27}, {6, 7, 8, 15, 16, 17, 19, 21, 23, 25, 26}, {2, 3,
5, 8, 9, 11, 12, 14, 20, 21, 23}, {2, 4, 6, 10, 12, 19, 21, 25, 26, 27}, {2,
4, 6, 10, 16, 17, 18, 20, 22, 24, 25, 26, 27}, {5, 7, 8, 9, 11, 13, {15, 16,
17, 18, 20, 22, 24}, {1, 4, 10, 13, 16, 18, 19, 22, 25, 27}, {1, 3, 5, 7, 8,
10, 12, 14, 16, 17, 24, 25, 26}, {1, 10, 16, 17, 18, 19, 25, 26, 27}, {7, 8,
9, 16, 17, 18, 25, 26, 27}, {1, 3, 5, 8, 11, 15, 17, 19, 21, 23, 26}, {2, 6,
8, 10, 12, 14, 17, 19, 21, 23, 26}, {2, 4, 6, 7, 8, 9, 12, 21, 25, 26, 27},
{1, 2, 5, 6, 10, 11, 14, 15, 17, 19, 20, 23, 24}, {4, 5, 6, 7, 13, 14, 15,
16, 22, 23, 24}, {1, 3, 5, 7, 10, 12, 14, 16, 22, 24, 25}, {3, 7, 8, 9, 11,
13, 15, 21, 25, 26, 27}, {3, 7, 8, 9, 12, 21, 25, 26, 27}, {1, 3, 5, 7, 8,
15, 16, 17, 19, 21, 23, 25, 26}, {3, 4, 7, 9, 12, 13, 21, 22, 25, 27}, {4,
5, 7, 9, 13, 14, 16, 18, 22, 23}, {1, 3, 5, 9, 11, 13, 18, 20, 22, 27}, {1,
11, 13, 15, 16, 17, 18, 20, 22, 24, 25, 26, 27}, {1, 3, 4, 10, 12, 13, 19,
21, 22, 25, 27}, {6 7, 8, 10, 12, 14, 16, 17, 19, 21, 23, 25, 26}, {3, 7, 8,
9, 12, 20, 22, 24, 25, 26, 27}, {2, 4, 6, 11, 13, 15, 19, 21, 23}, {6, 7, 8,
15, 16, 17, 24, 25, 26}, {1, 4, 5, 10, 13, 14, 16, 18, 19, 22, 23}, {1, 3,
5, 7, 9, 13, 16, 18, 22, 25, 27}, {3, 4, 5, 7, 9, 12, 13, 14, 21, 22, 23},
{2, 4, 9, 10, 12, 14, 18, 20, 22, 27}, {4, 7, 9, 10, 12, 14, 16, 18, 22, 25,
27}, {1, 6, 10, 15, 16, 17, 19, 24, 25, 26}, {4, 7, 9, 13, 16, 18, 19, 21,
23, 25, 27}, {5, 7, 8, 9, 14, 16, 17, 18, 23}, {1, 3, 5, 7, 9, 10, 12, 14,
16, 18, 22, 25, 27}, {3, 6, 7, 8, 12, 15, 21, 24, 25, 26}, {2, 4, 6, 7, 8,
9, 11, 13, 15, 21, 25, 26, 27}, {1, 3, 11, 13, 15, 19, 21, 25, 26, 27}, {2,
4, 9, 11, 13, 18, 19, 21, 23, 27}, {1, 3, 6, 10, 12, 15, 19, 21, 24, 25,
26}, {1, 3, 5, 7, 9, 13, 16, 18, 19, 21, 23, 25, 27}, {5, 6, 7, 8, 14, 15,
16, 17, 23, 24}, {1, 3, 5, 8, 9, 11, 17, 18, 20, 26, 27}, {1, 5, 6, 10, 14,
15, 16, 17, 19, 23, 24}, {2, 4, 6, 7, 8, 9, 12, 14, 21, 23}, {2, 3, 4, 9,
11, 12, 13, 20, 21, 22, 27}, {4, 7, 9, 13, 16, 18, 22, 25, 27}, {1, 3, 10,
12, 19, 21, 25, 26, 27}, {3, 5, 7, 8, 9, 12, 14, 20, 22, 24}, {1, 2, 4, 10,
11, 13, 18, 19, 20, 22, 27}, {2, 4, 6, 7, 8, 9, 12, 20, 22, 24, 25, 26, 27},
{2, 8, 9, 10, 12, 14, 17, 18, 20, 26, 27}, {3, 5, 6, 7, 8, 12, 14, 15, 21,
23, 24}, {3, 5, 7, 8, 9, 11, 13, 15, 21, 23}, {1, 3, 11, 13, 15, 20, 22, 24,
25, 26, 27}, {2, 4, 6, 7, 8, 9, 12, 14, 20, 22, 24}, {1, 3, 5, 9, 10, 12,
14, 18, 20, 22, 27}, {2, 4, 5, 9, 11, 13, 14, 18, 20, 22, 23}, {1, 3, 5, 8,
9, 10, 12, 14, 17, 18, 20, 26, 27}, {2, 4, 6, 7, 8, 9, 11, 13, 15, 21, 23},
{2, 8, 9, 11, 17, 18, 19, 21, 23, 26, 27}, {2, 3, 5, 6, 8, 11, 12, 14, 15,
20, 21, 23, 24}, {1, 2, 4, 5, 10, 11, 13, 14, 18, 19, 20, 22, 23}, {2, 8, 9,
10, 12, 14, 17, 18, 19, 21, 23, 26, 27}, {3, 5, 7, 8, 9, 11, 13, 15, 20, 22,
24}, {1, 3, 5, 8, 9, 11, 17, 18, 19, 21, 23, 26, 27}, {1, 2, 3, 4, 10, 11,
12, 13, 19, 20, 21, 22, 27}, {1, 5, 10, 14, 16, 17, 18, 20, 22, 24}, {1, 3,
5, 7, 13, 15, 16, 22, 24, 25}, {1, 2, 6, 10, 11, 15, 17, 19, 20, 24, 26},
{1, 2, 10, 11, 17, 18, 19, 20, 26, 27}, {1, 5, 11, 13, 15, 16, 17, 18, 19,
23}, {2, 3, 4, 5, 9, 11, 12, 13, 14, 20, 21, 22, 23}, {2, 4, 6, 10, 14, 16,
17, 18, 19, 23}, {3, 7, 8, 9, 11, 13, 15, 20, 22, 24, 25, 26, 27}, {4, 7, 9,
10, 12, 14, 16, 18, 19, 21, 23, 25, 27}, {1, 3, 5, 10, 12, 14, 20, 22, 24},
{1, 5, 10, 14, 16, 17, 18, 19, 23}, {1, 3, 5, 7, 13, 15, 16, 19, 21, 23,
25}, {1, 3, 5, 9, 11, 13, 18, 19, 21, 23, 27}, {1, 3, 4, 6, 10, 12, 13, 15,
19, 21, 22, 24, 25}, {2, 8, 9, 11, 17, 18, 20, 26, 27}, {2, 4, 6, 10, 14,
16, 17, 18, 20, 22, 24}, {2, 4, 6, 10, 16, 17, 18, 19, 25, 26, 27}, {1, 3,
10, 12, 20, 22, 24, 25, 26, 27}, {2, 3, 8, 9, 11, 12, 20, 21, 26, 27}, {2,
4, 6, 7, 8, 9, 14, 16, 17, 18, 23}, {3, 5, 7, 8, 9, 12, 14, 21, 23}, {2, 4,
9, 10, 12, 14, 18, 19, 21, 23, 27}, {1, 4, 6, 10, 13, 15, 16, 19, 22, 24,
25}, {4, 6, 7, 10, 12, 14, 16, 22, 24, 25}, {1, 3, 5, 10, 12, 14, 19, 21,
23}, {2, 5, 8, 9, 11, 14, 17, 18, 20, 23}

-- 
NEU +++ DSL Komplett von GMX +++ http://www.gmx.net/de/go/dsl
GMX DSL-Netzanschluss + Tarif zum supergünstigen Komplett-Preis!