home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2812 < prev    next >
Encoding:
Internet Message Format  |  1993-01-06  |  1.6 KB
  1. Path: sparky!uunet!munnari.oz.au!manuel.anu.edu.au!dubhe.anu.edu.au!nunki.anu.edu.au!not-for-mail
  2. From: jmr@cs.anu.edu.au (Mike Robson)
  3. Newsgroups: comp.theory
  4. Subject: Re: P=NP; the proof
  5. Date: 7 Jan 1993 09:14:17 +1100
  6. Organization: Computer Science Department, ANU, Australia
  7. Lines: 31
  8. Distribution: inet
  9. Message-ID: <1ifljqINN137@nunki.anu.edu.au>
  10. References: <1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au>
  11. NNTP-Posting-Host: nunki.anu.edu.au
  12. Keywords: Collapse of hierarchy
  13.  
  14. jmr@cs.anu.edu.au (Mike Robson) writes:
  15.  
  16. >jmr@cs.anu.edu.au (Mike Robson) writes:
  17.  
  18.  
  19. >>Who can shoot down this alleged proof that P=NP?
  20. >>The ideas are taken from the Gismondi and Swart papers but the
  21. >>algorithms are simplified and the proofs are completely new.
  22. >>If you haven't read their papers, you will probably not follow this.
  23. >>I'll post a more detailed version soon unless anyone has convinced
  24. >>me I'm wrong (in which case I will post a retraction).
  25.  
  26. >I was wrong about the dimensions of the matrix M since it has more
  27. >rows than the number of nonzero sab. I can't see any way to fix this
  28. >(though I am working on it). I've had mail from Peter Breuer of
  29. >Cambridge who says he has found a fix. I am looking forward to hearing
  30. >from him what it is.
  31.  
  32. >So currently my proof is dead but if you believe in resurrection
  33. >watch this space.
  34.  
  35. >Mike Robson.
  36.  
  37. AARRGGHH!!
  38.  
  39. Jim Reeds has proved that this problem cannot be fixed.
  40. I'll go back to trying to decide if the current Gismondi and Swart
  41. linear programming formulation has the required property (that every
  42. solution covers a permutation). If that claim is true, then I think
  43. my approach is a good way to try and prove it.
  44.  
  45.