home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2840 < prev    next >
Encoding:
Text File  |  1993-01-08  |  2.0 KB  |  47 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!ames!ads.com!marcel
  3. From: marcel@ADS.COM (Marcel Schoppers)
  4. Subject: Re: Suggstion: (was: Re: P=NP; the proof)
  5. Message-ID: <1993Jan9.001406.24951@ads.com>
  6. Keywords: Collapse of hierarchy
  7. Sender: Marcel Schoppers
  8. Organization: Advanced Decision Systems, Mtn. View, CA (415)960-7300
  9. References: <1ifljqINN137@nunki.anu.edu.au> <1iicnjINNloe@uwm.edu> <1ij07vINN2f6@nunki.anu.edu.au>
  10. Distribution: inet
  11. Date: Sat, 9 Jan 1993 00:14:06 GMT
  12. Lines: 33
  13.  
  14. In article <1ij07vINN2f6@nunki.anu.edu.au> jmr@cs.anu.edu.au (Mike Robson) writes:
  15. >markh@csd4.csd.uwm.edu (Mark) writes:
  16. >>When you come up with a P=NP proof, first make sure you can translate it to
  17. >>several of the other known NP-complete problems.  Each conversion should lead
  18. >>to some significant result and insight if the original proof is correct.
  19. >>Also, you'd get far more attention by simultaneously publicising polynomial
  20. >>algorithms for 10 to 20 NP-complete problems, and a single tenuous and
  21. >>highly abstract proof.  The conversions are in the literature, so it's
  22. >>a trivial bookkeeping process to develop 20 algorithms from one.
  23. >
  24. >>Second, test the thing out before publicising it, by running the algorithms on
  25. >>actual cases and then using these test cases to exemplify the algorithms when
  26. >>you do publicise them.
  27. >
  28. >>If you're refereeing journals or otherwise trying to determine the validity
  29. >>of P=NP proofs, reject all alleged proofs that don't meet the two criteria
  30. >>above.
  31. >>Mark
  32. >
  33. >Thanks for the suggestion.
  34. >
  35. >I've just come up with a fantastic n^12 algorithm for the subset sum
  36. >problem which translates into a n^24 algorithm for SAT which gives me
  37. >a n^48 algorithm for graph isomorphism. As soon as I have tested this
  38. >on a few non trivial pairs of nonisomorphic graphs I'll submit
  39. >it to CACM (or whatever journal seesm appropriate in 100993).
  40. >Mike Robson.
  41.  
  42. Better yet:  I've just come up with a beautiful n^2 algorithm for graph
  43. isomorphism, but the actual execution time is 10^100 * n^2 seconds.
  44. Marcel
  45.  
  46.  
  47.