HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How do nondeterministic Turing machines compute general function problems?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
howcomputefunctiongeneralmachinesnondeterministicturingproblems

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#59358, answer score: 7

Revisions (0)

No revisions yet.