World's most popular travel blog for travel bloggers.

# [Solved]: How do nondeterministic Turing machines compute general function problems?

, ,
Problem Detail:

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

#### Answered By : Yuval Filmus

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.