CDR: Re: Minesweeper and defeating modern encryption technology

[Bill Stewart]

At 06:04 PM 11/5/00 -0600, Jim Choate wrote:
>
>On Sun, 5 Nov 2000, dmolnar wrote:
>
>> > 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.
>???
>
>A NDTM has a stage which if given correct input will cause the result to
>have one of several states (e.g. A Turing machine that holds both roots of
>a quadratic at the same time). However, we're right back to 'provably
>correct' which can't occur, even in principle because there are some
>legitimate input states that can't be resolved as 'correct'. I wasn't the
>one who injected 'guessing' in there (which a NDTM doesn't do, ever. It
>takes the next state only after a 'proof of correctness' step.). When
>the 'guess' factor is injected then you get a probabilistic NDTM. Which is
>what I was addressing.

Dave's right, Jim.  The NDTM obtains The Right Answer by using a process
you could call "guessing" or you could call "an oracle".  That's not
"Oracle" like "Larry Ellison telling you what you WILL buy next", it's
"Oracle" like "Stoned priestess telling you that if you attack today,
a great kingdom will fall", and the polynomial-time part is where
you crank that through and find out that yes, it's correct.
(Unfortunately it's *your* kingdom, but it's correct.)  

The reason the NDTM is hypothetical is because always guessing the
right answer isn't a technology that's really available,
unless quantum computers can do that with a sufficently useful precision.
(Looks like QCs will at best guess the right answer some of the time,
not all the time, and you'll still have to check it.)

>In addition a NDTM has little worth in a world where we postulate all
>possible Boolean sentences are resolvable. It, after all, allows a state
>to be both 1 and 0, clearly contrary to our assertion. What one would want
>is to show that a DTM was all that is required to resolve any of those
>Boolean equations. Which can't be done if we accept the NDTM <-> DTM proof.

The NDTM doesn't allow the state to be both 0 and 1, it tells you which.
The DTM part verifies that the answer from the oracle is correct,
even though obtained by non-deterministic magic.
 


				Thanks! 
					Bill
Bill Stewart, bill.stewart at pobox.com
PGP Fingerprint D454 E202 CBC8 40BF  3C85 B884 0ABE 4639