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 :
ACi is the class of decision problems solvable by a nonuniform family of Boolean circuits, with polynomial size, depth O(logi(n)), and unbounded fanin. The gates allowed are AND, OR, and NOT.
Then AC is the union of ACi over all nonnegative i.
ACi is contained in NCi+1; thus, AC = NC.
For a random oracle A, (ACi)A is strictly contained in (ACi+1)A, and (uniform) ACA is strictly contained in PA, with probability 1 [Mil92].
FO-uniform AC with depth is equal to FO[].
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().
(Named in honor of Nick Pippenger.)
NCi is the class of decision problems solvable by a uniform family of Boolean circuits, with polynomial size, depth O(logi(n)), and fan-in 2.
Then NC is the union of NCi over all nonnegative i.
Also, NC equals the union of PT/WK(logkn, nk)/poly over all constants k.
NCi is contained in ACi; thus, NC = AC.
Contains NL, in fact NL is contained in NC2.
Generalizations include RNC and QNC.
[IN96] construct a candidate pseudorandom generator in NC based on the subset sum problem.
For a random oracle A, (NCi)A is strictly contained in (NCi+1)A, and uniform NCA is strictly contained in PA, with probability 1 [Mil92].
In descriptive complexity, NC can be defined by FO[]
Log space uniform NC is contained in ATIME(poly(log(n))) = polyL [RUZ81].
SO[] is to SO as FO[] is to FO. But we now also have second-order quantifier in the quantifier block.
In Descriptive complexity we can see that :