World's most popular travel blog for travel bloggers.

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

, , No Comments
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?)

Asked By : lukas.coenig

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback