# Difference between revisions of "Complexity Zoo:F"

(→FO[t(n)]: Iterated First-Order logic) |
m (1 revision: Complexity zoo import.) |

## Revision as of 23:10, 17 November 2012

*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() -
FOLL -
FP -
FP^{NP[log]} -
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

- The number of accepting paths a is bounded by a polynomial in the size of the input x.
- 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 , the following conditions are equivalent:

- There exists an EXP machine such that if given a string , accepts and has exponentially bounded accepting paths, then produces one such path.
- There exists an EXP/poly machine which accepts a string if and only accepts.

##### FewP: NP With Few Witnesses

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

- If the answer is 'no,' then all computation paths reject.
- 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].

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

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:

- the function F
_{I}is represented by an algebraic circuit over {+, -, *, /, max, min} with rational constants - 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.

##### 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^{0} 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 is true iff there is an edge from to if the structure is a graph, and 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, is the number iff there is elements such that . Thanks to this we also want the primitive "bit", where is true if only the th bith of is 1. (We can replace by plus and time, ternary relation such that is true iff and is true iff ).

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 ( ), negation () and universal quantification () over element of the structures. We also often use existantial quantification () and disjunction () but those can be defined thanks to the 3 first symbols.

The semantics of the formulae in FO is straightforward, is true iff is false, is true iff is true and is true, and () is true iff whatever element we decide that is we can choose, 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(), we know that for all , there exist at most one such that phi(u,v).

We can suppose that DTC() is syntactic sugar for TC() where .

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 , then always implies .

We can obtain the monotony by restricting the formula to have only positive occurrences of (i.e. there is an even number of negations before every occurrence of ). We can also describe LFP() as syntactic sugar of PFP() where .

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

##### 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 be an integer, vectors of variables, a second-order variable of arity , and a FO(PFP) function using and as variables, then we can define iteratively such that and which means that the property is true on the input if is true on input , and when the variable is replaced by . Then, either there is a fixed point, or the list of is looping.

PFP( is defined as the value of the fixed point of on y if there is a fixed point, else as false.

Since s are property of arity , there is at most values for the 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 be a positiver integer and be vectors of variables, then TC( is true if there exist variables such that and for all . Here, is a formula over written in FO(TC) and means that the variables and are replaced by and .

Every formula of TC can be written in a normal form FO( where 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[]: Iterated First-Order logic

Let be a function from integers to integers. abbreviates and abbreviates .

A quantifier block is a list where the s are quantifier free FO-formulae and each s is either or . If is a quantifier block then is the block consisting of iterated copies of . Note that there are quantifiers in the list, but only k variables; each variable is used times.

FO[] consists of the FO-formulae with quantifier blocks that are iterated times.

In Descriptive complexity we can see that :

- FO[] is equal to fo-uniform AC
^{i}, and in fact FO[] is fo-uniform AC of depth - FO[] is equal to NC
- FO[] is equal to P and FO(LFP)
- FO[] 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^{0}, and is contained in uniform AC^{1}.

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

##### 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,

- If the answer is "yes" then D
^{L}(x) (D with oracle for L) accepts with probability at least 2/3. - 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)).