home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2822 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  1.6 KB
  1. Path: sparky!uunet!paladin.american.edu!gatech!rpi!uwm.edu!csd4.csd.uwm.edu!markh
  2. From: markh@csd4.csd.uwm.edu (Mark)
  3. Newsgroups: comp.theory
  4. Subject: Suggstion: (was: Re: P=NP; the proof)
  5. Date: 7 Jan 1993 23:01:07 GMT
  6. Organization: Computing Services Division, University of Wisconsin - Milwaukee
  7. Lines: 25
  8. Distribution: inet
  9. Message-ID: <1iicnjINNloe@uwm.edu>
  10. References: <1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au>
  11. NNTP-Posting-Host: 129.89.7.4
  12. Keywords: Collapse of hierarchy
  13.  
  14. In article <1ifljqINN137@nunki.anu.edu.au> jmr@cs.anu.edu.au (Mike Robson) writes:
  15. >>So currently my proof is dead but if you believe in resurrection
  16. >>watch this space.
  17. >
  18. >>Mike Robson.
  19. >
  20. >AARRGGHH!!
  21. >
  22. >Jim Reeds has proved that this problem cannot be fixed.
  23.  
  24. When you come up with a P=NP proof, first make sure you can translate it to
  25. several of the other known NP-complete problems.  Each conversion should lead
  26. to some significant result and insight if the original proof is correct.
  27. Also, you'd get far more attention by simultaneously publicising polynomial
  28. algorithms for 10 to 20 NP-complete problems, and a single tenuous and
  29. highly abstract proof.  The conversions are in the literature, so it's
  30. a trivial bookkeeping process to develop 20 algorithms from one.
  31.  
  32. Second, test the thing out before publicising it, by running the algorithms on
  33. actual cases and then using these test cases to exemplify the algorithms when
  34. you do publicise them.
  35.  
  36. If you're refereeing journals or otherwise trying to determine the validity
  37. of P=NP proofs, reject all alleged proofs that don't meet the two criteria
  38. above.
  39.