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 function problems of the form "compute f(x)," where f is the number of accepting paths of an NP machine.
The canonical #P-complete problem is #SAT.
Defined in [Val79], where it was also shown that #Perfect Matching (or equivalently, Permanent) is #P-complete. What makes that interesting is that the associated decision problem Perfect Matching is in P.
Any function in #P can be approximated to within a polynomial factor in BPP with NP oracle [Sto85]. Likewise, any problem in #P can be approximated to within a constant factor by a machine in FP||NP running in time [SU05].
The class of decision problems solvable by an NP machine such that for some polynomial-time computable (i.e. FP) function f,
Defined in [FFK94].
Contains BQP [FR98], WAPP [BGM02], LWPP, and WPP.
Has the same relation to BPP as FNP does to NP. Equivalently, it is the randomised analogue of FP.
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.
Given a graph, the problem of outputting the size of its maximum clique is complete for FPNP[log].
A class of number-theoretic functions, defined as the closure of basic integer arithmetic operations (, as well as constants 0, 1, and projections) under composition and polynomially long sums and products. Defined by [Con73], who mistakenly claimed it coincides with FP.
Equals UD-uniform FTC0 by [Hes01].
The class of decision problems solvable by an NP machine such that
Defined in [FFK94], where it was also shown that LWPP is low for PP and C=P. (I.e. adding LWPP as an oracle does not increase the power of these classes.)
Contains SPP.
Also, contains the graph isomorphism problem [KST92].
Contains a whole litter of problems for solvable black-box groups: group intersection, group factorization, coset intersection, and double-coset membership [Vin04].
The class of function problems of the form, "Find any n-bit string x that maximizes a cost function C(x), where C is computable in FP (i.e. polynomial-time)."
Defined in [ACG+99].
The class of NPMV functions that are single-valued (i.e., such that every accepting path outputs the same value).
Defined in [BLS84].
Contains NPSVt.
P = NP if and only if FP = NPSV.
Defined like NT, but with a more general ordering on inputs. A problem L is in NT* if, first, there is a partially defined predecessor function pred(x) in FP that organizes the space of inputs into a forest. The size of the lineage of each x must also be bounded by 2poly(|x|). Second, if L(x) is the Boolean answer to L on input x, then L(x)+L(pred(x)) is computable in polynomial time; or if pred(x) does not exist, L(x) is computable in polynomial time.
Defined in [GHJ+91].
Contains NT and is contained in ⊕P. The inclusions are either both strict or both equalities (whence ⊕P = P as well).
The class that started it all.
The class of decision problems solvable in polynomial time by a Turing machine. (See also FP, for function problems.)
Defined in [Edm65], [Cob64], [Rab60], and other seminal early papers.
Contains some highly nontrivial problems, including linear programming [Kha79] and finding a maximum matching in a general graph [Edm65].
Contains the problem of testing whether an integer is prime [AKS02], an important result that improved on a proof requiring an assumption of the generalized Riemann hypothesis [Mil76].
A decision problem is P-complete if it is in P, and if every problem in P can be reduced to it in L (logarithmic space). The canonical P-complete problem is circuit evaluation: given a Boolean circuit and an input, decide what the circuit outputs when given the input.
Important subclasses of P include L, NL, NC, and SC.
P is contained in NP, but whether they're equal seemed to be an open problem when I last checked.
Efforts to generalize P resulted in BPP and BQP.
The nonuniform version is P/poly, the monotone version is mP, and versions over the real and complex number fields are PR and PC respectively.
In descriptive complexity, P can be defined by three different kind of formulae, FO(lfp) which is also FO()], and also as SO(Horn)
P queries are exactly the one that can be written in the While/cons languages.
P is the class of decision problems solvable by a (logspace) uniform family of polynomial-size Boolean circuits.
P can be computed by interactive protocols (see IP) where the verifier runs in log space (see L and BPL) [GKR15].
The class of decision problems for which the following holds. There exists a #P function f and an FP function g such that, for all inputs x,
Defined in [BGM02], where the following was also shown:
There exists an oracle relative to which SBP is not closed under intersection [GLM+15].
If SAT can be solved by an NP-machine with sub-exponential number of accepting paths, then SBP = AM [Vol20].
The class of functions computable as |S|, where S is the set of output values returned by the accepting paths of an NL machine.
Defined in [AJ93], where it is also shown that span-L is a hard class in the sense that span-L is contained in FP if and only if FP = #P.
Span-L is contained in #P, and if span-L = #P, then NL = NP [AJ93].
Span-L is contained in FPRAS [ACJ+21].
The class of decision problems solvable by an NP machine such that
We may additionally require that all paths make the same number of binary nondeterministic choices, but then the second condition has to be modified so that if the answer is "yes", the number of accepting and rejecting paths differ by 2. (If the total number of paths is even then the numbers can't differ by 1.)
Defined in [FFK94], where it was also shown that SPP is low for PP, C=P, ModkP, and SPP itself. (I.e. adding SPP as an oracle does not increase the power of these classes.)
Independently defined in [OH93], who called the class XP.
Contained in LWPP, C=P, and WPP among other classes.
Contains FewP; indeed, FewP is low for SPP, so that SPPFewP = SPP [FFK94].
Contains the problem of deciding whether a graph has any nontrivial automorphisms [KST92].
Indeed, contains graph isomorphism [AK02].
Contains a whole gaggle of problems for solvable black-box groups: solvability testing, membership testing, subgroup testing, normality testing, order verification, nilpotetence testing, group isomorphism, and group intersection [Vin04]
[AK02] also showed that the Hidden Subgroup Problem for permutation groups, of interest in quantum computing, is in FPSPP.
A superclass of VPk in Valiant's algebraic complexity theory, but not quite the analogue of NP.
A problem is in VNPk if there exists a polynomial p with the following properties:
Originated in [Val79b].
If the field k has characteristic greater than 2, then the permanent of an n-by-n matrix of indeterminates is VNPk-complete under a type of reduction called p-projections ([Val79b]; see also [Bur00]).
A central conjecture is that for all k, VPk is not equal to VNPk. Bürgisser [Bur00] shows that if this were false then:
In both cases, PH collapses to Σ2P.
The class of decision problems solvable by an NP machine such that
Defined in [FFK94].
Contained in C=P ∩ coC=P, as well as AWPP.
