Complexity Zoo:F

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

---

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

---

FBQP - FERT - FPERT - Few - FewEXP - FewP - FH - FIXP - FNL - FNL/poly - FNP - FO - FO(DTC) - FO(LFP) - FO(PFP) - FO(TC) - FO($t(n)$) - FOLL - FP - FP^NP[log] - FPL - FPR - FPRAS - FPT - FPT_nu - FPT_su - FPTAS - FQMA - frIP - F-TAPE(f(n)) - F-TIME(f(n))

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: First-Order logic

First order logic is the smallest logical class of logic language. It is the base of Descriptive complexity and equal to the class AC⁰ and to AH, the alternating logtime hierarchy.

When we use logic formalism, the input is a structure, usually it is either strings (of bits or over an alphabet) whose elements are position of the strings, or graphs whose elements are vertices. The mesure of the input will there be the size of the structure. Whatever the structure is, we can suppose that there are relation that you can test, by example $E(x,y)$ is true iff there is an edge from $x$ to $y$ if the structure is a graph, and $P(n)$ is true iff the nth letter of the string is 1. We also have constant, who are special elements of the structure, by example if we want to check reachability in a graph, we will have to choose two constant s and t.

In descriptive complexity we almost always suppose that there is a total order over the elements and that we can check equality between elements. This let us consider elements as number, $x$ is the number $n$ iff there is $(n-1)$ elements $y$ such that $y<x$. Thanks to this we also want the primitive "bit", where $bit(x,y)$ is true if only the $y$th bith of $x$ is 1. (We can replace $bit$ by plus and time, ternary relation such that $plus(x,y,z)$ is true iff $x+y=z$ and $times(x,y,z)$ is true iff $x*y=z$).

Since in a computer elements are only pointers or string of bit, thoses assumptions make sens, and those primitive function can be calculated in most of the small complexity classes. We can also imagine FO without those primitives, which gives us smaller complexity classes.

The language FO is then defined as the closure by conjunction ( $\wedge$), negation ($\neg$) and universal quantification ($\forall$) over element of the structures. We also often use existantial quantification ($\exists$) and disjunction ($\vee$) but those can be defined thanks to the 3 first symbols.

The semantics of the formulae in FO is straightforward, $\neg A$ is true iff $A$ is false, $A\wedge B$ is true iff $A$ is true and $B$ is true, and ($\forall xP$) is true iff whatever element we decide that $x$ is we can choose, $P$ is true.

A querie in FO will then be to check if a FO formulae is true over a given structure, this structure is the input of the problem. One should not confuse this kind of problem with checking if a quantified boolean formula is true, which is the definition of QBF, which is Pspace-complete. The difference between those two problem is that in QBF the size of the problem is the size of the formula and elements are just boolean value, whereas in FO the size of the problem is the size of the structure and the formula is fixed.

Every formulae is equivalent to a formulae in prenexe normal form where we put recursively every quantifier and then a quantifier-free formulae.

---

FO(DTC): First-order with deterministic transitive closure

FO(DTC) is defined as FO(tc) where the transitive closure operator is deterministic, which means that when we apply DTC($\phi _{u,v}$), we know that for all $u$, there exist at most one $v$ such that phi(u,v).

We can suppose that DTC($\phi _{u,v}$) is syntactic sugar for TC($\psi _{u,v}$) where $\psi (u,v)=\phi (u,v)\wedge \forall x,(x=v\vee \neg \psi (u,x))$.

It was shown in [Imm99] page 144 that this class is equal to L.

---

FO(LFP): First-order with least fixed point

FO(LFP) is the set of boolean queries definable with first-order fixed-point formulae where the partial fixed point is limited to be monotone, which means that if the second order variable is $P$, then $P_{i}(x)$ always implies $P_{i+1}(x)$.

We can obtain the monotony by restricting the formula $\phi$ to have only positive occurrences of $P$ (i.e. there is an even number of negations before every occurrence of $P$). We can also describe LFP($\phi _{P,x}$) as syntactic sugar of PFP($\psi _{P,x}$) where $\psi (P,x)=\phi (P,x)\vee P(x)$.

Thanks to monotonicity we only add and never remove vectors to the truth table of $P$, and since there is only $n^{k}$ possible vectors we always find a fixed point before $n^{k}$ iterations. Hence it was shown in [Imm82] that FO(LFP)=P. This definition is equivalent to FO($n^{O(1)}$).

---

FO(PFP): First-order with partial fixed point

FO(pfp) is the set of boolean queries definable with first-order formulae with a partial fixed point operator.

Let $k$ be an integer, $x,y$ vectors of $k$ variables, $P$ a second-order variable of arity $k$, and $\phi$ a FO(PFP) function using $x$ and $P$ as variables, then we can define iteratively $(P_{i})_{i\in N}$ such that $P_{0}(x)=false$ and $P_{i}(x)=\phi (P_{i-1},x)$ which means that the property $P_{i}$ is true on the input $x$ if $\phi$ is true on input $x$, and when the variable $P$ is replaced by $P_{i-1}$. Then, either there is a fixed point, or the list of $(P_{i})$ is looping.

PFP($\phi _{P,x})(y)$ is defined as the value of the fixed point of $(P_{i})$ on y if there is a fixed point, else as false.

Since $P$s are property of arity $k$, there is at most $2^{n^{k}}$ values for the $P_{i}$s, so with a poly-space counter we can check if there is a loop or not.

It was proved in [Imm98] that FO(pfp) is equal to PSPACE.

---

FO(TC): First-order with transitive closure

FO(TC) is the set of boolean queries definable with first-order formulae with a transitive closure (TC) operator.

TC is defined this way: let $k$ be a positiver integer and $u,v,x,y$ be vectors of $k$ variables, then TC($\phi _{u,v})(x,y)$ is true if there exist $n$ variables $(x_{i})$ such that $x_{1}=x,x_{n}=y$ and for all $i<n$ $\phi _{u,v}(x_{i},x_{i+1})$. Here, $\phi _{u,v}$ is a formula over $u,v$ written in FO(TC) and $\phi _{u,v}(x,y)$ means that the variables $u$ and $v$ are replaced by $x$ and $y$.

Every formula of TC can be written in a normal form FO($\phi _{u,v})(0,max)$ where $\phi$ is a FO formula and we suppose that there is an order on the model where variables are quantified, so we can choose the minimum and maximum element.

It was shown in [Imm98] page 150 that this class is equal to NL.

---

FO[$t(n)$]: Iterated First-Order logic

Let $t(n)$ be a function from integers to integers. $(\forall xP)Q$ abbreviates $(\forall x(P\Rightarrow Q))$ and $(\exists xP)Q$ abbreviates $(\exists x(P\wedge Q))$.

A quantifier block is a list $(Q_{1}x_{1}.\phi _{1})...(Q_{k}x_{k}.\phi _{k})$ where the $\phi _{i}$s are quantifier free FO-formulae and each $Q_{i}$s is either $\forall$ or $\exists$. If $Q$ is a quantifier block then $[Q]^{t(n)}$ is the block consisting of $t(n)$ iterated copies of $Q$. Note that there are $k*t(n)$ quantifiers in the list, but only k variables; each variable is used $t(n)$ times.

FO[$t(n)$] consists of the FO-formulae with quantifier blocks that are iterated $\Theta (t(n))$ times.

In Descriptive complexity we can see that :

• FO[$(\log n)^{i}$] is equal to fo-uniform ACⁱ, and in fact FO[$t(n)$] is fo-uniform AC of depth $t(n)$
• FO[$(\log n)^{O(1)}$] is equal to NC
• FO[$n^{O(1)}$] is equal to P and FO(LFP)
• FO[$2^{n^{O(1)}}$] is equal to PSPACE and FO(PFP)

---

FOLL: First-Order log log n

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

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

Contains uniform AC⁰, and is contained in uniform AC¹.

Is not known to be comparable to L or NL.

---

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 RP 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 FPT 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)).