On Sun, 5 Nov 2000, Jim Choate wrote:
On Sat, 4 Nov 2000, Bill Stewart wrote:
No - it gives you a direct solution that takes exponential time, because there are exponentially many answers the thing could guess, each of which takes a polynomial time to validate. The "then a miracle occurs" step is that the NTM guesses the _correct_ answer - that's why it's hypothetical, rather than real.
There is no guarantee that a NDTM will guess the correct answer at any stage. The question the NDTM answers over a DTM is "Is there a statistical algorithm that is more efficient than a deterministic one?".
Um, the definition of "nondeterministic Turing machine" implies such a guarantee. You seem to be thinking of a probabilistic Turing machine - a machine which can flip coins and use the results in an algorithm. They are **not** the same thing.