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.