Kozen D.C. Theory of Computation

Подождите немного. Документ загружается.

Lecture 30

Circuit Lower Bounds and Relativized

PSPACE = PH

In this lecture and the next we study lower bounds for families of Boolean

circuits of constant depth and their application to relativized complexity.

These results are interesting not only from the point of view of the design

and analysis of algorithms, but also for their consequences regarding the

structure of the polynomial-time hierarchy.

The ﬁrst lower bound results for constant-depth circuits were obtained

by Furst, Saxe, and Sipser [46] and Ajtai [5] in the mid-1980s. They showed

the nonexistence of circuit families of constant depth and polynomial size

for the Parity function and other Boolean functions. A series of later

papers established explicit superpolynomial lower bounds on the size of

constant-depth circuits for some of these functions, culminating in a nearly

optimal result of H˚astad [56]. A detailed history and exposition of this work

can be found in the survey article of Boppana and Sipser [20].

In this lecture we introduce the complexity class AC

of Boolean func-

tions that can be computed by a family of constant-depth, polynomial-size

circuits of unbounded indegree. We then show that a suﬃciently strong

superpolynomial lower bound on the size of constant-depth circuits for

Parity implies the existence of an oracle separating PSPACE from PH .

This relationship was ﬁrst observed by Furst, Saxe, and Sipser [46] and

Circuit Lower Bounds and Relativized PSPACE = PH 193

was one of the primary motivations for the study of the complexity of

constant-depth circuits.

At the end of this lecture, we set up the machinery needed to prove that

Parity is not in AC

, then dive into the details in Lecture 31. Our proof is

a minor variant of the original proof of Furst, Saxe, and Sipser [46], which

introduced the idea of a random partial valuation. This was one of the ﬁrst

applications of probability to lower bound proofs, although the conclusion

is not probabilistic at all.

Unfortunately, this result is not strong enough to obtain an oracle sepa-

rating PSPACE from PH . Stronger bounds achieving separation were ﬁrst

obtained by Yao [126] and H˚astad [56]. A complete proof of H˚astad’s result

is given in Supplementary Lecture H.

Parity and the Class AC

A parity function is a Boolean function {0, 1}

→{0, 1} whose value

changes whenever any one of its inputs changes. There are exactly two

such functions for any n, namely the function that computes the mod-2

sum of its inputs and the function that computes the complement of this

value. We refer to these functions collectively as Parity.

We have studied uniform families of Boolean circuits previously in Lec-

tures 11 and 12. Recall that the complexity class NC discussed in those lec-

tures was deﬁned in terms of logspace-uniform families of Boolean circuits

of polylog depth and polynomial size. There was also a degree restriction:

the gates of the circuits were binary ∧ and ∨ or unary ¬ gates.

To deﬁne the class AC

, we restrict to constant depth, but we relax

the degree restriction to allow ∧ and ∨ gates to compute the conjunction

and disjunction, respectively, of an unbounded number of Boolean inputs

in one step. (It is easy to show that no function of a single output that

depends on all its inputs can be computed by a circuit of bounded degree

in o(log n)depth.)

For example, for ﬁxed k, the Boolean function that returns 1 if at least

k of its inputs are 1 can be computed by an AC

circuit of size

+1 and

depth 2 as



S ⊆{x

,... ,x

}

|S | =k



As with NC , the oﬃcial deﬁnition of AC

includes a uniformity con-

dition. However, we are concerned here only with lower bounds, and any

lower bound that we can derive for nonuniform circuits holds a fortiori for

uniform circuits, so we can conveniently ignore this issue.

We can also assume without loss of generality that all negations are ap-

plied to inputs only, and that the gates are arranged in levels with inputs

194 Lecture 30

and their negations at level 0 and conjunctions and disjunctions strictly

alternating level by level. The assumption regarding negations can be en-

forced by constructing the dual circuit as in Lecture 12. The assumption

regarding the alternation of ∧ and ∨ can be enforced by the addition of

dummy gates if necessary without signiﬁcantly increasing the depth or size.

Separating PH from PSPACE

The main result of this lecture is that a suﬃciently strong lower bound on

the size of constant-depth circuits for Parity implies the existence of an

oracle separating PSPACE from the polynomial-time hierarchy.

Theorem 30.1 (Furst, Saxe, and Sipser [46]) Suppose that there exists no family of cir-

cuits for Parity of depth d and size 2

(log n)

for any constants c and d.

Then there exists an oracle A ⊆{0, 1}

∗

such that PH

= PSPACE

Proof. Let A ⊆{0, 1}

∗

.Thecharacteristic function of A, also denoted

by A, is the function

A(x)

def



1, if x ∈ A

0, otherwise.

Deﬁne the set

P (A)

def

= {x ∈{0, 1}

∗



y∈A, |y |=|x |

A(y) ≡ 1(mod2)}

= {x ∈{0, 1}

∗

| the number of strings in A of length |x|

is odd}.

For the set A shown in the diagram below, P(A) would contain all strings

of length 4, as the number of strings of length 4 in A is 9, which is odd.





0110100010111101

{0, 1}

∩ A

There is an oracle Turing machine that for any oracle A accepts the

set P (A) and runs in linear space. The machine on input x simply steps

through all the strings of length |x| in some order, querying the oracle on

Circuit Lower Bounds and Relativized PSPACE = PH 195

each one and keeping track of the number of positive responses mod 2.

Thus P(A) ∈ PSPACE

for any A.

Now for any oracle machine M , let us say that M is correct on n if,

supplied with any oracle A and input x of length n, M accepts x iﬀ x ∈

P (A); that is, for any A and x of length n, M correctly computes the parity

of the number of elements of A of length n. We argue that there can be

no polynomial-time Σ

-machine that is correct on all but ﬁnitely many n,

otherwise we could build a family of circuits violating the assumption of

the theorem.

Suppose for a contradiction that there were such a machine M.On

inputs of length n, M runs in time n

and makes at most d alternations of

universal and existential states along any computation path, where c and d

are constants. The computation tree of M on any input can be divided into

d levels such that the conﬁgurations on any level are either all universal

conﬁgurations or all existential conﬁgurations, and the ﬁrst level contains

only existential conﬁgurations.



∧

∨

∧

∨

We can assume without loss of generality that on input x, M never

queries its oracle on any string that is not the same length as x, because

these strings are irrelevant in determining whether x ∈ P (A). If M does so,

we can build another machine N that simulates M, supplying an arbitrary

truth value whenever M would attempt to query the oracle on a string of

the wrong length. The machine N must be correct on n if M is.

Now we build a parity circuit C

for each n on which M is correct.

The circuit C

is built from the computation tree of N on input 0

and

all possible oracles A. The gates of the circuit are the conﬁgurations of

N on input 0

; there are at most 2

of these for some constant c.The

inputs are Boolean variables representing the truth values of A(y), |y | = n.

There are 2

of these. The output gate is the start conﬁguration of N .An

oracle query just reads the input gate corresponding to the query string.

An existential conﬁguration α becomes an ∨-gate of unbounded indegree,

taking its inputs from all the universal or halting conﬁgurations β for which

there exists a computation path α → β in which all conﬁgurations, except

possibly the last, are existential. A universal conﬁguration becomes an ∧-

gate of unbounded indegree in a similar fashion. Thus we have ﬂattened

196 Lecture 30

each existential and each universal level of the computation tree into a

circuit of depth 1:



ssss

ssssssss





∨

∨∨

∨∨∨∨

⇒

ssssssss







∨

The resulting circuits C

are of depth d and size 2

,have2

inputs,

and compute the parity of their inputs. In terms of the number of inputs

m =2

, the size is 2

(log m)

. We only have circuits whose input sizes are

powers of 2, but we can obtain parity circuits for other input sizes m by

taking the circuit for the next larger power of 2 and setting all but m inputs

to 0. Thus we have a family of circuits of constant depth d and size 2

(log m)

for Parity. This contradicts the assumption of the theorem.

Now we use this to construct an oracle A separating PH from PSPACE .

We know from the contradiction that the premise that M was correct on all

but ﬁnitely many n was erroneous. Thus there must exist arbitrarily large n

on which M is incorrect. Proceeding by diagonalization, let M

,... be

a list of all polynomial-time Σ

machines for all constants d.Weconstruct

A in stages. At the ith stage, let n

be a number larger than any number

chosen at any earlier stage such that M

is incorrect on n

.LetB

be an

oracle on which M

gives the incorrect answer on input 0

,letA

= B

∩

{0, 1}

,andletA =



.ThenM

with oracle A is also incorrect on

, because it receives the same responses from A as from B

.ThusnoM

computes P (A). 2

Lower Bounds for Parity

In Lecture 31, we present the result of Furst, Saxe, and Sipser [46] that

Parity is not in AC

. The proof is based on the observation that if we

set some of the inputs of a parity circuit to 0 or 1, the resulting circuit still

computes a parity function, albeit on fewer inputs. If we have a circuit of

constant depth d, we set each input randomly and independently to 0 or 1,

each with a certain probability (1 −p)/2 close to but strictly less than 1/2,

or leave it unset with the remaining probability p.Thisiscalledarandom

partial valuation.Bychoosingp carefully, we can to show that with high

likelihood, the resulting circuit is equivalent to one of depth strictly less

than d while still retaining a good percentage of unassigned variables. By

repeating this process, we can reduce the depth to 2 with bounded indegree

at the ﬁrst level; but we can show independently that no such family can

compute Parity.

Circuit Lower Bounds and Relativized PSPACE = PH 197

Note that the degree of the gates and uniformity of the family of circuits

are not issues here. The lower bounds hold even for nonuniform circuits

containing gates of unbounded indegree and outdegree.

Lecture 31

Lower Bounds for Constant Depth Circuits

In this lecture we present the details of the result of Furst, Saxe, and Sipser

[46] that Parity is not in AC

Recall that a formula or circuit is in t-conjunctive normal form (t-

CNF ) if it is a conjunction of clauses, each clause a disjunction of at most

t literals, each literal a variable or its negation. Dually, a formula or circuit

is in t-disjunctive normal form (t-DNF ) if it is a disjunction of terms, each

term a conjunction of at most t literals. We can assume without loss of

generality that no term or clause contains a pair of complementary literals.

By convention, the empty conjunction is equivalent to 1 and the empty

disjunction is equivalent to 0.

Given a parity circuit of constant depth d, we can assume without loss

of generality that the gates are arranged in levels with variables and their

negations at level 0 and other levels alternating between disjunctions and

conjunctions. We can also assume that the gates at level 1 are disjunctions;

if not, consider the dual circuit instead, which is also a parity circuit.

The length of a term or clause M, denoted |M |, is the number of literals

in M.Weoftenomitthesymbol∧ in terms and write

x for ¬x.Thusxyz

means the same as ¬x ∧y ∧¬z.

A partial valuation of a set X of Boolean variables is an assignment

of constants to some of the variables of X, possibly leaving some variables

unassigned. Formally, a partial valuation on X is a map ρ : X → X ∪{0, 1}

Lower Bounds for Constant Depth Circuits 199

such that for each x ∈ X, ρ(x) ∈{x, 0, 1}.Wesaythatx is unassigned

under ρ if ρ(x)=x.

Any partial valuation ρ on X extends to a function on Boolean formulas

over X in a natural way, replacing each variable x with ρ(x)andthen

simplifying wherever possible using the Boolean algebra axioms 0 ∨ x = x,

0 ∧ x =0,1∨ x =1,1∧ x = x. For example, if ρ(x)=1,ρ(y) = 0, and

ρ(z)=z,then

ρ((x ∨ y) ∧ (

x ∨ z)) = z.

For the remainder of this lecture, we consider randomly chosen partial

valuations in which each variable is independently assigned 0 or 1, each

with probability (1 − 1/

√

n)/2, or left unassigned with probability 1/

√

The central idea of the proof is that all the CNF subcircuits at level 2

will very likely become equivalent to DNF circuits after applying a ﬁnite

number of partial valuations chosen randomly according to this distribu-

tion. Thus the chances are good that we will be able to replace all the CNF

gates at level 2 with DNF gates, then absorb the disjunctions at level 2

into the disjunctions at level 3, thereby reducing the depth by one level.

Continuing in this fashion, we will be able to get rid of all levels except

two.

Lemma 31.1 After a random partial valuation, the probability that there are fewer than

√

n/2 unassigned variables is at most (2/e)

√

n/2

Proof. Each variable remains unassigned with probability 1/

√

n.There

are n variables in all, so the mean number of unassigned variables is n/

√

n =

√

n. The result now follows immediately from the Chernoﬀ bound (I.7) with

µ =

√

n and δ =1/2. 2

Lemma 31.1 is important, because it says that after the application

of a random partial valuation, it is very likely that there are still enough

unassigned variables left that the size of the circuit is still polynomial in

the number of inputs.

The following are two technical lemmas that are used in our main de-

velopment.

Lemma 31.2 Let c be a constant, and let A be any set of variables of size at least c but

o(n

1/c

). The probability that a random partial valuation leaves more than c

variables of A unassigned is bounded above by n

1−c/2

for suﬃciently large

Proof. Let X be a random variable representing the number of variables

of A left unassigned by the random partial valuation. We wish to estimate

Pr (X ≥ c). If s = |A|, then the expected number of unassigned variables

200 Lecture 31

is µ = sn

−1/2

. Plugging this into the Chernoﬀ bound (I.6), for suﬃciently

large n,

Pr (X ≥ c) <e

c−µ

(µ/c)

≤ (eµ/c)

=(esn

−1/2

/c)

= n

−c/2

(es/c)

≤ n

1−c/2

the last inequality by the assumption that s is o(n

1/c

). 2

Lemma 31.3 Let a and b be constants. Let S be any set of pairwise disjoint sets of vari-

ables such that S has size at least b log n and all elements of S havesizeless

than a.ForA ∈ S,letE(A) be the event that a random partial valuation

assigns 0 to all variables in A. For suﬃciently large n, the probability that

E(A) does not occur for any A ∈ S is bounded above by n

b log(1−2

−a

)

Proof. Let A ∈ S and let s = |A|. For suﬃciently large n, the probability

of E(A)is2

−s

(1−n

−1/2

)

≥ 2

−s

/2 ≥ 2

−a

. The probability that E(A)does

not occur is thus bounded by 1−2

−a

. Because the elements of S are pairwise

disjoint, the events E(A) are independent, therefore the probability that

E(A) fails for all A ∈ S is the product of the probabilities that it fails for

each of them, which is bounded by (1 − 2

−a

)

|S |

.But

(1 − 2

−a

)

|S |

≤ (1 − 2

−a

)

b log n

= n

b log(1−2

−a

)

Now we are ready to give the main part of the argument, which we

have split into three lemmas. Let t be a constant. Call a circuit a t-circuit

if every level-1 gate is of degree at most t; that is, if every level-2 gate is a

t-CNF circuit.

Lemma 31.4 If Parity has polynomial-size circuits of depth d,thenParity has

polynomial-size t-circuits of depth d for some constant t.

Lemma 31.5 If Parity has polynomial-size t-circuits of depth d ≥ 3 and t ≥ 1,then

Parity has polynomial-size (t −1)-circuits of depth d.

Lemma 31.6 If Parity has polynomial-size 1-circuits of depth d ≥ 1,thenParity has

polynomial-size circuits of depth d − 1.

Proof of Lemma 31.4. Suppose Parity has circuits of depth d and

size n

. Consider a random partial valuation ρ on the variables of the nth

circuit. Let t =2k +4 and b =(k +1)/ log(3/2). For some level-1 clause

C, consider the event |ρ(C) | >t;thatis,morethant literals of C remain

unassigned. We show that for suﬃciently large n, this event occurs with

probability at most n

−(k+1)

There are three cases, depending on the size of C.

Lower Bounds for Constant Depth Circuits 201

Case 1 If |C |≤t, then the probability is already 0, so we are done.

Case 2 If t ≤|C |≤b log n, then by Lemma 31.2, for suﬃciently large n,

the probability that a random partial valuation leaves more than t literals

in C unassigned is bounded above by n

1−t/2

= n

−(k+1)

Case 3 The last case is |C |≥b log n. If any literal of C is assigned 1, then

ρ(C)=1,so|ρ(C) | = 0. Thus the probability that there are at least t

literals remaining unassigned is bounded by the probability that no literal

in C is assigned 1. To calculate this probability, note that for suﬃciently

large n, the probability that any particular literal is not assigned 1 is

1 −

(1 −

√

(1 +

√

) ≤

These events are independent, thus the probability that no literal in C is

assigned 1 is at most





|C |

≤





b log n

≤ n

b log(2/3)

= n

−(k+1)

We have shown that for suﬃciently large n, for each level-1 clause C,

the probability that |ρ(C) | >tis at most n

−(k+1)

. By the law of sum, the

probability that there exists a level-1 clause with more than t literals is

bounded by the sum of these probabilities. Because there are at most n

level-1 clauses in all,

Pr (∃C |ρ(C) | >t) ≤



Pr (|ρ(C) | >t) ≤ n

−(k+1)

= n

−1

which is vanishingly small.

Now by Lemma 31.1, the probability that there are fewer than

√

n/2

unassigned variables is also vanishingly small. Again by the law of sum, the

probability that either event occurs in a single random partial valuation is

vanishingly small. That is, with probability tending to 1, the random partial

valuation leaves at least

√

n/2 variables unassigned and knocks all level-1

gates down to degree at most t. As the probability of this event is nonzero,

there must be a partial valuation that realizes it. By making this partial

valuation (and by assigning a few other inputs if necessary), we obtain a

circuit for Parity on

√

n/2 variables and all level-1 gates of degree at most

t. These circuits are still polynomial-size, because polynomial in n is still

polynomial in

√

n/2. 2

Proof of Lemma 31.5. Suppose Parity has t-circuits of depth d ≥ 3,

t ≥ 1, and size n

.LetS be the set of clauses in some level-2 conjunction.