Thread View: comp.theory
12 messages
12 total messages
Started by Mike Robson
Wed, 06 Jan 1993 05:34
P=NP; the proof
Author: Mike Robson
Date: Wed, 06 Jan 1993 05:34
Date: Wed, 06 Jan 1993 05:34
144 lines
6668 bytes
6668 bytes
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.
Re: P=NP; the proof
Author: Mike Robson
Date: Wed, 06 Jan 1993 19:42
Date: Wed, 06 Jan 1993 19:42
20 lines
1287 bytes
1287 bytes
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). I was wrong about the dimensions of the matrix M since it has more rows than the number of nonzero sab. I can't see any way to fix this (though I am working on it). I've had mail from Peter Breuer of Cambridge who says he has found a fix. I am looking forward to hearing from him what it is. So currently my proof is dead but if you believe in resurrection watch this space. Mike Robson.
Re: P=NP; the proof
Author: Mike Robson
Date: Wed, 06 Jan 1993 22:14
Date: Wed, 06 Jan 1993 22:14
30 lines
1718 bytes
1718 bytes
jmr@cs.anu.edu.au (Mike Robson) writes: >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). >I was wrong about the dimensions of the matrix M since it has more >rows than the number of nonzero sab. I can't see any way to fix this >(though I am working on it). I've had mail from Peter Breuer of >Cambridge who says he has found a fix. I am looking forward to hearing >from him what it is. >So currently my proof is dead but if you believe in resurrection >watch this space. >Mike Robson. AARRGGHH!! Jim Reeds has proved that this problem cannot be fixed. I'll go back to trying to decide if the current Gismondi and Swart linear programming formulation has the required property (that every solution covers a permutation). If that claim is true, then I think my approach is a good way to try and prove it.
Re: P=NP; the proof
Author: Jim Reeds
Date: Wed, 06 Jan 1993 22:40
Date: Wed, 06 Jan 1993 22:40
19 lines
1226 bytes
1226 bytes
Mike Robson writes > Who can shoot down this alleged proof that P=NP? [...] > Claim 2: If T is a solution to $LP$, it covers a permutation vector > $Q sub pi$. Maybe I can. The T matrix displayed in section 3 of Gismondi and Swart's isomorphism paper (sept 1992) covers no permutation vector. (There are only 24, so you can check by brute force, if you want.) Claim 2, if true, would imply that the feasible region for Robson's linear programming problem had precisely the set of permutation vectors as its extreme points. This is clearly out of step with the discussion in G&S section 3. I think G&S introduce their whole rigamarole of U vectors and actions of permutations on triples of symbols to get around this problem.
Re: P=NP; the proof
Author: P.T. Breuer
Date: Thu, 07 Jan 1993 12:15
Date: Thu, 07 Jan 1993 12:15
72 lines
4103 bytes
4103 bytes
jmr@cs.anu.edu.au (Mike Robson) writes:
>>jmr@cs.anu.edu.au (Mike Robson) writes:
>>>Who can shoot down this alleged proof that P=NP?
[etc.]
>>I was wrong about the dimensions of the matrix M since it has more
>>rows than the number of nonzero sab. I can't see any way to fix this
>>(though I am working on it). I've had mail from Peter Breuer of
>>Cambridge who says he has found a fix. I am looking forward to hearing
>>from him what it is.
>
>>So currently my proof is dead but if you believe in resurrection
>>watch this space.
>
>>Mike Robson.
>
>AARRGGHH!!
>
>Jim Reeds has proved that this problem cannot be fixed.
Indeed, Jim Reeds has notified us of a consequence of Mike's Claim 2
which contradicts a fact (this is known as `no problem' in the police
jargon!). So it's not surprising that attempts to prove it run into
difficulty somewhere.
But the claim is really just a touch to strong; one could modify
it by strengthening the hypotheses to rule out the exceptional
situation that fouls up the proofs, and carry the hypotheses around
until one can get rid of them in some other way. So it's not a hopeless
direction to try.
My patch went like this: we're looking at the situation where MN=S is
what the equations really `say'. The S are a vector of some s_{a,b},
and the N is a vector of some of the t_{a,b,c,d}. Maybe all.
[M is a matrix of 1's and zeros. The system is got by looking at the linear
programming problem when we have a solution T' covered by a T we began
with, and we've chosen T' to have as many 0's as possible. The N
consists of those variables in T which are non-zero. We're trying
to modify it to have just one more zero, which would be a
contradiction. We're also supposing that some of the s variables are
neither zero nor 1, so that's what gets contradicted, and then we can
use Claim 1, to conclude that we're looking at a permutation.]
Mike's argument was correct for the case when M has a nontrivial
kernel. When it's injective, however, then it has a left inverse,
M^{-1}. I pointed out that we might be able to wriggle S a little bit while
preserving the constraints (1). Then M(N+dN)= S+dS determines dN, which
cannot be zero since M is injective. Note that dS must be in the kernel of
the system (1), so we can wriggle it a _lot_ if required. All we do is
choose dS just large enough to make dN just large enough to touch one
more of the inequalities (4). That kills one more t. As required. Note
that it's not ipso facto clear that the dN will necessarily be the right
shape to impact on (4), though I don't see how not.
My patch broke down when trying to prove that dS existed. But Mike has
since written to me with an expanded proof of the paragraph I rather
rubbished in his original, about altering all the s_{a,b} by +epsilon
or -epsilon according to where they lay in a `cycle' got by a
particular means. This argument now looks cast iron to me (go back to
Mike's post to see if you can follow it, or ask Mike for the expanded
version), so I conclude that dS does exist. My patch therefore comes
back to life, modulo the note at the end of the last paragraph.
But Jim Reed's argument (contact him or Mike for details, please, not
me) shows that Claim 2 is invalid. So it must be that, incredibly, the
dN=MdS generated by Mike's construction don't have any component in any
of the nonzero t's. Since N consists exactly of the nonzero t's, I
don't know whattinhell is going on.
Any ideas?
Peter
Re: P=NP; the proof
Author: Jim Reeds
Date: Thu, 07 Jan 1993 16:00
Date: Thu, 07 Jan 1993 16:00
22 lines
1538 bytes
1538 bytes
jmr@cs.anu.edu.au (Mike Robson) writes: >[...] >I'll go back to trying to decide if the current Gismondi and Swart >linear programming formulation has the required property (that every >solution covers a permutation). If that claim is true, then I think >my approach is a good way to try and prove it. This is rather more than G&S themselves state. If every point in the feasible region covers a permutation, then the extreme points of the feasible region are exactly the permutations, and hence every point in the feasible region is expressible as a convex combination of permutations. But all G&S claim is that any solution is expresible as an affine combination of permutations, with AT MOST ONE NEGATIVE COEFFICIENT. (I would like to see a real proof that any solution is expressible as an affine combination of permutations, regardless of sign. Equivalently, I'd like to know the dimension of the affine hull of the G&S feasible region.) Jim
Suggstion: (was: Re: P=NP; the proof)
Author: Mark
Date: Thu, 07 Jan 1993 23:01
Date: Thu, 07 Jan 1993 23:01
25 lines
1681 bytes
1681 bytes
In article <1ifljqINN137@nunki.anu.edu.au> jmr@cs.anu.edu.au (Mike Robson) writes: >>So currently my proof is dead but if you believe in resurrection >>watch this space. > >>Mike Robson. > >AARRGGHH!! > >Jim Reeds has proved that this problem cannot be fixed. When you come up with a P=NP proof, first make sure you can translate it to several of the other known NP-complete problems. Each conversion should lead to some significant result and insight if the original proof is correct. Also, you'd get far more attention by simultaneously publicising polynomial algorithms for 10 to 20 NP-complete problems, and a single tenuous and highly abstract proof. The conversions are in the literature, so it's a trivial bookkeeping process to develop 20 algorithms from one. Second, test the thing out before publicising it, by running the algorithms on actual cases and then using these test cases to exemplify the algorithms when you do publicise them. If you're refereeing journals or otherwise trying to determine the validity of P=NP proofs, reject all alleged proofs that don't meet the two criteria above.
Re: Suggstion: (was: Re: P=NP; the proof)
Author: Mike Robson
Date: Fri, 08 Jan 1993 04:34
Date: Fri, 08 Jan 1993 04:34
35 lines
2097 bytes
2097 bytes
markh@csd4.csd.uwm.edu (Mark) writes: [historical allusions deleted] >When you come up with a P=NP proof, first make sure you can translate it to >several of the other known NP-complete problems. Each conversion should lead >to some significant result and insight if the original proof is correct. >Also, you'd get far more attention by simultaneously publicising polynomial >algorithms for 10 to 20 NP-complete problems, and a single tenuous and >highly abstract proof. The conversions are in the literature, so it's >a trivial bookkeeping process to develop 20 algorithms from one. >Second, test the thing out before publicising it, by running the algorithms on >actual cases and then using these test cases to exemplify the algorithms when >you do publicise them. >If you're refereeing journals or otherwise trying to determine the validity >of P=NP proofs, reject all alleged proofs that don't meet the two criteria >above. Thanks for the suggestion. I've just come up with a fantastic n^12 algorithm for the subset sum problem which translates into a n^24 algorithm for SAT which gives me a n^48 algorithm for graph isomorphism. As soon as I have tested this on a few non trivial pairs of nonisomorphic graphs I'll submit it to CACM (or whatever journal seesm appropriate in 100993). More seriously: we all know about the conversions so why bother elaborating them. If it turns out that P=NP (I doubt it today), then it is the fact that matters. Mike Robson.
Re: Suggstion: (was: Re: P=NP; the proof)
Author: Peter Wayner
Date: Fri, 08 Jan 1993 04:51
Date: Fri, 08 Jan 1993 04:51
26 lines
1855 bytes
1855 bytes
markh@csd4.csd.uwm.edu (Mark) writes: >Second, test the thing out before publicising it, by running the algorithms on >actual cases and then using these test cases to exemplify the algorithms when >you do publicise them. I believe G+S did this. But this is a difficult experiment to run. "Most" 3SAT formulas are easy to solve. The tricky ones are excedingly difficult to find. And if you could find them (and prove you had a method for showing these were guaranteed to be hard) you might be better off trying to turn this procedure into a proof that P<>NP. What if the polynomial was O(n^6)? It would be hard to find data points for complex cases as n got above 10. How would you know you had O(n^6) performance and not just exponential time growth with a bit of error thrown in? Although I think that every author of a P=NP proof should have a running version of the algorithm, I still think it is hard to draw many conclusions from this. It shows that the guy can construct something that comes close, but it doesn't cut to the mathematical core of the problem. We already have neat algorithms that get close to the right answer on NP-complete problems like the travelling salesman. For all practical intents and realistic purposes, this is enough.It's really just an academic question now.
Re: P=NP; the proof
Author: Mike Robson
Date: Fri, 08 Jan 1993 05:22
Date: Fri, 08 Jan 1993 05:22
42 lines
2344 bytes
2344 bytes
reeds@alice.att.com (Jim Reeds) writes: >jmr@cs.anu.edu.au (Mike Robson) writes: >>[...] >>I'll go back to trying to decide if the current Gismondi and Swart >>linear programming formulation has the required property (that every >>solution covers a permutation). If that claim is true, then I think >>my approach is a good way to try and prove it. >This is rather more than G&S themselves state. If every point in the >feasible region covers a permutation, then the extreme points of the >feasible region are exactly the permutations, and hence every point in >the feasible region is expressible as a convex combination of permutations. I should have been more precise. I think they are claiming that every solution has covers the s and t variables of a permutation (not the u). I think that gets round your argument; if not things look bad. >But all G&S claim is that any solution is expresible as an affine >combination of permutations, with AT MOST ONE NEGATIVE COEFFICIENT. Where did they claim that? >(I would like to see a real proof that any solution is expressible >as an affine combination of permutations, regardless of sign. Equivalently, >I'd like to know the dimension of the affine hull of the G&S feasible >region.) They claim to have a complete proof based on the dimensions of the spaces involved but I haven't seen any details. I have an idea of how to construct a proof by taking an arbitrary solution and systematically zeroing out all u variables except those of the identity permutation vector. This can be done by subtracting carefully chosen permutations, possibly preceded by adding other permutations which don't involve any u variables except the ones which you haven't got round to yet. >Jim Mike.
Re: Suggstion: (was: Re: P=NP; the proof)
Author: Gordon Royle
Date: Tue, 12 Jan 1993 07:24
Date: Tue, 12 Jan 1993 07:24
17 lines
1326 bytes
1326 bytes
In <pcw.726468672@digex> pcw@access.digex.com (Peter Wayner) writes: >core of the problem. We already have neat algorithms that get close to >the right answer on NP-complete problems like the travelling salesman. >For all practical intents and realistic purposes, this is enough.It's >really just an academic question now. Is this true? I am not aware of any decent algorithms for Travelling Salesman at all. In fact G&J show that there cannot be any polynomial time approximation algorithms for Travelling Salesman that achieve ANY given multiple of the optimal solution (page 147). Does this not contradict the above statement, or am I labouring under a delusion? Gordon
Re: Suggstion: (was: Re: P=NP; the proof)
Author: Claude Diderich
Date: Tue, 12 Jan 1993 12:53
Date: Tue, 12 Jan 1993 12:53
39 lines
2608 bytes
2608 bytes
In article <gordon.726823495@ningaui>, gordon@cs.uwa.oz.au (Gordon Royle) writes: > In <pcw.726468672@digex> pcw@access.digex.com (Peter Wayner) writes: > > >core of the problem. We already have neat algorithms that get close to > >the right answer on NP-complete problems like the travelling salesman. > >For all practical intents and realistic purposes, this is enough.It's > >really just an academic question now. > > > Is this true? I am not aware of any decent algorithms for Travelling > Salesman at all. In fact G&J show that there cannot be any polynomial > time approximation algorithms for Travelling Salesman that achieve > ANY given multiple of the optimal solution (page 147). > Does this not contradict the above statement, or am I labouring under a > delusion? > > > Gordon Peter Wayer's statement is not true. We do have algorithms that give in general good solutions for the TSP, but we cannot say anything about the quality in general of any solution produced. Indeed such algorithms may in 95% of the cases approach the optimal solution by 90%. But we cannot guarantee 100% of the cases. Furthermore, we do not have any possibility to check if a given solution is within the 95% of good solutions or not. But TSP is not the only NP-complete problem. There are other problems like Max Clique that even cannot be approximated within any constant, e.g. approxiating is as hard as solving. Therefore I think the P?=NP question is not ony of theoretical interesed. Claude --------------------------------------------------------------------------- Claude G. Diderich Internet: diderich@di.epfl.ch 30, Avenue S.Reymondin -- CH-1009 Pully (VD) -- Switzerland -- Europe ``Imagination is more important than knowledge'' Albert Einstein ---------------------------------------------------------------------------
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads