7
$\begingroup$

(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?)

$\endgroup$
2
  • $\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, 2016 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, 2016 at 11:29

2 Answers 2

6
$\begingroup$

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.

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

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.

$\endgroup$
3
  • $\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, 2016 at 13:04
  • $\begingroup$ I don't understand. When you say "there is no way to execute a nondeterministic algorithm", are you speaking pragmatically in saying that a NTM cannot exist in this universe, but if it could, then there would be a way to execute? Also, you say that "you need to get rid of the idea of having an algorithm you execute to get a result"... but we know that you can simulate a NTM using a DTM, and that DTM uses an algorithm you execute to get a result. Doesn't that imply an algorithm in the NTM as well? $\endgroup$
    – cowlinator
    Feb 16 at 23:59
  • $\begingroup$ @cowlinator That's a bit like saying that $\pi$ is an algorithm because you can compute it to arbitrary precision with a suitable algorithm. 😉 But yes, you can simulate an NTM with a DTM in a certain sense. If you do it right, you'll find an answer of the NTM, if it does indeed compute any. However, most "metrics" you apply to NTMs will be skrewed. That all said, you seem to be focused on the first part of my answer; I suggest you read on below the line, which I think illustrates some inherent differences that may help. $\endgroup$
    – Raphael
    Feb 17 at 9:33

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.