NetNews Usenet Archive 1993 #1/NN_1993_1.iso/spool/comp/theory/2799

Internet Message Format | 1993-01-06 | 6.4 KB

Path: sparky!uunet!munnari.oz.au!manuel.anu.edu.au!dubhe.anu.edu.au!nunki.anu.edu.au!not-for-mail
From: [e-mail] (Mike Robson)
Newsgroups: comp.theory
Subject: P=NP; the proof
Date: 6 Jan 1993 16:34:47 +1100
Organization: Computer Science Department, ANU, Australia
Lines: 146
Distribution: inet
Message-ID: <[e-mail]>
NNTP-Posting-Host: nunki.anu.edu.au
Summary: Modification of the Gismondi Swart algorithm is easy to prove correct
Keywords: Collapse of hierarchy


Who can shoot down this alleged proof that P=NP?
The ideas are taken from the Gismondi and Swart papers but the
algorithms are simplified and the proofs are completely new.
If you haven't read their papers, you will probably not follow this.
I'll post a more detailed version soon unless anyone has convinced
me I'm wrong (in which case I will post a retraction).
The following document is in eqn|troff -ms format and is
copyright (C) J. M. Robson 1993.

-----------------------------------------------------------------------


.ce 3

.EQ
delim $$
.EN
P=NP
Mike Robson
6 January 1993


Consider the following linear programming problem $LP$ in variables
$s sub {a,b}$ and $t sub {a,b,c,d}$ for $a$, $b$, $c$ and
$d$ integers from $1$ to $n$, $a != c$ and $b != d$:

.EQ C 1
   sum from a s sub {a,b} ~=~ 1 ~=~ sum from b s sub {a,b}
.EN
.EQ C 2
   sum from a t sub {a,b,c,d} ~=~ s sub {c,d} ~=~ sum from b t sub {a,b,c,d}
.EN
.EQ C 3
   sum from c t sub {a,b,c,d} ~=~ s sub {a,b} ~=~ sum from d t sub {a,b,c,d}
.EN
.EQ C 4
   t sub {a,b,c,d} ~ >= ~ 0.
.EN

Define a permutation vector $Q sub pi$ for any permutation $pi$ as the
solution to $LP$ which has $s sub a,b = 1$ wherever $pi a = b$,
$t sub a,b,c,d =1$ wherever $pi a = b$ and $pi c =d$ and all other
$s$ and $t$ variables zero.


Claim 1: If $T$ is a solution to $LP$ with all its $s$ variables equal
to 0 or 1, then $T$ is the permutation vector $Q sub pi$ for some $pi$.

Proof: The $s$ variables define a permutation $pi$ such that $pi a =b$
iff $s sub a,b =1$.
Suppose that $t sub a,b,c,d > 0$; then $s sub a,b$ and $s sub c,d$ are both
positive by the equalities (2) and (3) and so are both equal to 1; no $d prime$
can have $t sub {a,b,c,d prime} >0$, so $t sub a,b,c,d = s sub a,b = 1$;
hence $T$ has $t$ variables equal to 1 wherever $Q sub pi$ does and it cannot
have more positive elements.


Claim 2: If T is a solution to $LP$, it covers a permutation vector
$Q sub pi$.

Proof: Define $T prime$ to be a solution to $LP$ which is covered
by $T$ and does not cover any other such solution with more zero $t$ variables
(i.e. $T prime$ is a solution covered by $T$ maximal among these solutions
w.r.t the number of zero $t$ variables).
We will suppose that the $s$ variables of $T prime$ are not all zero or 1
and derive a contradiction; the result then follows by claim 1.

Let the non zero $t$ variables of $T prime$ be the set $N$. Deleting
the other variables from the equations (2) and (3) and discarding those
corresponding to zero $s sub a,b$s, we obtain a number of
equations of the form
.ce
$N sub {i sub 1} + N sub {i sub 2} + ... ~=~ s sub a,b$.
This can be written as a matrix equation:
.EQ C 5
MN ~=~ S.
.EN
Note from (3) that to every nonzero $s sub a,b$ there corresponds at least
one nonzero $t sub a,b,c,d$ so that $M$ has at least as many columns as rows.
Either $M$ has a left inverse $M sup -1$ or not.

If $M$ has no left inverse, there is a vector $delta N$ of the same dimension
as $N$ such that $M delta N =[0]$; any sum $N + x delta N$ gives a potential
solution to $LP$ which has all the zero variables of $T prime$ and satisfies
all the constraints except possibly the positivity constraints (4).
Increasing $x$ gradually from $0$ until the first such constraint is about to
fail gives a new solution covered by $T prime$ and with (at least)
one more zero, in contradiction to the definition of $T prime$.

If $M$ has a left inverse $M sup -1$, then by the remark on the dimensions
of $M$, it must be that $M$ is in fact square so that $M sup -1$
is also a right inverse. We can rewrite the equation for $S$
as $N = M sup -1 S$; now by continuously modifying $S$ so as to retain
all the zero $s$ variables of $T prime$, we again get solutions to
$LP$ (by combining the modified $S$ with the $t$ variables obtained
by computing $N ~=~ M sup -1 S$ which must satisfy $MN=S$ and keeping the
remaining $t$s equal to $0$)
which are covered by $T prime$ and eventually we get one with an extra
zero variable, again contradicting the definition of $T prime$.

{To see that the $s$ variables can indeed be modified in this way,
consider the $s$ variables which are neither $0$ nor $1$;
any such $s sub a,b$ must have at least one matching $ s sub {a prime ,b}$
and one $ s sub {a, b prime}$; join these to
$s sub a,b$ by edges to give a graph $G$;
$G$ must contain a cycle with alternating `horizontal' and `vertical'
edges; add $epsilon$ or $- epsilon$ to the vertices along this cycle
alternately to modify the $s$ variables in the required way.}


Now we regard the variables $t$ as constituting a square matrix
with subscripts taken from the pairs $a,c$ ($a != c$) or $b,d$ with $b != d$.

Claim 3: If T is a solution to $LP$ and covers a permutation vector
$Q$, and $A$ and $B$ are
vectors with all elements $0$ or $1$, if $TA=B$ then $QA=B$.

Proof: Consider an element $B sub i$ of $B$ and note that $B sub i = T sub i A$
(where $T sub i$ is the $i$th row of $T$, namely a vector with
non-negative elements whose sum is $1$).
If $B sub i =0$, then $T sub i A =0$ and clearly also $Q sub i A =0$ also
since the positive elements of $Q sub i$ are a subset of those of $A sub i$.
If $B sub i = 1$, Then $A$ must have element $A sub j$ equal to $1$ wherever
$T sub i,j$ is nonzero; but $Q sub i$ has exactly one nonzero element, a
$Q sub i,j$ which is equal to $1$ for a $j$ such that $T sub i,j$ is
positive; hence $ Q sub i A = 1$.


Remark: The same analysis holds if we restrict our attention to two
submatrices $T tilde$ and $Q tilde$ obtained by deleting certain rows
from both $T$ and $Q$.

Corollary: Hamiltonian Circuit is in $P$.

Proof: As in [Gismondi and Swart].

Theorem: P=NP.

Remark: This proves that the various Gismondi and Swart algorithms are
correct since their sets of constraints are supersets of the ones
used here and are certainly satisfied by the permutation vectors.
I claim that this is the first valid proof of P=NP and that the
algorithms implied by this proof are much simpler than theirs.