On Tue, 25 Apr 2000, Kai Henningsen wrote:
> > Which is my point. Or did you not read the text you quoted?
>
> If that was your point, you nicely managed to completely obscure it: you
> actually seemed to say the opposite.
Perhaps that's because my argument was of the form "assume the opposite of
what you're trying to prove and show a contradiction". And was sarcastic
to boot. It's all about context (which I made sure to quote).
> > Except simulation _very_ quickly becomes infeasible. But don't take my
> > word for it - try simulating the possible branches of an arbitrary
> > Turing machine with just 4 states. With binary input and a blank tape
> > even.
>
> Umm, "exponential time" *is* equivalent to "quickly becomes infeasible" in
> my book.
My point in the previous post was that it's much worse than exponential
(which you might try to tackle for problems as large as 100 or 1000,
given a small exponent). The complexity grows faster than any computable
function of n.
-- "Love the dolphins," she advised him. "Write by W.A.S.T.E.."- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Sun Apr 30 2000 - 21:00:09 EST