Clarifying nondeterminism

From: Simon Thoresen (simonthoresen_at_hotmail.com)
Date: 04/19/04 

Date: Mon, 19 Apr 2004 16:52:42 +0200

I am having a problem with nondeterminism, and was hoping someone here could
clarify it for me.

An archtypical algorithm for solving NP class problems is defined as
follows:
1. non-deterministically guess a certificate;
2. check the certificate; if the certificate works, then say "yes"; if the
certificate doesn't work, then give up.

Such an algorithm implies that there is only ever a single guess and a
single test. "Non-deterministically guess" would then mean to either give
the solution or give nothing. Is that correct? Could such a guess give an
arbitrary wrong guess on one run, and a correct one on a second run?

The litterature I have read on the subject happily dodges elaborating this
"guess". A nondeterministic Turing machine consists of a guessing module
that writes an arbitrary guess onto the tape for the checking module to
test. What does "arbitrary" mean in this context? If it means random,
wouldn't every run give different guesses on the same input?

Other threads in this group describe nondeterminism as doing everything in
parallell or consulting an oracle; so a single nondeterministical guess
would actually give a solution if there is one. However many times the
algorithm is run, and thus however many times the guess is made, it will
never differ from the first run - unless ofcourse there are more than one
possible solution from which the guess may choose.

The NDTM model described in Garey and Johnson's "Computers and
Intractability" will write an arbitrary guess to the tape of the Turing
machine. The checking stage will accept the input if the verification
evaluates to "yes". But wouldn't such a model give an arbitrary guess which
would yield "yes" or "no" evaluations regardless of the input. I know, of
course, that this is wrong - but I would really love it if someone could
elaborate a little.

Regards,
Simon

Relevant Pages

  • Re: Clarifying nondeterminism
    ... I am having a problem with nondeterminism, and was hoping someone here could ... An archtypical algorithm for solving NP class problems is defined as ... check the certificate; if the certificate works, ... The NDTM model described in Garey and Johnson's "Computers and ...
    (comp.theory)
  • Re: Clarifying nondeterminism
    ... > I am having a problem with nondeterminism, and was hoping someone here could ... > An archtypical algorithm for solving NP class problems is defined as ... > certificate doesn't work, then give up. ... Thus a non-deterministic algorithm like the one you ...
    (comp.theory)
  • Re: Can EXPTIME and NP be separated via diagonalization?
    ... Now we must verify that the algorithm works. ... I think you have a misconception about how nondeterminism works. ... SAT formula, if I have an oracle for SAT, I can find a satisfying ... arrangement for the formula or find that no such arrangement exists. ...
    (comp.theory)
  • Re: Can EXPTIME and NP be separated via diagonalization?
    ... inputted language in time bounded by x^k+k; ... Now we must verify that the algorithm works. ... I think you have a misconception about how nondeterminism works. ...
    (comp.theory)