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

Internet Message Format | 1993-01-07 | 3.9 KB

Path: sparky!uunet!mcsun!uknet!cam-eng!ptb
From: [e-mail] (P.T. Breuer)
Newsgroups: comp.theory
Subject: Re: P=NP; the proof
Summary: the current situation
Keywords: Collapse of hierarchy
Message-ID: <[e-mail]>
Date: 7 Jan 93 12:15:48 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]>
Sender: [e-mail] (Peter T. Breuer)
Distribution: inet
Organization: Cambridge University Engineering Department, England
Lines: 72
Nntp-Posting-Host: tw305.eng.cam.ac.uk

[e-mail] (Mike Robson) writes:
>>[e-mail] (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