Class Description

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

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

A quantifier block is a list ${\displaystyle (Q_1{x}_1.{\varphi }_1)...(Q_k{x}_k.{\varphi }_k)}$ where the ${\displaystyle {\varphi }_i}$s are quantifier free FO-formulae and each ${\displaystyle Q_i}$s is either ${\displaystyle \mathrm{\forall }}$ or ${\displaystyle \mathrm{\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 \mathrm{\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)

Linked From 4 Classes

AC: Unbounded Fanin Polylogarithmic-Depth Circuits

ACⁱ is the class of decision problems solvable by a nonuniform family of Boolean circuits, with polynomial size, depth O(logⁱ(n)), and unbounded fanin. The gates allowed are AND, OR, and NOT.

Then AC is the union of ACⁱ over all nonnegative i.

ACⁱ is contained in NCⁱ⁺¹; thus, AC = NC.

AC¹ contains NL.

For a random oracle A, (ACⁱ)^A is strictly contained in (ACⁱ⁺¹)^A, and (uniform) AC^A is strictly contained in P^A, with probability 1 [Mil92].

FO-uniform AC with depth ${\displaystyle t(n)}$ is equal to FO[${\displaystyle t(n)}$].

More about...

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 ${\displaystyle P}$, then ${\displaystyle P_i(x)}$ always implies ${\displaystyle P_{i+1}(x)}$.

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

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

More about...

NC: Nick's Class

(Named in honor of Nick Pippenger.)

NCⁱ is the class of decision problems solvable by a uniform family of Boolean circuits, with polynomial size, depth O(logⁱ(n)), and fan-in 2.

Then NC is the union of NCⁱ over all nonnegative i.

Also, NC equals the union of PT/WK(log^kn, n^k)/poly over all constants k.

NCⁱ is contained in ACⁱ; thus, NC = AC.

Contains NL, in fact NL is contained in NC².

Generalizations include RNC and QNC.

[IN96] construct a candidate pseudorandom generator in NC based on the subset sum problem.

For a random oracle A, (NCⁱ)^A is strictly contained in (NCⁱ⁺¹)^A, and uniform NC^A is strictly contained in P^A, with probability 1 [Mil92].

In descriptive complexity, NC can be defined by FO[${\displaystyle \log (n{)}^{O(1)}}$]

Log space uniform NC is contained in ATIME(poly(log(n))) = polyL [RUZ81].

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