Re: Nondeterministic turing machines.

On Mon, 17 Apr 2006 19:35:24 -0700, Vinod wrote:

Many books define nondeterministic turing machines as those which have
the power of guessing the answer and verifying the answer in polynomial
time. Some say that they are given a certificate, using which they
verify the answer to a problem in polynomial time. Still others define
them to have witness strings which are similar to the certificates
using which the NDTM can verify the solution to a problem in polynomial
time.

Can someone give me a good intuition for the above definitions,
especially those based on "guessing" and "certificates"?

I will make a try.

As per one of a number of equivalent definitions, a nondeterministic
Turing Machine (NDTM) is a Turing Machine (TM) that has a finite number
of choices of next move at each step. That is, from a given
configuration (current state and tape symbol currently under the tape
head), an NDTM can make _one of a finite number_ of moves. A move
results in the following:

1. A change of state.
2. The symbol under the tape head being overwritten with another.
3. The tape head being moved left or right.

Any or all three of the above may be identity transformations, where the
new state is the same as the original one, etc. Also, for some
configurations, there may be no next move defined.

In contrast, in a deterministic TM, there can be _at most one_ move from
each configuration.

Also note that the set of possible moves from each configuration is
fixed, as part of the definition of each NDTM : it is not the case that
an NDTM can make _any_ move whatsoever from a given configuration -- it
has to choose from one of the finite number of allowed moves in its
definition.

The NDTM is said to accept an input string if, when started with the
string placed on the input tape starting at the leftmost position, and
with nothing else (except blanks) on the tape, and the tape head placed
on the first symbol of the input string,

there is _some_ sequence of moves such that the NDTM reaches a final
state.

Note that since the NDTM has, in general, a choice of moves from each
configuration, there may be _many distinct sequences_ of moves that it
can make for a given input string. The NDTM is said to accept the string
if _at least one_ of these sequences ends in a final state.

In contrast, a deterministic TM has exactly one sequence of moves for
a given input string, and it is said to accept the string if this
sequence ends in a final state.

So, an NDTM does not accept a string only if _none_ of the different move
sequences results in a final state. Otherwise it is accepts the string.

Note that this definition of acceptance by the NDTM does not involve the
notion of _actually_ "running" the NDTM on the input in all possible ways
-- there only has to be at least one way in which the NDTM _can be_ run
on the string to reach a final state. Here is where the notion of
"guessing" comes in -- since the NDTM will not accept a string only if
there is _no way_ it can accept the string, it is assumed to "guess" a
correct sequence of moves, if there exists one, that will result in the
string being accepted.

One intuitive way of thinking about this is to consider the NDTM as a
threaded program, which starts one new thread for each choice it can make
at each stage. Thus the computation branches out at each such stage.
Given an input string, the program will accept the string if some thread
in this tree of threads results in a final state.

-----

The definition of an NDTM does not say anything about the amount of time
taken by the NDTM to accept a string -- the polynomial time limit you
mentioned has nothing to do with NDTMs per se. However, one important
class of problems -- the class NP -- is defined as those which can be
decided in polynomial time by an NDTM that halts on all inputs. The class
NP has another definition, as the class of problems that can be verified
in polynomial time by a _deterministic_ TM that halts on all inputs.
This means that given an instance of the problem, there
exists some string (called a "certificate" or "witness", which is, in
general, different for each instance of the problem) such that the
deterministic TM can decide in polynomial time whether or not to accept
the instance, perhaps with the help of information contained in the
certificate. The two definitions have been shown to be equivalent (the
argument is easy to follow).

Please let me know if there are any online resources/text books that
give a good intuition for the same.

You could try Michael Sipser's "Introduction to the Theory of
Computation", where he gives a very intuitive picture. If you are feeling
particularly masochistic, you could try the classic "Introduction to
Automata Theory, Languages, and Computation" by Hopcroft and Ullman.

I am not sure if the following gives an intuitive picture(I haven't read it):

ftp://ftp.cis.ohio-state.edu/pub/tex/osu/gurari/zip-bk/pic/theory-bk.zip

Regards,
Philip
.

Relevant Pages