4 ms·
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. Th
by bodhiandphysics 4y ago
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 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.