stable algorithm with complexity O(n)

[Aaron Brady]

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.