Class Description

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

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 measure 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 ${\displaystyle E(x,y)}$ is true iff there is an edge from ${\displaystyle x}$ to ${\displaystyle y}$ if the structure is a graph, and ${\displaystyle 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, ${\displaystyle x}$ is the number ${\displaystyle n}$ iff there is ${\displaystyle (n-1)}$ elements ${\displaystyle y}$ such that ${\displaystyle y<x}$. Thanks to this we also want the primitive "bit", where ${\displaystyle bit(x,y)}$ is true if only the ${\displaystyle y}$th bit of ${\displaystyle x}$ is 1. (We can replace ${\displaystyle bit}$ by plus and time, ternary relation such that ${\displaystyle plus(x,y,z)}$ is true iff ${\displaystyle x+y=z}$ and ${\displaystyle times(x,y,z)}$ is true iff ${\displaystyle x*y=z}$).

Since in a computer elements are only pointers or string of bits, those assumptions make sense, and those primitive functions 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 ( ${\displaystyle \wedge }$), negation (${\displaystyle \neg }$) and universal quantification (${\displaystyle \forall }$) over element of the structures. We also often use existential quantification (${\displaystyle \exists }$) and disjunction (${\displaystyle \vee }$) but those can be defined thanks to the 3 first symbols.

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

A query 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 prenex normal form where we put recursively every quantifier and then a quantifier-free formulae.

Linked From

AC⁰: Unbounded Fanin Constant-Depth Circuits

An especially important subclass of AC, corresponding to constant-depth, unbounded-fanin, polynomial-size circuits with AND, OR, and NOT gates.

Computing the Parity or Majority of n bits is not in AC⁰ [FSS84].

There are functions in AC⁰ that are pseudorandom for all statistical tests in AC⁰ [NW94]. But there are no functions in AC⁰ that are pseudorandom for all statistical tests in QP (quasipolynomial time) [LMN93].

[LMN93] showed furthermore that functions with AC⁰ circuits of depth d are learnable in QP, given their outputs on O(2^{log(n)^O(d)}) randomly chosen inputs. On the other hand, this learning algorithm is essentially optimal, unless there is a 2^{n^o(1)} algorithm for factoring [Kha93].

Although there are no good pseudorandom functions in AC⁰, [IN96] showed that there are pseudorandom generators that stretch n bits to n+Θ(log n), assuming the hardness of a problem based on subset sum.

AC⁰ contains NC⁰, and is contained in QAC_f⁰ and MAC⁰.

In descriptive complexity, uniform AC⁰ can be characterized as the class of problems expressible by first-order predicates with addition and multiplication operators - or indeed, with ordering and multiplication, or ordering and division (see [Lee02]). So it's equivalent to the class FO, and to the alternating logtime hierarchy.

[BLM+98] showed the following problem is complete for depth-k AC⁰ circuits (with a uniformity condition):

Given a grid graph of polynomial length and width k, decide whether there is a path between vertices s and t (which can be given as part of the input).

More about...

Dyn-FO: Dynamic FO

The class of dynamic problems solvable using first-order predicates.

Basically what this means is that an algorithm maintains some polynomial-size data structure (say a graph), and receives a sequence of updates (add this edge, delete that one, etc.). For each update, it computes a new value for the data structure in FO -- that is, for each bit of the data structure, there is an FO function representing the new value of that bit, which takes as input both the update and the previous value of the data structure. At the end the algorithm needs to answer some question (i.e. is the graph connected?).

See [HI02] for more information, and a complete problem for Dyn-FO.

See also Dyn-ThC⁰.

More about...

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

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

Since ${\displaystyle P}$s are property of arity ${\displaystyle k}$, there is at most ${\displaystyle 2^{n^{k}}}$ values for the ${\displaystyle 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.

More about...

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 ${\displaystyle k}$ be a positive integer and ${\displaystyle u,v,x,y}$ be vectors of ${\displaystyle k}$ variables, then TC(${\displaystyle \phi _{u,v})(x,y)}$ is true if there exist ${\displaystyle n}$ variables ${\displaystyle (x_{i})}$ such that ${\displaystyle x_{1}=x,x_{n}=y}$ and for all ${\displaystyle i<n}$ ${\displaystyle \phi _{u,v}(x_{i},x_{i+1})}$. Here, ${\displaystyle \phi _{u,v}}$ is a formula over ${\displaystyle u,v}$ written in FO(TC) and ${\displaystyle \phi _{u,v}(x,y)}$ means that the variables ${\displaystyle u}$ and ${\displaystyle v}$ are replaced by ${\displaystyle x}$ and ${\displaystyle y}$.

Every formula of TC can be written in a normal form FO(${\displaystyle \phi _{u,v})(0,max)}$ where ${\displaystyle \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.

More about...

FO[${\displaystyle t(n)}$]: Iterated First-Order logic

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

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

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

In Descriptive complexity we can see that :

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

More about...

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.

More about...

HO: High-Order logic

High order logic is an extension of Second order, First order where we add quantification over higher order variables.

We define a relation of order ${\displaystyle o}$ and arity ${\displaystyle k}$ to be a subset of ${\displaystyle k}$-tuple of relation of order ${\displaystyle o-1}$ and arity ${\displaystyle k}$. When ${\displaystyle o=1}$ it is by extension a first order variable. "The quantification of formula in HO is over a given order (which is a straightforward extension of SO where we add quantification over constants (first-order variables) and relations (second-order variables)). The atomic predicates now can be general application of relations of order ${\displaystyle o}$ and arity ${\displaystyle k}$ to ${\displaystyle k}$ relations of order ${\displaystyle o-1}$ and arity ${\displaystyle a}$ and test of equality between two relations of the same order and arity.

${\displaystyle HO^{o}}$ is the set of formulae with quantification up to order O. ${\displaystyle \Sigma _{j}^{i}}$(resp. ${\displaystyle \Pi _{j}^{i}}$) is defined as the set of formula in ${\displaystyle HO^{i+1}}$ beginning by an existential (resp universal) quantifier followed by at most ${\displaystyle j-1}$ alternation of quantifiers.

This class was defined in [HT06], and it was proved that ${\displaystyle \Sigma _{j}^{i}=\exp _{2}^{i-1}(n^{O}(1))^{\Sigma _{j-1}^{P}}}$ where ${\displaystyle \Sigma _{j-1}^{P}}$ is the ${\displaystyle j}$th level of the polynomial hierarchy.

More about...

SO: Second-Order logic

We define second-order variable has got an arity ${\displaystyle k}$ and represent any proposition of arity ${\displaystyle k}$. They are usually written in upper-case.

Second order logic is the set of FO formulae where we add quantification over second-order variables.

Every formuale is equivalent to a formulae in prenex normal form, where we first write quantification on variable on second order and then a FO-formulae in prenex normal form.

In Descriptive complexity we can see that SO is equal to PH, more precisely we have that formulae in prenex normal form where existential and universal of second order alternate ${\displaystyle k}$ times are the ${\displaystyle k}$th level of the polynomial hierarchy.

This means that SO with only existential second-order quantification is equal to ${\displaystyle \Sigma ^{1}}$ which is NP, and with only universal quantification is equal to ${\displaystyle \Pi ^{1}}$ which is Co-NP.

More about...

SO[LFP]: Second-Order logic with least fixed point

SO[LFP] is to SO what FO[LFP] is to FO. The LFP operator can now also take second-order variable as argument.

In Descriptive complexity we can see that SO[LFP] is equal to EXPTIME.

More about...

SO[TC]: Second-Order logic with transitive closure

SO[TC] is to SO as FO[TC] is to FO. The TC operator can now also take second-order variable as argument.

In Descriptive complexity we can see thatSO[TC] is equal to PSPACE.

More about...

SO[${\displaystyle t(n)}$]: Iterated Second-Order logic

SO[${\displaystyle t(n)}$] is to SO as FO[${\displaystyle t(n)}$] is to FO. But we now also have second-order quantifier in the quantifier block.

In Descriptive complexity we can see that :

• SO[${\displaystyle n^{O(1)}}$] is equal to PSPACE it is also another way to write SO(TC)
• SO[${\displaystyle 2^{n^{O(1)}}}$] is equal to EXPTIME it is also another way to write SO(LFP)

More about...