The input is 2n Boolean variables Ai, Bi, i = 1...n. The outputs are defined by

Question

The input is 2n Boolean variables Ai, Bi, i = 1...n. The outputs are defined by the following system of Boolean equations: W0 = 1 Wi = Wi-1 Lambda (Ai Bi) i = 1,...n Y = Wn Using only 2-input, gates (any of the standard types), construct a circuit that computes Y and all Wi,i = 1...n, for the case n = 4. How many gate delays are encountered in computing Y? Suppose we were only interested in the output Y and not any of the other Zi. Design a circuit where the maximum delay is only three gate delays. (You can only use 2-input gates like before). What would be the delays for the circuits of part (a) and (b) when generalized for n = 8. (You do not have to draw the circuits).

Explanation / Answer

Boolean circuits are one of the prime examples of so-called non-uniform models of computation in the sense that inputs of different lengths are processed by different circuits, in contrast with uniform models such as Turing machines where the same computational device is used for all possible input lengths. An individual computational problem is thus associated with a particular family of Boolean circuits where each is the circuit handling inputs of n bits. A uniformity condition is often imposed on these families, requiring the existence of some resource-bounded Turing machine which, on input n, produces a description of the individual circuit . When this Turing machine has a running time polynomial in n, the circuit family is said to be P-uniform. The stricter requirement of DLOGTIME-uniformity is of particular interest in the study of shallow-depth circuit-classes such as AC0 or TC0. [edit]Polynomial-time uniform A family of Boolean circuits is polynomial-time uniform if there exists a deterministic Turing machine M, such that M runs in polynomial time For all , M outputs a description of on input [edit]Logspace uniform A family of Boolean circuits is logspace uniform if there exists a deterministic Turing machine M, such that M runs in logarithmic space For all , M outputs a description of on input [edit]History Circuit complexity goes back to Shannon (1949), who proved that almost all Boolean functions on n variables require circuits of size T(2n/n). Despite this fact, complexity theorists were unable to prove circuit lower bounds for specific Boolean functions. The first function for which superpolynomial circuit lower bounds could be shown was the parity function, which computes the sum of its input bits modulo 2. The fact that parity is not contained in AC0 was first established independently by Ajtai (1983) and by Furst, Saxe and Sipser (1984). Later improvements by Håstad (1987) in fact establish that any family of constant-depth circuits computing the parity function requires exponential size. Smolensky (1987) proved that this is true even if the circuit is augmented with gates computing the sum of its input bits modulo some odd prime p. The k-clique problem is to decide whether a given graph on n vertices has a clique of size k. For any particular choice of the constants n and k, the graph can be encoded in binary using bits which indicate for each possible edge whether it is present. Then the k-clique problem is formalized as a function such that outputs 1 if and only if the graph encoded by the string contains a clique of size k. This family of functions is monotone and can be computed by a family of circuits, but it has been shown that it cannot be computed by a polynomial-size family of monotone circuits (that is, circuits with AND and OR gates but without negation). The original result of Razborov (1985) was later improved to an exponential-size lower bound by Alon and Boppana (1987). Rossman (2008) shows that constant-depth circuits with AND, OR, and NOT gates require size to solve the k-clique problem even in the average case. Moreover, there is a circuit of size which computes . Raz and McKenzie later showed that the monotone NC hierarchy is infinite (1999). The Integer Division Problem lies in uniform TC0 (Hesse 2001). [edit]Circuit lower bounds Circuit lower bounds are generally difficult. Known results include Parity is not in nonuniform AC0, proved by Ajtai (1983) and by Furst, Saxe and Sipser. Uniform TC0 is not contained in PP, proved by Allender. The classes SP 2, PP[2] and MA/1[3] (MA with one bit of advice) are not in SIZE(nk) for any constant k. While it is suspected that the nonuniform class ACC0 does not contain the majority function, it was only in 2010 that Williams proved that .[4] It is open whether NEXPTIME has nonuniform TC0 circuits. Proofs of circuit lower bounds are strongly connected to derandomization. A proof that P = BPP would imply that either or that permanent cannot be computed by nonuniform arithmetic circuits (polynomials) of polynomial size and polynomial degree.[5] [edit]Complexity classes Many circuit complexity classes are defined in terms of class hierarchies. For each nonnegative integer i, there is a class NCi, consisting of polynomial-size circuits of depth , using bounded fan-in AND, OR, and NOT gates. We can talk about the union NC of all of these classes. By considering unbounded fan-in gates, we construct the classes ACi and AC. We construct many other circuit complexity classes with the same size and depth restrictions by allowing different sets of gates.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.