home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2860 < prev    next >
Encoding:
Internet Message Format  |  1993-01-12  |  1.8 KB
  1. Path: sparky!uunet!digex.com!digex!pcw
  2. From: pcw@access.digex.com (Peter Wayner)
  3. Newsgroups: comp.theory
  4. Subject: Re: Suggstion: (was: Re: P=NP; the proof)
  5. Date: 8 Jan 93 04:51:12 GMT
  6. Organization: Express Access Online Communications, Greenbelt MD USA
  7. Lines: 28
  8. Distribution: inet
  9. Message-ID: <pcw.726468672@digex>
  10. References: <1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au> <1iicnjINNloe@uwm.edu>
  11. NNTP-Posting-Host: access.digex.com
  12. Keywords: Collapse of hierarchy
  13.  
  14. markh@csd4.csd.uwm.edu (Mark) writes:
  15.  
  16.  
  17. >Second, test the thing out before publicising it, by running the algorithms on
  18. >actual cases and then using these test cases to exemplify the algorithms when
  19. >you do publicise them.
  20.  
  21. I believe G+S did this. But this is a difficult experiment to run. "Most"
  22. 3SAT formulas are easy to solve. The tricky ones are excedingly difficult
  23. to find. And if you could find them (and prove you had a method for showing
  24. these were guaranteed to be hard) you might be better off trying to
  25. turn this procedure into a proof that P<>NP. 
  26.  
  27. What if the polynomial was O(n^6)? It would be hard to find data points
  28. for complex cases as n got above 10. How would you know you had O(n^6)
  29. performance and not just exponential time growth with a bit of error
  30. thrown in? 
  31.  
  32. Although I think that every author of a P=NP proof should have a
  33. running version of the algorithm, I still think it is hard to draw
  34. many conclusions from this. It shows that the guy can construct
  35. something that comes close, but it doesn't cut to the mathematical
  36. core of the problem. We already have neat algorithms that get close to
  37. the right answer on NP-complete problems like the travelling salesman.
  38. For all practical intents and realistic purposes, this is enough.It's
  39. really just an academic question now.
  40.  
  41.  
  42.