Complexity Zoo:F

From Qwiki

FBQP: Function BQP

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].

---

Few: FewP With Flexible Acceptance Mechanism

The class of decision problems solvable by an NP machine such that

1. The number of accepting paths a is bounded by a polynomial in the size of the input x.
2. For some polynomial-time predicate Q, Q(x,a) is true if and only if the answer is 'yes.'

Also called FewPaths.

Defined in [CH89].

Contains FewP, and is contained in P^FewP [Kob89] and in SPP [FFK94].

See also the survey [Tor90].

---

FewEXP: NEXP With Few Witnesses

The class of decision problems solvable by an NEXP machine such that, given a "yes" instance, no more than an exponential number of computation paths accept.

Contained in MIP[NP^FewEXP] (MIP where provers are not unbounded in computational power, but are limited to NP^FewEXP) [AKS+94].

Alternatively, FewEXP can refer to the sparsity of accepting paths in a given instance. In [AKR+03], the authors show that the conjectures "FewEXP search instances are EXP-solvable" and "FewEXP decision instances are EXP/poly-solvable" are equivalent. That is, for all NEXP machines N, the following conditions are equivalent:

1. There exists an EXP machine M such that if given a string x, N(x) accepts and has exponentially bounded accepting paths, then M(x) produces one such path.
2. There exists an EXP/poly machine M which accepts a string x if and only N(x) accepts.

---

FewP: NP With Few Witnesses

The class of decision problems solvable by an NP machine such that

1. If the answer is 'no,' then all computation paths reject.
2. If the answer is 'yes,' then at least one path accepts; furthermore, the number of accepting paths is upper-bounded by a polynomial in n, the size of the input.

Defined in [AR88].

Is contained in ⊕P [CH89].

There exists an oracle relative to which P, UP, FewP, and NP are all distinct [Rub88].

Also, there exists an oracle relative to which FewP does not have a Turing-complete set [HJV93].

Contained in Few.

See also the survey [Tor90].

---

FH: Fourier Hierarchy

FH_k is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels of Hadamard gates and all other gates preserving the computational basis. (Conditional phase flip gates are fine, for example.) Thus

• FH₀ = P
• FH₁ = BPP
• FH₂ contains factoring because of Kitaev's phase estimation algorithm

It is an open problem to show that the Fourier hierarchy is infinite relative to an oracle (that is, FH_k is strictly contained in FH_k+1).

Defined in [Shi03].

---

FIXP: Fixed Point

The class of fixed point problems. In the framework of fixed point problems, an instance I is associated with a (continuous) function F_I, and a solution of I is a fixed point of F_I.

Properties of FIXP problems:

1. the function F_I is represented by an algebraic circuit over {+, -, *, /, max, min} with rational constants
2. there is a polynomial time algorithm that computes the circuit from I.

Every FIXP problem has Partial Computation, Decision, (Strong) Approximation, and Existence counterparts; these can all be solved in PSPACE.

The Nash equilibrium problem for 3 or more players is FIXP-complete.

Linear-FIXP = PPAD.

Defined in [EY07].

---

FNL: Function NL

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.

---

FNL/poly: Nonuniform FNL

Has the same relation to FNL as P/poly does to P.

Contained in #L/poly [RA00].

---

FNP: Function NP

The class of function problems of the following form:

Given an input x and a polynomial-time predicate F(x,y), if there exists a y satisfying F(x,y) then output any such y, otherwise output 'no.'

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.

---

FO(t(n)): First-Order

The class of decision problems for which a "yes" answer can be expressed by a first-order logic predicate, with a block of restricted quantifiers repeated t(n) times. See [Imm98] for a full definition.

FO(poly(n)) = P (see [Var82] for example).

FO(poly(n)) is contained in SO-E.

---

FOLL: First-Order loglog n

The class of decision problems solvable by a nonuniform family of polynomial-size, unbounded-fanin, depth O(loglog n) circuits with AND, OR, and NOT gates.

Defined in [BKL+00], where it was also shown that many problems on finite groups are in FOLL.

Contains AC⁰, and is contained in AC¹.

Is not known to be comparable to L/poly or NL/poly.

---

FP: Function Polynomial-Time

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 FP^NP = FP^NP[log] (that is, allowed only a logarithmic number of queries), then P = NP [Kre88]. The corresponding result for P^NP versus P^NP[log] is not known, and indeed fails relative to some oracles (see [Har87b]).

---

FP^NP[log]: FP With Logarithmically Many Queries To NP

Given a graph, the problem of outputting the size of its maximum clique is complete for FP^NP[log].

---

FPR: Fixed-Parameter Randomized

Has the same relation to FPT as R does to P.

Defined in [AR01], where it was shown that, if the Resolution proof system is automatizable (that is, if a refutation can always be found in time polynomial in the length of the shortest refutation), then W[P] is contained in FPR.

---

FPRAS: Fully Polynomial Randomized Approximation Scheme

The subclass of #P counting problems whose answer, y, is approximable in the following sense. There exists a randomized algorithm that, with probability at least 1-δ, approximates y to within an ε multiplicative factor in time polynomial in n (the input size), 1/ε, and log(1/δ).

The permanent of a nonnegative matrix is in FPRAS [JSV01].

---

FPT: Fixed-Parameter Tractable

The class of decision problems of the form (x,k), k a parameter, that are solvable in time f(k)p(|x|), where f is arbitrary and p is a polynomial.

The basic class of the theory of fixed-parameter tractability, as described by Downey and Fellows [DF99].

To separate FTP and W[2], one could show there is no proof system for CNF formulae that admits proofs of size f(k)n^O(1), where f is a computable function and n is the size of the formula.

Contained in FPT_nu, W[1], and FPR.

Contains FPTAS [CC97], as well as FPT_su.

Contains EPTAS unless FPT = W[1] [Baz95].

---

FPT_nu: Fixed-Parameter Tractable (nonuniform)

Same as FPT except that the algorithm can vary with the parameter k (though its running time must always be O(p(|x|)), for a fixed polynomial p).

An alternate view is that a single algorithm can take a polynomial-length advice string, depending on k.

Defined in [DF99] (though they did not use our notation).

---

FPT_su: Fixed-Parameter Tractable (strongly uniform)

Same as FPT except that f has to be recursive.

Defined in [DF99] (though they did not use our notation).

---

FPTAS: Fully Polynomial-Time Approximation Scheme

The subclass of NPO problems that admit an approximation scheme in the following sense. For any ε>0, there is an algorithm that is guaranteed to find a solution whose cost is within a 1+ε factor of the optimum cost. Furthermore, the running time of the algorithm is polynomial in n (the size of the problem) and in 1/ε.

Contained in PTAS.

Defined in [ACG+99].

Contained in FPT [CC97].

---

FQMA: Function QMA

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.

---

frIP: Function-Restricted IP Proof Systems

The class of problems L that have a decider in the following sense. There exists a BPP machine D such that for all inputs x,

1. If the answer is "yes" then D^L(x) (D with oracle for L) accepts with probability at least 2/3.
2. If the answer is "no" then D^A(x) accepts with probability at most 1/3 for all oracles A.

Contains compIP [BG94] and Check [BK89].

Contained in MIP = NEXP [FRS88].

Assuming NEE is not contained in BPEE, NP (and indeed NP ∩ Coh) is not contained in frIP [BG94].

---

F-TAPE(f(n)): Provable DSPACE(f(n)) For Formal System F

The class of decision problems that can be proven to be solvable in O(f(n)) space on a deterministic Turing machine, from the axioms of formal system F.

Defined in [Har78].

See also F-TIME(f(n)). The results about F-TAPE mirror those about F-TIME, but in some cases are sharper.

---

F-TIME(f(n)): Provable DTIME(f(n)) For Formal System F

The class of decision problems that can be proven to be solvable in O(f(n)) time on a deterministic Turing machine, from the axioms of formal system F.

Defined in [Har78], where the following was also shown:

• If F-TIME(f(n)) = DTIME(f(n)), then DTIME(f(n)) is strictly contained in DTIME(f(n)g(n)) for any nondecreasing, unbounded, recursive g(n).
• There exist recursive, monotonically increasing f(n) such that F-TIME(f(n)) is strictly contained in DTIME(f(n)).

See also F-TAPE(f(n)).