[bodhiandpysics1]

Np hard problems aren't that hard to solve. I'm solving one right now actually for work (graph bi-partition using simulated annealing), and it doesn't even take that long. Of course my algorithm isn't actually correct! Or if I had a correct algorithm it might be really fast but still not have polynomial growth. You need a proof.

[glitchc]

This belies a misunderstanding of NP space. Any problem is easy to solve if the dataset being processed is small enough. Computers are wonderful at brute-forcing terrible solutions.

[bawolff]

You need the proof to show it really works in all cases. However if the goal is some quick (non-exhaustive) verification, then why can't you just use the algorithm? (Ignoring the big constants, high degree polynomial issue siblings mention).

Either A, it doesn't work, showing the paper is incorrect. Or B it works, showing that even if it doesn't prove the paper fully correct, it shows that at least something interesting is going on.

[bodhiandphysics]

This algorithm solves all np problems.

For all possible solutions (there are at most 2^p(x) where p is some polynomial), Check if that solution is correct.

This of course takes exponential time. Just because you have an algorithm to solve np problems doesn’t mean you’ve done something useful.

[bawolff]

I mean use it on an instance of the problem big enough that an exponential algorithm would take years and see if the new algorithm doesn't *. Either something interesting will happen or it won't.

* yes i am aware that this falls apart if there is a very high constant or the algo is n^1000.