4 ms·
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 algori
by bawolff 4y ago
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 4y agoThis 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 4y agoI 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.