🚀 go-pugleaf

In article <1993Jan6.161440.25658@eng.cam.ac.uk> ptb@eng.cam.ac.uk (P.T. Breuer) 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).
>> 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?
>

I just want to point out a couple of typos.

The first typo occurs in the P.T. Breuer's inserted comments in the proof
of Claim 2.
>[text omitted]
>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)$
>[text omitted]

I believe the above should read
	 "...changing $N$ to $N+\delta N=M^{-1}(S+x\delta S)$".
However, I don't follow his argument this when it is changed in this
way, but that may just be my own problem.

The second typo occurs in the proof of Claim 3.
>[text omitted]
>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$.
>[text omitted]

The above should read "... are a subset of those of $T_i$."
Mike Robson's posting had this typo in it as well.  I _do_ follow this
argument when it is changed in this way.


In any case, this is an interesting development.


-- David Neto
neto@cs.utoronto.ca