3 ms·
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 tak
by bodhiandpysics1 4y ago
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.
- bawolff 4y agoYou 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.
- glitchc 4y agoThis 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.