home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2804 < prev    next >
Encoding:
Internet Message Format  |  1993-01-06  |  2.4 KB
  1. Path: sparky!uunet!utcsri!relay.cs.toronto.edu!neat.cs.toronto.edu!cs.toronto.edu!neto
  2. Newsgroups: comp.theory
  3. From: neto@cs.toronto.edu (David Neto)
  4. Subject: Re: P=NP; the proof
  5. Message-ID: <93Jan6.131544est.47610@neat.cs.toronto.edu>
  6. Organization: Department of Computer Science, University of Toronto
  7. References: <1ht5atINN4iu@nunki.anu.edu.au> <1i3ferINN53m@nunki.anu.edu.au> <1993Jan6.161440.25658@eng.cam.ac.uk>
  8. Distribution: inet
  9. Date: 6 Jan 93 18:16:03 GMT
  10. Lines: 50
  11.  
  12. In article <1993Jan6.161440.25658@eng.cam.ac.uk> ptb@eng.cam.ac.uk (P.T. Breuer) writes:
  13. >jmr@cs.anu.edu.au (Mike Robson) writes:
  14. >> Who can shoot down this alleged proof that P=NP?
  15. >> The ideas are taken from the Gismondi and Swart papers but the
  16. >> algorithms are simplified and the proofs are completely new.
  17. >> If you haven't read their papers, you will probably not follow this.
  18. >> I'll post a more detailed version soon unless anyone has convinced
  19. >> me I'm wrong (in which case I will post a retraction).
  20. >> The following document is in eqn|troff -ms format and is
  21. >> copyright (C) J. M. Robson 1993.
  22. >> [troff omitted]
  23. >
  24. >For my own edification, I translated Mikes document into LaTeX.
  25. >I added some comments to the proofs. I believe Mike made a serious
  26. >mistake in the proof of 2, getting confused over left/right inverses of
  27. >matrices -- the transformational view is much more helpful -- but I
  28. >think I've mended it. Claims 1 and 2 seem to be proved now. I haven't
  29. >checked 3 and 4. Are we getting closer to P=NP?
  30. >
  31.  
  32. I just want to point out a couple of typos.
  33.  
  34. The first typo occurs in the P.T. Breuer's inserted comments in the proof
  35. of Claim 2.
  36. >[text omitted]
  37. >So $S+x\delta S$ solves (\ref{C 1}) for any $x$. By slowly increasing
  38. >the size of $x$ from zero and changing $N$ to $N+\delta N=M(S+x\delta S)$
  39. >[text omitted]
  40.  
  41. I believe the above should read
  42.      "...changing $N$ to $N+\delta N=M^{-1}(S+x\delta S)$".
  43. However, I don't follow his argument this when it is changed in this
  44. way, but that may just be my own problem.
  45.  
  46. The second typo occurs in the proof of Claim 3.
  47. >[text omitted]
  48. >If $B_i =0$, then $T_i A =0$ and clearly also $Q_i A =0$ also
  49. >since the positive elements of $Q_i$ are a subset of those of $A_i$.
  50. >[text omitted]
  51.  
  52. The above should read "... are a subset of those of $T_i$."
  53. Mike Robson's posting had this typo in it as well.  I _do_ follow this
  54. argument when it is changed in this way.
  55.  
  56.  
  57. In any case, this is an interesting development.
  58.  
  59.  
  60. -- David Neto
  61. neto@cs.utoronto.ca
  62.