CDR: Re: Minesweeper and defeating modern encryption technology

dmolnar dmolnar at hcs.harvard.edu
Sun Nov 5 12:44:14 PST 2000



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.






More information about the cypherpunks-legacy mailing list