4 ms·
I've edited out "almost", I meant to use it as qualifying the "stumbled upon" part, not the algorithm. In any case by fast polynomial solution I meant one with
by mariorz 17y ago
I've edited out "almost", I meant to use it as qualifying the "stumbled upon" part, not the algorithm.
In any case by fast polynomial solution I meant one with a low degree. Let's assume this algorithm is as fast as existing approximate ones.
- mitko 17y agook then. This shifts the hard part of the problem from "how do I make this run in a lifetime", to "how do I reduce this problem to 3SAT efficiently". This seems to be related: http://en.wikipedia.org/wiki/P_%3D_NP_problem#Consequences_of_proof http://en.wikipedia.org/wiki/P_%3D_NP_problem#Consequences_o...