🚀 go-pugleaf

markh@csd4.csd.uwm.edu (Mark) writes:


>Second, test the thing out before publicising it, by running the algorithms on
>actual cases and then using these test cases to exemplify the algorithms when
>you do publicise them.

I believe G+S did this. But this is a difficult experiment to run. "Most"
3SAT formulas are easy to solve. The tricky ones are excedingly difficult
to find. And if you could find them (and prove you had a method for showing
these were guaranteed to be hard) you might be better off trying to
turn this procedure into a proof that P<>NP. 

What if the polynomial was O(n^6)? It would be hard to find data points
for complex cases as n got above 10. How would you know you had O(n^6)
performance and not just exponential time growth with a bit of error
thrown in? 

Although I think that every author of a P=NP proof should have a
running version of the algorithm, I still think it is hard to draw
many conclusions from this. It shows that the guy can construct
something that comes close, but it doesn't cut to the mathematical
core of the problem. We already have neat algorithms that get close to
the right answer on NP-complete problems like the travelling salesman.
For all practical intents and realistic purposes, this is enough.It's
really just an academic question now.