4.2 Computational Models and Complexity Classes
4.2.4 Boolean Circuits and the N C -classes
Due to their capability to cover a large variety of computational phenomena Boolean circuits have proved to be one of the most suitable models of parallel computation. In this thesis we do not directly deal with Boolean circuits but indirectly through the no-tions ofN Ci,i∈ {1,2},AC1, indexing (random-access) ATMs, and branching programs.
Therefore, in this section, we provide only a brief description of circuits and uniformity restrictions imposed on them. For the formal definition of Boolean circuits, other notions and results concerning circuit complexity and Boolean functions, the reader is referred to [6,187,209,213].
Informally, a Boolean circuit is an assembly composed of a fixed numbern of Boolean input variablesx1, ...,xn, a finite number of gates over a basis set of Boolean functionsB, and a fixed numberm of outputs y1, ...,ym. The graphical representation of a Boolean circuit is viewed as a finite (labeled) directed acyclic graph (V,E) in which vertices are labeled by input variables, gates, and outputs [209]. Usually, the gates inBare the OR, AND, or NOT Boolean functions.
Thein-degree(out-degree) (see Section2.1), which for a Boolean circuit is also called fan-in (respectivelyfan-out), of each vertex depends on the type of the variable that labels that vertex. Inputs have fan-in 0. Outputs have fan-out 0. A Boolean circuit with n input vertices andmoutput vertices computes a Boolean functionf:{0,1}n→ {0,1}m. Each output element yi, 1 ≤ i ≤ m, gives the ith bit of the output y = (y1, ..., ym).
Intuitively, since the input of a Boolean circuit has a fixed length nit solves a problem P for an fixed instance of lengthnofP. Hence, the circuity model builds for each input length a circuit of its own, and therefore, for arbitrarily large number of inputs, whose lengths cover an infinite set of instances of a problem, there would be an infinite number of circuits solving the problem. A family of Boolean circuits {Ci}i≥1 solves a problem
Chapter 4. Asymptotic Growth, Computational Models, and Complexity Classes
P if the function computed by Ci, which has iinput vertices, solves the problem P for an instance of lengthi.
Since the input of a Boolean circuit has a fixed length, this model builds for each input length a circuit of its own. Therefore, for arbitrarily large number of inputs, whose lengths cover an infinite set of instances of a problem, there would be an infinite number of circuits solving the problem. Hence, Boolean circuits are non-uniform models of computation. In order to rank them among the realistic models of computation, an infinite family of circuits should be restructured according to several rules that make them “regular” and “uniformly constructible”. Under uniformity conditions Boolean circuits are calleduniform Boolean circuits. This makes it possible to compare Boolean circuits with other parallel or sequential models such as alternating or sequential TMs.
The main complexity measures of Boolean circuits aresize, i.e., the number of non-input gates, and depth, i.e., the length of the longest directed path from some input vertex to some output vertex. The size complexity of a family of circuits C = {Ci}i≥1 is the function s: N → N such that Cn has size s(n), for every n. The depth complexity of C is the function d:N→ N such that Cn has depth d(n), for every n. In other words, the size complexity of a circuit familyC is a function that provides the number of gates (vertices) in the nth circuit inC, while the depth complexity is a function that provides the depth of thenth circuit inC.
A Boolean circuit familyC={Ci}i≥1 of sizes(n) and depthd(n) islog-space uniform if there exists a deterministic TM that simulates4 thenthcircuit inCby using O(logs(n)) space on any input of lengthn. This uniformity restriction is calledUL-uniformity, while C is calledUL-uniform. If the deterministic TM simulating theC-family is restricted to useO(logs(n)) time, on any input of length n, thenC is calledUE-uniform. If instead of a TM we use an ATM that simulates the C-family in O(logs(n)) space and O(d(n)) time, on inputs of lengthn, thenC is called UE∗-uniform.
Denote by [209]
- SIZE(s(n)) the class of all setsA⊆ {0,1}∗ for which there is a family of circuits C of sizeO(s(n)) that acceptsA;
- DEP T H(d(n)) the class of all sets A⊆ {0,1}∗ for which there is a family of circuits C of depthO(d(n)) that acceptsA;
-SIZE-DEP T H(s(n), d(n)) the class of all setsA⊆ {0,1}∗ for which there is a family of circuitsC of size O(s(n)) and depth O(d(n)) that acceptsA;
-X-Y the class of all setsA⊆ {0,1}∗ for which there is anX-uniform circuit familyCof complexityY acceptingA, whereX∈ {UL, UE, UE∗}andY∈ {SIZE(s(n)), DEP T H(d(n)), SIZE-DEP T H(s(n), d(n))}.
4In other words (see also [209]), a Boolean circuit familyC={Ci}i≥1is log-space uniform if there ex-ists a proper encoding scheme of thenthcircuit such that the function 1n→Cnis inDSP ACE(logs(n)).
The following relations between time and space complexity classes of TMs or ATMs and the above circuit complexity classes hold [6,17,187,209]:
Ift(n)≥nis time-constructible ands(n)≥lognspace-constructible, then DT IM E(t(n))⊆SIZE(t(n) logt(n)), N SP ACE(s(n))⊆DEP T H(s2(n)),
DT IM E(t(n))⊆UL-SIZE(t(n) logt(n)), UL-SIZE(tO(1)(n)) =DT IM E(tO(1)(n)), UL-DEP T H(s(n))⊆DSP ACE(s(n))⊆N SP ACE(s(n))⊆UL-DEP T H(s2(n))⊆ DSP ACE(s2(n)), UL-SIZE-DEP T H(2s(n), s(n))⊆DSP ACE(O(s(n))),
P SP ACE=UL-SIZE-DEP T H(2nO(1)(n), nO(1)).
Lets(n), t(n)≥lognsuch thats(n) andt(n) are computable by a deterministic TM in O(s(n))) time, thenAT IM E-SP ACE(t(n), s(n))=UE-SIZE-DEP T H(2O(s(n)), t(n))=
UE∗-SIZE-DEP T H(2O(s(n)), t(n)). Consequently, if t(n) ≥ logn and s(n) ≥ n such that logs(n) is computable by a deterministic TM inO(logs(n))) time, thenUE -SIZE-DEP T H(s(n), t(n))=UE∗-SIZE-DEP T H(s(n), t(n))=AT IM E-SP ACE(t(n),logs(n)).
Ift(n)≥s2(n) thenAT IM E-SP ACE(t(n), s(n)) =UL-SIZE-DEP T H(2O(s(n)), t(n)).
Furthermore we have UE∗-DEP T H(logn) = UE-DEP T H(logn) = AT IM E(logn) = ALOGT IM E ⊆DSP ACE(logn).
Other connections between the above complexity measures of Boolean circuits, TMs, and ATMs, can be found in [6, 17,187,209], oeuvres from which we have gathered the above results. It is easy to observe that the size complexity of a circuit corresponds to the time complexity of a TM, and to the space complexity of an ATM. The depth complexity of a circuit corresponds to the space of a TM, and to the time of an ATM.
The depth is referred to as a parallel time complexity, while the size as the amount of hardware used by that circuit. Recall that the parallel time complexity of a parallel machine is polynomially related to thespace complexity of a sequential machine (thethe parallel computation thesis).
The N C class is defined as the class of all languages (functions or problems) accepted (respectively, computable or solvable) by a family of log-space uniform Boolean circuits with polynomial size, depth bounded by a polynomial in logn, and bounded fan-in gates.
AC is the class of languages (functions or problems) accepted (respectively, computable or solvable) by a family of log-space uniform Boolean circuits with polynomial size, depth bounded by a polynomial in logn, and unbounded fan-in gates [209,213].
Fori≥0 denote by N Ci (ACi) the class of languages accepted by polynomial size log -space uniform Boolean circuits, with depth O(logi n) and fanin 2 (respectively unres -tricted fan-in). We haveN Ci⊆ N Ci+1,i≥1, (ACi⊆ ACi+1,i≥0) andN C =∪i≥1N Ci (AC =∪i≥0ACi). For alli≥0, we haveN Ci⊆ ACi ⊆ N Ci+1. Hence,N C =AC.
Chapter 4. Asymptotic Growth, Computational Models, and Complexity Classes
Depending on the type of the uniformity restrictions, i.e., speedups on time and space imposed on (alternating) TMs simulating a family of circuits, we obtain several N C
“uniform” classes. With respect to these uniformity restrictions several characterizations of theN Cclass in terms of ATM resources are presented in [187,209]. It is proved that for i≥2, allN Ciclasses behave similarly, no matter which uniformity restriction is imposed on circuits, i.e.,UX-N Ci=N Ci =ASP ACE-T IM E(logn,login)⊆DSP ACE(login), whereASP ACE-T IM E(s(n), t(n)) denotes the class of languages acceptable by ATMs in simultaneous space s(n) and time t(n), and X ∈ {UL, UE, UE∗}. For i = 1, the above equality holds only for the UE-uniformity and UE∗-uniformity, more precisely, UE-N C1= UE∗-N C1 = ASP ACE-T IM E(logn,logn) = ALOGT IM E ⊆ UL-N C1 ⊆ DSP ACE(logn). The uniformity condition we are dealing with in this thesis is the UE∗-uniformity.
A similar characterization holds also for theACi classes, wherei≥1, for which we have UL-ACi = ACi = ASP ACE-ALT(logn,login), where ASP ACE-ALT(s(n), a(n)) de-notes the class of languages acceptable by ATMs usinga(n) alternations between existen-tial and universal states and spaces(n). For i= 0, AC0 =AT IM E-ALT(logn,O(1)), while for i= 1,AC1 =ASP ACE-ALT(logn,logn).
The next relations between N C1,AC1,N C2, and (nondeterministic) Turing time and space complexity classes5hold: N C1⊆DSP ACE(logn)⊆N SP ACE(logn) =LOGLIN
⊆LOGCF L⊆ AC1 ⊆ N C2⊆DSP ACE(log2n)⊆ N C ⊆DT IM E(nO(1)) =P.
Note thatN C1 is contained inDSP ACE(logn) no matter which uniformity restriction is imposed to circuits. Hence, N C1 ⊆DSP ACE(logn) “universally” holds. For more characterizations of N Ci, i≥1, in terms of TM and ATM resources, and more results concerning parallel and circuit complexity classes the reader is referred to [6, 7, 26, 187, 209]. Concerning the Chomsky hierarchy it is well known that REG ⊂ N C1, CF L⊂LOGCF L
[208]
⊆ AC1⊆ N C2, and CF L
[187]
⊆ N C2.
Recall that LOGCF L coincides with the class of all decision problems recognized by ATMs using logarithmic space and having polynomial size accepting computation trees [186]. Furthermore, in [208] it is proved that LOGCF L coincides with the class of languages recognizable by uniform semi-unbounded Boolean circuits of polynomial size and logarithmic depth, where semi-unbounded means that the fan-in of all AND-gates is bounded by some constant. Hence, the main difference betweenLOGCF L and AC1 is that LOGCF Lis characterized by Boolean circuits with bounded fan-in AND gates and unbounded fan-in OR gates, while AC1 is characterized by Boolean circuits with unbounded fan-in gates.
5Recall thatLOGCF L(LOGLIN) is the class of decision problems logarithmic space reducible to a context-free (respectively, linear context-free) language.