[FOM] Combinatorial sentence that infers P < NP

[Lew Gordeew]

  In the postings of Nov 03, Nov 05, Dec 20, 2004, I referred to a
combinatorial principle that infers P < NP. That principle was rather
involved (see [G04]). Now I present a simple version thereof, called CS
below. The main simplification is due to an observation by A. Krebs that
what was called the proper normal case in [G04] is in fact characteristic
for P < NP.
 
1. _Basic_notations_ (in the sequel € stands for set-theoretical membership
relation).

1.1. Let n>1 and [n] : = {1, ···, n}. For any i, j € n let (i,j) :=
n(i-1)+j. Clearly (-,-) is an injective pairing of the type [n]×[n] -> [n²].

1.2. Let «n» := {{(i,j),(k,m)} : i, j, k, m € [n] & j<>m}.

1.3. For any X contained in «n» let Xº contained in «n» be the minimal
closure of X satisfying the following three conditions:
1.3.1) Xº contains X.
1.3.2) if {u,v}, {v,w}, {w,z} € Xº and {u,z} € «n», then {u,z} € Xº.
1.3.3) if {u,v}, {v,w}, {w, u} € Xº, then Xº := «n».

1.4. For any X, Y contained in «n», let X÷Y := X, if X disjont with Y, else
empty.

1.5. Let T be a finite rooted binary-branching tree whose gates are labeled
by AND or OR, and whose every source x is labeled by an element
[iota(x),rho(x)] of the ordinary Cartesian product [2]׫n».
T is called positive iff iota(x)=1 holds true for all sources x.
A set of sources X is called T-conjunctive iff any pair of distinct sources
from X has the closest common ancestor AND.
Maximal T-conjunctive sets of sources are called T-cuts. Denote by S(T) the
set of all T-cuts.
For any X € S(T) and i € [2], let X_i := {rho(x) : x € X & iota(x)=i}.
Set D(T) := {(X_1)º÷X_2 : X € S(T)}.

1.6. Let T ~ T' :<=> (for every X € D(T) there is X' € D(T') such that X
contains X') & (for every X' € D(T') there is X € D(T) such that X' contains
X).

1.7. Denote by Phi_n a positive tree
AND{OR {[1,{(f(i),i),(f(j),j)}] : i<j € [n]} : f ranging over arbitrary
functions of the type [n] -> [n]}.
Notably #(Phi_n) is exponential in n.

1.8. Combinatorial sentence CS :
"For any tree T, as above, T ~ Phi_n fails, provided that n is sufficiently
large and #(T) merely polynomial in n."

2. _Results_

2.1. THEOREM. In Peano Arithmetic, P < NP is derivable from CS.

2.2. NOTE. It is very likely that CS is provable by standard combinatorial
arguments. Now let CSP be the positive restriction of CS :
"For any positive tree T, as above, T ~ Phi_n fails, provided that n is
sufficiently large and #(T) merely polynomial in n."
Preliminary analysis shows that CSP is in fact derivable in Peano
Arithmetic, but a desired proof of CS should be more involved than that of
CSP.

Preprint:
http://www-ls.informatik.uni-tuebingen.de/gordeew/publikationen/Combinatorics.pdf

-------------------------------------------------
L. Gordeev, Tuebingen University,
Germany

gordeew at informatik.uni-tuebingen.de

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

-- 
5 GB Mailbox, 50 FreeSMS http://www.gmx.net/de/go/promail
+++ GMX - die erste Adresse für Mail, Message, More +++