6.7

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Regarding an AC⁰ circuit of depth d as a depth- $c06-math-1430$ circuit of the type considered in Theorem 6.37, we obtain the following.

Corollary 6.38

This corollary completes the proof of Theorem 6.34. Actually, we can obtain a better lower bound than that in Corollary 6.38 by using the argument in the proof of Theorem 6.37 once again. We leave it as an exercise.

The rest of this section is devoted to the proof of the Switching Lemma.

First, we notice that each AND-OR circuit corresponds to a CNF and each OR-AND circuit corresponds to a DNF. Recall, from Chapter 5, that for any Boolean function f, D(f) denotes the minimum depth of a decision tree computing f. Also recall that in a decision tree computing f, each path from root to a leaf with label 1 corresponds to an implicant. Therefore, if $c06-math-1439$ , then f can be computed by an OR-AND circuit of bottom fan-in at most s. The above observation shows that to prove the Switching Lemma, it suffices to prove that for any AND-OR circuit G with bottom fan-in at most t,

The following is a stronger form.

Lemma 6.39

Proof

Write $c06-math-1453$ . We prove the lemma by induction on w. For w = 0, G ≡ 1; hence, the inequality holds trivially.

Next, we consider w ≥ 1. First, note that

If $c06-math-1459$ , then $c06-math-1460$ . Thus, by the inductive hypothesis, we have

Therefore, it suffices to prove

Let $c06-math-1463$ , where $c06-math-1464$ or $c06-math-1465$ . Let $c06-math-1466$ denote the event that for every $c06-math-1467$ , $c06-math-1468$ and let $c06-math-1469$ denote the event that for every $c06-math-1470$ , $c06-math-1471$ . Then

where

We claim that for $c06-math-1474$ ,

6.7

To prove this, we assume, without loss of generality, that $c06-math-1476$ . Note that for ρ with $c06-math-1478$ , $c06-math-1479$ implies that there exists a Boolean assignment σ on variables in J with σ ≢ 0 such that $c06-math-1483$ . (Indeed, if this is not true, then we can build a decision tree for $c06-math-1484$ of depthless than s by concatenating each small tree for $c06-math-1486$ to a balanced binary tree of depth $c06-math-1487$ , each path corresponding to a σ. This would be a contradiction to the assumption of $c06-math-1489$ .) Let ρ₁ and ρ₂ be assignments on $c06-math-1492$ and $c06-math-1493$ induced from ρ, respectively. Let F_J be the function F with the restriction that all variables in $c06-math-1497$ are assigned 0. Then, it is easy to see that the condition $c06-math-1498$ is equivalent to the condition $c06-math-1499$ . Thus, by the inductive hypothesis, we have

(In the above, we represented each assignment σ on variables in J by a string in $c06-math-1503$ .) The above proves that (6.7) holds.

Next, we want to show

6.8

Note that

because requiring some variables not to be assigned with value 0 or 1 cannot increase the probability that a function is determined. Thus, we have

Now, observe that the condition $c06-math-1507$ means that $c06-math-1508$ is either 0 or $c06-math-1509$ for all literals y_i with $c06-math-1511$ . Thus, we get

This proves (6.8).

Now, how do we use (6.7) and (6.8) to get an upper bound for $c06-math-1513$ ? A simple way is just to use $c06-math-1514$ as an upper bound for b_J. In this way, we obtain

Now, recall that $c06-math-1517$ and so

which is close to and less than $c06-math-1519$ . Also recall that α was defined to be $c06-math-1521$ , which satisfies $c06-math-1522$ . Thus, we get

A more clever way to use (6.8) employs the inversion formula to get a better bound for q, which, in turn, improves the bound of Corollary 6.38. We leave the detail as an exercise to the reader (see Exercises 6.16 and 6.17).

6.7 P-Completeness

From the discussion in Section 6.4, we see that the question of whether $c06-math-1525$ is a major open question in complexity theory. Intuitively, this question asks whether all polynomial-time computable problems (representing problems with efficient sequential algorithms) can be recognized by circuits of poly-log depth (representing efficient parallel algorithms). Thus, it is a question of interest not only to the theoreticians who are concerned with the time/space tradeoff but also to the algorithm designers who are interested in finding efficient parallel algorithms.

Similar to the study of the P versus NP question, we can use the notion of P-completeness to demonstrate that some problems are the hardest problems that can be solved in polynomial time by sequential machines. If a problem A is shown to be P-complete, then it is in NC if and only if $c06-math-1531$ . Thus, this fact demonstrates that A is probably not in NC under the (commonly believed) assumption that $c06-math-1534$ .

Definition 6.40

Our first P-complete problem is the following:

Theorem 6.41

Proof

Clearly, the problem CVP is in P because each Boolean operation only takes a constant time to evaluate. To show its P-completeness, we need to prove that every language in P is logarithmic-space reducible to CVP. Actually, such a reduction is already done in the proof of Theorem 6.4. We constructed, in that proof, for each polynomial-time DTM M and each input x, a circuit C_x (with no variable) such that M accepts x if and only if the output value of circuit C_x equals 1. The only thing we need to check here is that the construction of C_x can be done in space $c06-math-1552$ . This can be seen from the fact thatC_x is constructed through connecting many copies of a constant-size circuit computing a fixed mapping (called f in that proof) that depends only on M and the fact that the connection is not only independent of x but actually independent of M.

Some special subproblems of CVP remain P-complete. The following are two examples.

Corollary 6.42

Proof

A circuit C is a planar circuit if it can be laid out in the plane.

Corollary 6.43

Proof

**Figure 6.8** A planar circuit for $c06-math-1565$ .

**Figure 6.10** A network N and a flow f.

The next example is the odd maximum flow problem. A network $c06-math-1568$ is a digraph $c06-math-1569$ with two specific vertices, the source s and the sink t, and a positive-integer capacity $c06-math-1572$ for each edge (i,j) (see Figure 6.10). The source s has no incoming edge and the sink t has no outgoing edge. A flow in the network is an assignment of a nonnegative integer value $c06-math-1576$ to each edge (i,j) such that $c06-math-1578$ and that for each vertex other than the source and the sink the sum of the assigned values for incoming edges equals the sum of the assigned values for outgoing edges. The value of a flow f equals the sum of the assigned values $c06-math-1580$ for all outgoing edges at the source s (or the sum of the assigned values $c06-math-1582$ for all incoming edges at the sink t).

Theorem 6.44

Proof

First, we need to show that OMF belongs to P. To do so, it suffices to show that the maximum flow of any network $c06-math-1586$ can be computed in polynomial time. There are a number of efficient algorithms for computing the maximum network flow. The reader is referred to any standard algorithm textbook for a complete proof, for instance, Cormen et al. (1990).

Now, we show that the problem MCV is logarithmic-space reducible to the problem OMF. To do so, for each monotone circuit C with variables already assigned values, we construct a network $c06-math-1588$ such that the output value of circuit C is 1 if and only if the value of the maximum flow of the network N is odd.

First, we assume that C has the following two properties: (a) every OR gate has fan-out at most two and (b) the output gate is an OR gate. It is easy to see that a circuitC that does not have these two properties can be transformed to one having the properties by adding some new OR-gates.

Now, for the circuit C with the two properties, we construct a network N_C based on the circuit C as follows:

We label the output gate with 0 and other vertices in the circuit C, consecutively, in the topological order starting from 1. By the topological order, we mean that no vertex gets an input from another one with a smaller label.
For any edge coming out of the vertex with label i, we assign capacity 2ⁱ to the edge.
We add two special vertices, the source s and the sink t, to the circuit. We connect the source s to every variable assigned with value 1 and connect the output OR gate and each AND gate to the sink t.
For any edge from s to a variable with label i, we assign capacity $c06-math-1605$ to it, where d is the number of outputs of the variable. For any edge from an AND gate to the sink t, its capacity is assigned so that the total capacity of incoming edges to this gate is equal to the total capacity of outgoing edges from this gate. The edge from the output OR gate to t has capacity 1.

It is clear that the construction of the network N_C can be done in logarithmic space. We show an example of the construction in Figure 6.11. A gate or a variable in the network N_C is said to be false if its value is 0 and is said to be true if its value is 1. Consider all edges from s and true vertices in N_C to t and false vertices in N_C. They form a cut from s to t. We claim that the value of the maximum flow of N_C equals the total capacity of this cut. (In Figure 6.11, this value is equal to 33.)

Before proving our claim, we observe that the correctness of the reduction follows from the claim. Indeed, all the values of the capacity are even numbers except one, which is the capacity of the edge from the output gate of C to the sink t. If the output value of C is 1, then this edge belongs to the cut and, hence, the maximum flow is odd by our claim. If the output value of C is 0, then this edge is not in the cut and the maximum flow is even.

It is left to prove our claim. To do so, we first show that the cut is a minimal cut. We note that a false variable has no incoming edge and a false OR gate cannot have an incoming edge from any true vertex. Thus, only false AND gates can receive incoming edges from any true vertex. For each of these false AND gates, there is an edge directly connecting it to the sink t. Moreover, the circuit C is monotone and, hence, every true gate is reachable from a true variable through a path consisting of only true gates. Therefore, removing any edge from the cut will result in a path from s to t, that is, the cut is minimal.

Next, we modify the network N_C by adding an imaginary edge from each OR gate to the source s, with the capacity equal to the total capacity of the incoming edges to the OR gate (see Figure 6.12). With this modification, it suffices to prove the existence of a flow f on the modified N_C such that all edges in our cut are full (i.e., having $c06-math-1631$ ) and that no edge from t or a false vertex to s or a true vertex is assigned with a positive value. Such a flow f can be found as follows:

For each edge (s,i), set $c06-math-1636$ .
For each true variable vertex i, set $c06-math-1638$ for all j. For each false variable vertex i, set $c06-math-1641$ for all j.
If f has been set for all incoming edges of a gate, then f is set for its outgoing edges as follows: For each true OR gate i, set $c06-math-1646$ for $c06-math-1647$ and $c06-math-1648$ . For each false OR gate i, set $c06-math-1650$ for all j. For each true AND gate i, set $c06-math-1653$ for all j. For each false AND gate i, set $c06-math-1656$ and $c06-math-1657$ for all $c06-math-1658$ .

It is not hard to verify that the flow f is well defined. In addition, f satisfies the following properties:

If i is a false vertex, then for any $c06-math-1662$ , $c06-math-1663$ .
If i is a true vertex, then for any $c06-math-1665$ , $c06-math-1666$ .

From property (b), we know that every edge from s or a true vertex to t or a false vertex is full. From property (a), we see that the flow passing through an imaginary edge does not pass through any false vertex. Therefore, if we remove the imaginary edges and reduce the corresponding flow in the path, then the flow in each edge from s or a true vertex to t or a false vertex is still full. Moreover, property (a) also implies that all edges from false vertices to true vertices have zero flow. Thus, the total value over the cut is equal to the value of the flow. This completes the claim and, hence, our proof.

**Figure 6.11** Reduction from MCV to OMF.

**Figure 6.12** The maximum flow for N_C with the imaginary edges. The dark vertices are the *false* ones.

We remark that there is a rich collection of P-complete problems in literature. As we mentioned before, these P-complete problems are not in NC unless $c06-math-1671$ . In addition to these P-complete problems, there also exist a number of problems in P for which one does not know whether it is P-complete or in NC. The following is an example.

A comparator gate has two output wires. In the first one, it outputs $c06-math-1672$ and in the second one, it outputs $c06-math-1673$ , where x and y are its two inputs. The problem COMPARATOR CIRCUIT VALUE is the circuit value problem on circuits consisting of comparator gates. Again, it is easy to see that this problem is in P. It is, however, not known whether it is P-complete. All problems that are logarithmic-space reducible to this problem form a complexity class, called CC. It is known that $c06-math-1676$ but not known whether the inclusions are proper or not.

6.8 Random Circuits and RNC

A random circuit is a circuit with random variables. Let $c06-math-1677$ be a circuit of variables x₁, $c06-math-1679$ , x_n and y₁, $c06-math-1682$ , y_m, where y₁, $c06-math-1685$ , y_m are random variables with the distribution satisfying

Let a and b be two real numbers satisfying $c06-math-1690$ . We say a language $c06-math-1691$ is(a,b)-accepted by the random circuit $c06-math-1693$ with n input variables if for all $c06-math-1695$ , we have $c06-math-1696$ and for all $c06-math-1697$ , we have $c06-math-1698$ .

In the following, we show that a random circuit can be simulated by a deterministic circuit with an increase of a constant number in depth and a polynomial factor in size. Let C be a random circuit and C₁, C₂, $c06-math-1702$ , C_k be copies of C with different random variables. Define two new random circuits $c06-math-1705$ and $c06-math-1706$ .

Lemma 6.45

Proof

Theorem 6.46

Proof

Assume that the random circuit C has size s, depth d, and $c06-math-1728$ , (1 + (log n)^−k)/2) accepts A. Note that

and

Thus, by Lemma 6.45, we know that circuit $c06-math-1732$ , n⁻²(1 + 2(log n)^−k+1)) accepts A.⁵ Next, we consider the circuit $c06-math-1737$ . We note that, for sufficiently large n,

Also, note that $c06-math-1740$ . Thus, for sufficiently large n,

Thus, circuit $c06-math-1743$ accepts A. Note that C₂ is a depth- $c06-math-1746$ circuit of size $c06-math-1747$ , which is bounded by a polynomial in s and n. Now we apply the above construction for k − 2 more times, and we obtain a random circuit Q of depth $c06-math-1752$ and polynomial size that $c06-math-1753$ , (1 + (log n)⁻¹)/2) accepts A. Using a similar argument, we can show that the circuit

$c06-math-1756$ accepts A. (See Exercise 6.32.) Now, we have found a random depth- $c06-math-1758$ circuit Q^′ of size polynomial in s and n, which $c06-math-1762$ accepts A. Thus, for any input x of length n, Q^′ makes a mistake with probability at most $c06-math-1767$ . Therefore, the probability that Q^′ makes a mistake on at least one input is at most $c06-math-1769$ . Thus, there exists an assignment for random variables such that, with this assignment, Q^′ accepts A without mistake. The theorem is proved by noticing that every random circuit with an assignment for its random variables is simply a deterministic circuit.

The following is an application of this result to the lower bound of the parity function. We say a (deterministic) circuit C c-approximates a function f if $c06-math-1775$ for at least $c06-math-1776$ inputs x.

Theorem 6.47

Proof

We now define a new complexity class based on random circuits. A language is in RNC if there is a uniform family of NC circuits, with polynomially many random variables, that $c06-math-1793$ accepts the language. It is obvious that $c06-math-1794$ . It is not known whether the inclusion is proper. Note that Theorem 6.46 showed that a language in RNC can be computed bya family of polynomial-size deterministic circuits. However, the proof was nonconstructive and so this family is a nonuniform-NC family of circuits. It is not known whether there is a way to find the deterministic circuits uniformly.

It is known that $c06-math-1795$ , but it is not clear whether $c06-math-1796$ . (It is obvious that $c06-math-1797$ , where R is the class of languages accepted by polynomial-time probabilistic TMs with bounded errors on inputs in the language and no error on inputs not in the language see Chapter 8). On the other hand, it is unlikely that $c06-math-1799$ , and so, a problem is probably not P-hard if it is in RNC. The following is an example.

It is well known that PM is polynomial-time solvable (Lawler, 1976). Before we show that PM is in RNC, we first prove a probabilistic lemma, which will also be used in Chapter 9.

Lemma 6.48

Proof

We call an element x_i in S bad if it is in some minimum-weight subset T in $c06-math-1825$ but notin all of them. Clearly, a bad element exists if and only if the minimum-weight subset is not unique.

What is the probability that an element is bad? Consider an element x_i in S. Suppose that all weights are chosen except the one for element x_i. Let $c06-math-1829$ be the smallest total weight among sets T in $c06-math-1831$ not containing x_i and $c06-math-1833$ the smallest total weight among all sets T in $c06-math-1835$ containing x_i but not counting the weight of x_i. We claim that x_i is bad if and only if the weight w_i of x_i is chosen to be $c06-math-1841$ . (If $c06-math-1842$ , then x_i cannot be bad.)

In fact, if $c06-math-1844$ , then the minimum-weight subsets in $c06-math-1845$ do not contain x_i and, hence, x_i is not bad. If $c06-math-1848$ , then every minimum-weight subset T in $c06-math-1850$ contains x_i and, hence, x_i is not bad. If $c06-math-1853$ , then there exists a minimum-weight subset T₁ in $c06-math-1855$ containing x_i, as well as a minimum-weight subset T₀ in $c06-math-1858$ not containing x_i, and so x_i is bad.

As there are 2n choices for the weight w_i of x_i and at most one choice can make the element x_i bad and as the weights $c06-math-1865$ and $c06-math-1866$ are chosen independently of weight w_i, the probability that x_i is bad is at most $c06-math-1869$ . Therefore, the probability that no element is bad is at least $c06-math-1870$ . This completes the proof of the lemma.

Theorem 6.49

Proof

To design a randomized algorithm for PM, we randomly choose weights from 1 to $c06-math-1871$ for edges in the input bipartite graph G where E is the edge set of G. The Isolation Lemma states that if there is a perfect matching then, with probability at least 1/2, the minimum-weight perfect matching is unique.

Now, for each set of randomly chosen weights $c06-math-1875$ on edges $c06-math-1876$ , compute the determinant of the matrix $c06-math-1877$ ( $c06-math-1878$ if $c06-math-1879$ ):

where π ranges over all permutations on $c06-math-1882$ and $c06-math-1883$ if π is an even permutation and it is −1 if π is an odd permutation. Note that $c06-math-1887$ if and only if the permutation π defines a perfect matching $c06-math-1889$ . Thus, if the determinant of A is nonzero, then G must have a perfect matching. In addition, if with weights $c06-math-1892$ the minimum-weight perfect matching is unique, say its weight is w^∗, then

for some integer c; hence, the determinant of A must not equal zero. In other words, if G has no perfect matching, then $c06-math-1898$ , and if G has a perfect matching, then $c06-math-1900$ .

Finally, we note that it is well known that $c06-math-1901$ can be computed in NC² (see, e.g., Cook (1985)). This completes the proof of the theorem.

Exercises

6.1 Design a monotone Boolean circuit with at most six gates and with fan-in at most three that computes the following Boolean function:

6.2 Construct a Boolean circuit computing the function f_con on graphs of n vertices (defined in Section 5.2). How many gates do you need?

6.3 Design a multioutput circuit that combines two levels of a branching program into one.

6.4 Prove that for a monotone increasing Boolean function f,

Using this formula, find an upper bound for C(f) when f is a monotone increasing Boolean function.

6.5

Prove that any planar circuit that computes the product of two n-bit binary integers must have at least $c06-math-1911$ vertices.
Prove that any planar circuit that computes the product of two $c06-math-1912$ Boolean matrices must contain at least $c06-math-1913$ vertices for some constant c.

6.6 Show that if $c06-math-1915$ , then $c06-math-1916$ .

6.7 Let x and y be Boolean variables, and let $c06-math-1919$ and $c06-math-1920$ . Show that both $c06-math-1921$ and $c06-math-1922$ can be represented monotonely from x, y, u, and v (with only AND and OR operations).

6.8 The inverter is the collection I_n of functions $c06-math-1928$ of variables $c06-math-1929$ such that $c06-math-1930$ . Design a circuit with n inputs and n outputs computing I_n with at most $c06-math-1934$ negation gates.

6.9

Show that the problem of multiplying a given sequence of integers is in NC¹.
Show that the problem of multiplying a given sequence of permutations in S_n is in LOGSPACE.

6.10 Suppose that $c06-math-1937$ for some class $c06-math-1938$ that contains P as a subclass. Show that $c06-math-1940$ if and only if there exist $c06-math-1941$ and $c06-math-1942$ such that

6.11 Prove that P/poly contains nonrecursive sets.

6.12 Prove Propositions 6.9 and 6.10.

6.13 Let log be the class of all functions h from integers to strings over {0,1} such that $c06-math-1946$ for some constant c > 0. Prove the following statements:

$c06-math-1948$ .
$c06-math-1949$ .
$c06-math-1950$ .
$c06-math-1951$ .

6.14 A function f is called a slice function if for some positive integer k,

Show that a general circuit computing a slice function can be converted into a monotone circuit by adding only a polynomial number of extra gates.
Show that it is NP-complete to determine whether a given graph G with 2n vertices has a clique of size n.
Show that it is also NP-complete to determine whether a given graph with 2n vertices has a clique of size n or at least $c06-math-1960$ edges.
Define a sequence of slice functions that represents the above NP-complete problem.

6.15 Let G be an AND-OR circuit with bottom fan-in 1 and ρ a random restriction from R_p. Prove that the probability that $c06-math-1964$ cannot be switched to an OR-AND circuit with bottom fan-in less than s is bounded by q^s where $c06-math-1967$ .

6.16 We refer to the proof of Lemma 6.39. Prove that there exist values $c06-math-1968$ for $c06-math-1969$ such that

6.17 Prove that for sufficiently large n, the parity function p_n cannot be computed by a depth-d circuit of size at most $c06-math-1974$ .

6.18 Let $c06-math-1975$ denote the maximum size of minterms of a Boolean function f. Let G be an AND-OR circuit with bottom fan-in t. Let ρ be a random restriction from R_p. Then for any Boolean formula F and s > 0, we have

where q satisfies

6.19 Let $c06-math-1986$ be a partition of variables in a circuit. Let $c06-math-1987$ be a probability space of restrictions defined as follows: For each B_i, first randomly pick one value, denoted by s_i, from $c06-math-1990$ with probabilities

Then for every $c06-math-1992$ , define

For each $c06-math-1994$ , define a (deterministic) restriction $c06-math-1995$ as follows: For each B_i with $c06-math-1997$ , let V_i be the set of all variables in B_i, which are given value $c06-math-2000$ . The restriction $c06-math-2001$ selects, for each B_i, a variable y_i in V_i and assigns value $c06-math-2005$ to y_i and value 1 to all other variables in V_j. Let G be an AND-OR circuit with bottom fan-in $c06-math-2009$ . Then from a random restriction ρ from $c06-math-2011$ , the probability that $c06-math-2012$ is not equivalent to an OR-AND circuit with bottom fan-in $c06-math-2013$ is bounded by q^s where $c06-math-2015$ .

6.20 Let $c06-math-2016$ be the depth-d levelable circuit that has the following structure: (a) $c06-math-2018$ has a top OR gate, (b) the fan-in of all gates is n, (c) $c06-math-2020$ has exactly n^d variables, each variable occurring exactly once in a leaf in the positive form. Let the function computed by $c06-math-2022$ be $c06-math-2023$ . Prove that, for any k > 0, there exists an integer n_k such that if a depth-d circuit D computes the function $c06-math-2028$ , with $c06-math-2029$ , which has bottom fan-in $c06-math-2030$ and fan-ins $c06-math-2031$ for all gates at level 1 to d − 2 (and with fan-ins of gates at level d − 1 unrestricted), then D must have size $c06-math-2035$ for some constant c > 0. [Hint: Use the random restriction of the last exercise.]

6.21 Let $c06-math-2037$ be a collection of AND-OR circuits of bottom fan-in $c06-math-2038$ . Then for a random restriction ρ from $c06-math-2040$ , the probability that every $c06-math-2041$ can be switched to an OR-AND circuit with bottom fan-in $c06-math-2042$ is greater than 2/3, if $c06-math-2043$ , where $c06-math-2044$ .

6.22 Show that the graph accessibility problem on undirected graphs is in LOGSPACE.

6.23 A language A is said to be NC-reducible to another language B if there exists a mapping f from strings to strings computable by a uniform family of NCⁱ circuits for some i > 0 such that $c06-math-2050$ if and only if $c06-math-2051$ . Prove the following:

If A is NC-reducible to B and B is NC-reducible to C, then A is NC-reducible to C.
If A is NC-reducible to B and B is in NC, then A is in NC.

6.24 Prove that NLOGSPACE $c06-math-2062$ .

6.25 Prove $c06-math-2063$ by designing and combining three logarithmic-space algorithms that perform the following tasks:

Generate a circuit in the given uniform family of circuits with logarithmic depth.
Transform the generated circuit to an equivalent circuit with all outdegree one (i.e., a tree-like circuit).
Evaluate the tree-like circuit.

6.26 A Boolean circuit is called an AM2 circuit if, in the circuit, (a) on any path from an input to the output the gates are required to alternate between OR and AND gates, (b) inputs are connected to only OR gates, (c) the output also comes from an OR gate, and (d) every gate has fan-out at most two. The problem AM2 CIRCUIT VALUE is defined as follows: Given an AM2 circuit and an assignment to its variables, determine whether the circuit value equals 1. Prove that AM2 CIRCUIT VALUE is P-complete.

6.27 An NAND gate can be obtained by putting a NOT gate at output of an AND gate. An NAND circuit is a Boolean circuit consisting of only NAND gates. The NAND CIRCUIT VALUE problem is to determine, for a given NAND circuit and a given assignment to its variables, whether the circuit value equals 1. Prove that NAND CIRCUIT VALUE is P-complete.

6.28 Show that the following problem is P-complete: Given a network $c06-math-2064$ and a nonnegative integer k, determine whether the maximum flow of N has value $c06-math-2067$ .

6.29 Prove than if a bipartite graph has a perfect matching, then a perfect matching can be found in RNC.

6.30 Show that if $c06-math-2068$ , then $c06-math-2069$ .

6.31 An r-circuit is a circuit with AND and OR gates of fan-in two and at most r negation gates. Let $c06-math-2072$ denote the size of the smallest r-circuit computing f. Show that for any Boolean function f of n variables,

6.32 Prove that if a random circuit $c06-math-2078$ accepts A, then $c06-math-2080$ accepts A.

6.33 Show that if $c06-math-2082$ , then $c06-math-2083$ , where p_n is the parity function of n variables.

6.34 Show that the problem of finding the determinant of an integer matrix is in NC².

Historical Notes

Shannon (1949) first considered the circuit size of a Boolean function as a measure of its computational complexity. Lupanov (1958) showed the general upper bound $c06-math-2087$ . Fischer (1974) proved the existence of Boolean functions with circuit complexity $c06-math-2088$ . An explicit language with circuit complexity $c06-math-2089$ was found by Blum (1984). See Dunne (1988) and Wegener (1987) for more complete treatment on Boolean circuits. Karp and Lipton (1982) studied the class of sets having polynomial-size circuits and obtained a number of results on P/poly, including Theorem 6.11 and Exercise 6.13. Sparse sets are first studied in Lynch (1975) and Berman and Hartmanis (1977). They are further studied in Chapter 7. For the sets with succinct descriptions (such as sets with polynomial-size circuits), see the survey paper of Balcázar et al. (1997).

Razborov (1985a) obtained the first superpolynomial lower bound $c06-math-2090$ for the size of monotone circuits computing the function $c06-math-2091$ . The exponential lower bound of Theorem 6.15 was given by Alon and Boppana (1987). Razborov (1985b) showed that the perfect matching problem for bipartite graphs also requires monotone circuits of superpolynomial size. Tardos (1988) showed an exponential lower bound for another problem in P. Berkowitz (1982) introduced slice functions and showed that circuits computing slice functions can be converted into monotone circuits with a polynomial number of additional gates (see Exercise 6.14). He also pointed out that there exist NP-complete slice functions. Yao (1994) adapted Razborov's technique to show that the connectivity requires depth $c06-math-2092$ in a monotone circuit. Goldman and Hastad (1995) improved the bound to $c06-math-2093$ . There are also many references on circuits with limited number of negation gates; see, for instance, Beals et al. (1995).

The class NC was first defined by Nick Pippenger (1979); indeed, the term NC was coined by Cook to mean “Nick's Class.” There are, in literature, a number of models for parallel computation, including PRAMs (Fortune and Wyllie, 1978), SIMDAGs (Goldschlager, 1978),Alternating Turing machines (Chandra et al., 1981), and vector machines (Pratt et al., 1974). See, for instance, van Emde Boas (1990) for a survey of these models and their relations to the Boolean circuit model. The fact that LOGSPACE and NLOGSPACE are in NC² was proved by Borodin (1977). Exercise 6.9 is from Beame et al. (1984), Cook and McKenzie (1987), and Immerman and Landau (1989). Exercise 6.22 is from Reingold (2008).

The fact that the parity function is not in AC⁰ was first proved by Furst et al. (1984) and Ajtai (1983). They proved that the parity function requires constant-depth circuits of superpolynomial size. Yao (1985) pushed up this lower bound to exponential size. Hastad (1986a, 1986b) simplified Yao's proof and proved the first Switching Lemma. Exercises 6.18 and 6.19 are from Hastad (1986a, 1986b). The idea of using the inversion formula in the proof of the Switching Lemma was initially proposed by Moran (1987). However, in his proof, he used $c06-math-2098$ instead of D(G), so that the inequality corresponding to (6.7) was incorrect. The current idea of using D(G) was suggested by Cai (1991). For other applications of the random restriction and the Switching Lemma, see, for instance, Aiello et al. (1990) and Ko (1989b). Exercise 6.21 is from Ko (1989a). Smolensky (1987) extended Yao's result to modulo functions. Fortnow and Laplante (1995) (see also section 6.12 of Li and Vitanyi (1997)) offer a different proof of Hastad's Lemma using the notion of Kolmogorov complexity.

P-complete problems were first studied by Cook (1973b). The P-completeness of the the problem CVP was established by Ladner (1975b). The circuit value problem for monotone and planar circuits was studied by Goldschlager (1977). Exercise 6.5 is from Lipton and Tarjan (1980). The problem OMF is proved to be P-complete by Goldschlager et al. (1982). Greenlaw et al. (1995) included a list of hundreds of P-complete problems. Mayr and Subramanian (1989) defined the class CC and studied its properties.

Random circuits were studied by Ajtai and Ben-Or (1984). Feather (1984) showed that finding the size of the maximum matching is in RNC. Karp et al. (1986) found the first RNC algorithm for finding the maximum matching. Our proof using the Isolation Lemma is from Mulmuley et al. (1987). The fact that the determinant of an integer matrix can be computed in NC was first proved by Csansky (1976) and Borodin, Cook and Pippenger (1983). See Cook (1985) for more discussions about the problem of computing integer determinants.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 6.7

Create new playlist

Sign In

Sign Up

Corollary 6.38

Lemma 6.39

Proof

6.7 P-Completeness

Definition 6.40

Theorem 6.41

Proof

Corollary 6.42

Proof

Corollary 6.43

Proof

Theorem 6.44

Proof

6.8 Random Circuits and RNC

Lemma 6.45

Proof

Theorem 6.46

Proof

Theorem 6.47

Proof

Lemma 6.48

Proof

Theorem 6.49

Proof

Exercises

Historical Notes

Table of Contents for
6.7