(Hope this hasn't been asked before, but I didn't find anything.)

In my understanding, nondeterminism applies to decision problems only, due to the requirement of the existence of an accepting path. In Wikipedia, the class $NP$-easy is defined to be solvable in deterministic poltime, with access to an oracle for a decision problem in NP. So this seems to back my assumption.

My question is: Is there an accepted way to define a non-deterministic Turing machine to compute a general function problem? (And is it always by a detour over an oracle for a decision problem?)

  • $\begingroup$ I'd appreciate a more detailed answer. (You certainly CAN have an operational view on nondeterminism!) But you're getting my point - if only one branch halts (or zero) then there's no problem, but in any other case, there are several outputs. $\endgroup$ Jun 8 '16 at 10:22
  • $\begingroup$ "You certainly CAN have an operational view on nondeterminism!" -- you can try, but this way only misconceptions and madness lie. $\endgroup$
    – Raphael
    Jun 8 '16 at 11:29

One accepted definition is as follows: a function $f$ (whose output is at most polynomial in its input) is in the class $\mathsf{FNP}$ if given $x,y$ one can decide in polynomial time whether $f(x)=y$. Compare this to the class $\mathsf{FP}$, which contains those functions $f$ such that given $x$, the value of $f(x)$ can be computed in polynomial time.

  • $\begingroup$ Ah, this makes lots of sense! Thanks!! $\endgroup$ Jun 7 '16 at 10:54
  • $\begingroup$ Do you have a citation for this definition? $\endgroup$
    – adrianN
    Jun 7 '16 at 12:03
  • 1
    $\begingroup$ No, but perhaps Wikipedia does. $\endgroup$ Jun 7 '16 at 12:03

First off, whenever you talk about nondeterminism you need to get rid of the idea of having an algorithm you execute to get a result. Nondeterministic models are descriptive only, not operational; there is no way to "execute" a nondeterministic algorithm. Sometimes, teachers say things like "the machine always guesses right" or "we execute all branches in parallel" but these intuition statements fall short in one way or the other.

So, accept that a nondeterministic machine describes some formal object. Period.

There are two ways to gain intuition about nondeterministic automata. From the lower end, consider finite-state transducers. They are essentially finite automata with output; obviously, FA reduce to them. In the non-deterministic case, each input can (but need not!) result in multiple outputs. Therefore, it makes sense to define the "result" of an FT $A$ on $w$ as the set of all outputs $A$ can produce on $w$. Now you can happily take the union over several input words, or consider preimages, and so on.

From the other end of the spectrum, consider NTM. The same idea works: for every input $w$, define as output the set of all tape contents you can have when the machine halts (in an accepting state) on $w$.

Note that nothing prevents you from requiring the automaton to have only one output per input, for instance when defining a complexity class.

It is similar for resource restrictions; the ideas used for defining decision problem classes should mostly carry over.

  • $\begingroup$ Thanks, this was (at least part of) the answer I was looking for (although I suspect you knew that all along...). I still believe that the "guessing" or "parallel" methaphors are important, particularly for beginners, if used with care. But you're of course right in saying that they do not capture all the subtleties of nondeterminism. $\endgroup$ Jun 8 '16 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.