🚀 go-pugleaf

jmr@cs.anu.edu.au (Mike Robson) writes:
> 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.
> [troff omitted]

For my own edification, I translated Mikes document into LaTeX.
I added some comments to the proofs. I believe Mike made a serious
mistake in the proof of 2, getting confused over left/right inverses of
matrices -- the transformational view is much more helpful -- but I
think I've mended it. Claims 1 and 2 seem to be proved now. I haven't
checked 3 and 4. Are we getting closer to P=NP?


\documentstyle[a4wide]{article}

\title{P=NP}
\author{Mike Robson}
\date{6 January 1993}
% LaTeXified and commented by P.T. Breuer, 6th Jan 1992
% I've checked and agree with claims 1 and 2, but haven't followed through
% 3 and 4 yet. I had to stick a big bracket in claim 2's proof.

\begin{document}
\maketitle


Consider the following linear programming problem $LP$ in variables
$s_{a,b}$ and $t_{a,b,c,d}$ for $a$, $b$, $c$ and
$d$ integers from $1$ to $n$, $a \ne c$ and $b \ne d$:

\begin{equation}\label{C 1}
   \sum\limits_a s_{a,b} ~=~ 1 ~=~ \sum\limits_b s_{a,b}
\end{equation}
\begin{equation}\label{C 2}
   \sum\limits_a t_{a,b,c,d} ~=~ s_{c,d} ~=~ \sum\limits_b t_{a,b,c,d}
\end{equation}
\begin{equation}\label{C 3}
   \sum\limits_c t_{a,b,c,d} ~=~ s_{a,b} ~=~ \sum\limits_d t_{a,b,c,d}
\end{equation}
\begin{equation}\label{C 4}
   t_{a,b,c,d} ~ \ge ~ 0.
\end{equation}

Define a permutation vector $Q_\pi$ for any permutation $\pi$ as the
solution to $LP$ which has $s_{a,b} = 1$ wherever $\pi a = b$,
$t_{a,b,c,d} =1$ wherever $\pi a = b$ and $\pi c =d$ and all other
$s$ and $t$ variables zero.


\bigskip\noindent
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_\pi$ for some $\pi$.

\bigskip\noindent
Proof: The $s$ variables define a permutation $\pi$ such that $\pi a =b$
iff $s_{a,b} =1$.
Suppose that $t_{a,b,c,d} > 0$; then $s_{a,b}$ and $s_{c,d}$ are both
positive by the equalities (\ref{C 2}) and (\ref{C 3}) and so are both equal to 1; no [other] $d'$
can have $t_{a,b,c,d'} >0$ [else $s_{c,d'}=1$ by the same argument,
contradicting (\ref{C 1})], so $t_{a,b,c,d} = s_{a,b} = 1$;
hence $T$ has $t$ variables equal to 1 wherever $Q_\pi$ does and it cannot
have more positive elements [by counting 1's on both sides in (\ref{C 1})
for the $s$ variables, and then by the same method using (\ref{C 2}) and
(\ref{C 3}) for the $t$s].


\bigskip\noindent
Claim 2: If T is a solution to $LP$, it covers a permutation vector
$Q_\pi$ [`covers' means that its nonzero variables are
a superset of $Q_\pi$'s].

\bigskip\noindent
Proof: Define $T'$ 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'$ 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'$ are not all zero or 1
and derive a contradiction; the result then follows by claim 1.

Let the nonzero $t$ variables of $T'$ be the set $N$
[with elements $N_1,\dots,N_{\#N}$]. Deleting
the other variables from the equations (\ref{C 2}) and (\ref{C 3}) and discarding those
corresponding to zero $s_{a,b}$s, we obtain a number of
equations of the form
\[N_{i_1} + N_{i_2} + ... ~=~ s_{a,b}\]
This can be written as a matrix equation:
\begin{equation}\label{C 5}
MN ~=~ S.
\end{equation}
[$N$ is a vector, $S$ is a vector, $M$ is a matrix]
Note from (\ref{C 3}) that to every nonzero $s_{a,b}$ there corresponds at least
one nonzero $t_{a,b,c,d}$ so that $M$ has at least as many columns as rows
[so it's a map from a low dimension space into a high dimension space].
Either $M$ has a left inverse $M^{-1}$ or not [more properly, either
$M$ is injective or it is not. If it is injective then there is a
post-transformation that will undo its action: a left inverse].

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'$ and satisfies
all the constraints except possibly the positivity constraints (\ref{C 4}).
Increasing $x$ gradually from $0$ until the first such constraint is about to
fail gives a new solution covered by $T'$ and with (at least)
one more zero, in contradiction to the definition of $T'$.

If $M$ has a left inverse $M^{-1}$, then by the remark on the dimensions
of $M$, it must be that $M$ is in fact square [I don't see this. It can
have more columns than rows, surely? But never mind, the argument works
so long as $S$ is continuously 1-1 related to $N$ through $M$ in this
situation, and it is. Go as follows: write out the $2n$ equations of
(\ref{C 1}) as though only in the at least $2n$ nonzero $s$ variables of
$T'$. If there are exactly $2n$ nonzero $s$ variables, then we are looking
at a permutation vector, by Claim 1, and done. So there are more than $2n$
and the system has a nontrivial kernel, containing, say, $\delta S \ne[0]$.
So $S+x\delta S$ solves (\ref{C 1}) for any $x$. By slowly increasing
the size of $x$ from zero and changing $N$ to $N+\delta N=M(S+x\delta S)$
until the first positivity constraint (\ref{C 4}) is hit,
then we have set an extra $t$ variable to zero, and are done.]
so that $M^{-1}$ is also a right inverse. We can rewrite the equation for $S$
as $N = M^{-1} S$; now by continuously modifying $S$ so as to retain
all the zero $s$ variables of $T'$, we again get solutions to
$LP$ (by combining the modified $S$ with the $t$ variables obtained
by computing $N ~=~ M^{-1} S$ which must satisfy $MN=S$ and keeping the
remaining $t$s equal to $0$)
which are covered by $T'$ and eventually we get one with an extra
zero variable, again contradicting the definition of $T'$.

[The following argument of Mike's is nonsense, because he doesn't
consider what happens to cycles coming off the main cycle]
{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_{a,b}$ must have at least one matching $ s_{a' ,b}$
and one $ s_{a, b'}$; join these to
$s_{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.}

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

\bigskip\noindent
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$.

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


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

\bigskip\noindent
Corollary: Hamiltonian Circuit is in $P$.

\bigskip\noindent
Proof: As in [Gismondi and Swart].

\bigskip\noindent
Theorem: P=NP.

\bigskip\noindent
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.

\end{document}