[OT] stable algorithm with complexity O(n)

greg greg at cosc.canterbury.ac.nz
Mon Dec 15 01:04:00 CET 2008


Lie Ryan wrote:
> "You know what you just did? You've 
> just found a problem that was supposed to be an example of unsolvable 
> problem."
> 
> It has happened before, why not again?

There's a big difference between an unsolvable problem and an
unsolved problem. In the cases you're talking about, nobody
had solved the problem before, but neither had anybody proved
there was no solution.

In the case at hand, there is a proof that such an algorithm
is impossible. Overturning that would require finding a
flaw in the proof, which for such a simple proof seems very
unlikely.

That's not to say nobody should try, but I won't be holding
my breath.

-- 
Greg



More information about the Python-list mailing list