stable algorithm with complexity O(n)
Aaron Brady
castironpi at gmail.com
Mon Dec 15 01:19:32 CET 2008
On Dec 14, 6:04 pm, greg <g... at cosc.canterbury.ac.nz> wrote:
> 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.
It's more likely you'd circumvent the assumptions. That is, find an
'outside-the-box' solution. For instance, a deeply parallel
architecture could escape the assumption that you can only compare two
numbers at a time (per step).
The proof's conclusion is still true if its assumption is.
More information about the Python-list
mailing list