home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2823 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  2.0 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: Suggstion: (was: Re: P=NP; the proof)
  5. Date: 8 Jan 1993 15:34:07 +1100
  6. Organization: Computer Science Department, ANU, Australia
  7. Lines: 36
  8. Distribution: inet
  9. Message-ID: <1ij07vINN2f6@nunki.anu.edu.au>
  10. References: <1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au> <1iicnjINNloe@uwm.edu>
  11. NNTP-Posting-Host: nunki.anu.edu.au
  12. Keywords: Collapse of hierarchy
  13.  
  14. markh@csd4.csd.uwm.edu (Mark) writes:
  15.  
  16. [historical allusions deleted]
  17.  
  18. >When you come up with a P=NP proof, first make sure you can translate it to
  19. >several of the other known NP-complete problems.  Each conversion should lead
  20. >to some significant result and insight if the original proof is correct.
  21. >Also, you'd get far more attention by simultaneously publicising polynomial
  22. >algorithms for 10 to 20 NP-complete problems, and a single tenuous and
  23. >highly abstract proof.  The conversions are in the literature, so it's
  24. >a trivial bookkeeping process to develop 20 algorithms from one.
  25.  
  26. >Second, test the thing out before publicising it, by running the algorithms on
  27. >actual cases and then using these test cases to exemplify the algorithms when
  28. >you do publicise them.
  29.  
  30. >If you're refereeing journals or otherwise trying to determine the validity
  31. >of P=NP proofs, reject all alleged proofs that don't meet the two criteria
  32. >above.
  33.  
  34. Thanks for the suggestion.
  35.  
  36. I've just come up with a fantastic n^12 algorithm for the subset sum
  37. problem which translates into a n^24 algorithm for SAT which gives me
  38. a n^48 algorithm for graph isomorphism. As soon as I have tested this
  39. on a few non trivial pairs of nonisomorphic graphs I'll submit
  40. it to CACM (or whatever journal seesm appropriate in 100993).
  41.  
  42.  
  43. More seriously: we all know about the conversions so why bother
  44. elaborating them. If it turns out that P=NP (I doubt it today),
  45. then it is the fact that matters.
  46.  
  47.  
  48. Mike Robson.
  49.  
  50.