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@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639