The class of function problems of the following form:
FNP generalizes NP, which is defined in terms of decision problems only.
Actually the word "function" is misleading, since there could be many valid outputs y. That's unavoidable, since given a predicate F there's no "syntactic" criterion ensuring that y is unique.
FP = FNP if and only if P = NP.
Contains TFNP.
A basic question about FNP problems is whether they're self-reducible; that is, whether they reduce to the corresponding NP decision problems. Although this is true for all NPC problems, [BG94] shows that if EE does not equal NEE, then there is a problem in NP such that no corresponding FNP problem can be reduced to it. [BG94] cites Impagliazzo and Sudan as giving the same conclusion under the assumption that NE does not equal coNE.
Has the same relation to BPP as FNP does to NP. Equivalently, it is the randomised analogue of FP.
Has the same relation to BQP as FNP does to NP.
There exists an oracle relative to which PLS is not contained in FBQP [Aar03].
Has the same relation to NL as FNP does to NP.
Defined by [AJ93], who also showed that if NL = UL, then FNL is contained in #L.
Sometimes defined as the class of functions computable in polynomial time by a Turing machine. (Generalizes P, which is defined in terms of decision problems only.)
However, if we want to compare FP to FNP, we should instead define it as the class of FNP problems (that is, polynomial-time predicates P(x,y)) for which there exists a polynomial-time algorithm that, given x, outputs any y such that P(x,y). That is, there could be more than one valid output, even though any given algorithm only returns one of them.
FP = FNP if and only if P = NP.
If FPNP = FPNP[log] (that is, allowed only a logarithmic number of queries), then P = NP [Kre88]. The corresponding result for PNP versus PNP[log] is not known, and indeed fails relative to some oracles (see [Har87b]).
The class of problems for which the task is to output a quantum certificate for a QMA problem, when such a certificate exists. Thus, the desired output is a quantum state.
Defined in [JWB03], where it is also shown that state preparation for 3-local Hamiltonians is FQMA-complete. The authors also observe that, in contrast to the case of FNP versus NP, there is no obvious reduction of FQMA problems to QMA problems.
The class of all (possibly partial, possibly multivalued) functions computed by an NP machine as follows: ignore the rejecting paths, and consider any output of an accepting path to be "one of the outputs."
Defined in [BLS84].
Contrast with FNP.
The class of functions computable by taking the maximum (or minimum) of the output values over all accepting paths of an NP machine. OptP[f(n)] restricts the size of the output to f(n) bits.
Defined in [Kre88].
Contrast with FNP.
MaxSat that returns the number of satisfied clauses, Clicque that returns the size of the clique, Chromatic Number are OptP[log n]-complete.
The class of FNP search problems solvable in O(2εn) time for every ε>0.
Defined in [IPZ01], who also gave reductions showing that if any of k-SAT, k-colorability, k-set cover, clique, or vertex cover is in SE, then all of them are.
The class of function problems of the following form:
Can be considered as the functional analogue of NP ∩ coNP. Defined in [MP91].
Contained in FNP.
Subclasses include PPA, PPP, and PLS.