Kozen D.C. Theory of Computation

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

202 Lecture 31

Let T be a maximal subset of S such that no two clauses of T contain the

same variable, either positively or negatively. By maximal, we mean that

there is no proper superset of T satisfying this property. Such a set T can

be constructed by considering all the clauses in S in some order, taking the

next clause into T if it does not have a variable in common with any of the

clauses previously taken.

Let a =2k +4 and b = −(k +1)/ log(1 −2

−a

). Consider the eﬀect of a

random partial valuation on the variables of T . We consider two cases.

Case 1 If T contains at least b log n elements, then we have at least

b log n clauses, no two of which share a variable. By Lemma 31.3, for suf-

ﬁciently large n,someclauseinT receives all 0 with probability at least

1 −n

b log(1−2

−a

)

=1−n

−(k+1)

, in which case the entire conjunction at level

2 disappears.

Case 2 If T contains at most b log n elements, then



T contains at most

bt log n elements and shares a variable with all clauses in S (otherwise T was

not maximal). By Lemma 31.2, for suﬃciently large n, the probability that

a random partial valuation leaves more than a variables of



T unassigned

is bounded above by n

1−a/2

= n

−(k+1)

. Thus with very high probability,

there are at most 2a literals 

,... ,



T unassigned, and every clause

of ρ(S) that is still of size t must contain one of these literals. Let ϕ

the conjunction of all clauses of ρ(S)ofsizeatmostt −1. Of the remaining

clauses of ρ(S), let ϕ

be the conjunction of those containing the literal



and no literal 

for i<j, and let ϕ



be ϕ

with all occurrences of 

deleted. Then ϕ

is equivalent to 

∨ϕ



, and the original conjunction after

the partial evaluation is equivalent to



j=0

≡ ϕ

∧



j=1

(

∨ϕ



Using the distributive laws of Boolean algebra, this can be expressed as a

disjunction of at most 2

(t−1)-CNF circuits of the form ϕ

∧ψ

∧···∧ψ

where each ψ

is either 

or ϕ



We have shown that for suﬃciently large n, with probability at least

1−n

−(k+1)

,anyt-CNF gate at level 2 becomes equivalent to a disjunction of

a constant number of (t −1)-CNF gates under a random partial valuation.

This disjunction can be merged with the disjunctions at level 3 to give a

(t − 1)-circuit.

The remainder of the proof proceeds as in Lemma 31.4. Brieﬂy, the

probabilities of each of these events and the event that there remain at

least

√

n/2 unassigned variables tend to 1 suﬃciently fast that they all

occur simultaneously with nonzero probability. 2

Lower Bounds for Constant Depth Circuits 203

Proof of Lemma 31.6. This is the easy one. A polynomial-size 1-circuit

of depth d ≥ 1 is equivalent to a circuit of depth d −1simplybybypassing

the singleton gates at level 1. (In fact, this is just a special case of Lemma

31.5 for t =1.) 2

Lemma 31.7 There is no (n − 1)-CNF or (n − 1)-DNF parity circuit on n inputs.

Proof. An (n − 1)-CNF circuit on n inputs is a conjunction of clauses

with at most n − 1 literals per clause. Any partial valuation of a parity

circuit is a parity circuit on the remaining variables. But by setting at

most n −1 variables, we can make all the literals in some clause 0, thus the

whole circuit has constant value 0 regardless of the values of the remaining

variables, so it cannot be a parity circuit. The argument for (n − 1)-DNF

circuits is similar. 2

Combining Lemmas 31.4–31.7, we have

Theorem 31.8 (Furst, Saxe, and Sipser [46]) Parity ∈ AC

Proof. By repeating the constructions of Lemmas 31.4–31.6, we could

start with any family of circuits for Parity of constant depth and poly-

nomial size and reduce them to a family of circuits for Parity of depth

2, polynomial size, and constant indegree at level 1. These circuits would

be t-DNF or t-CNF circuits for some constant t. But this is impossible by

Lemma 31.7. 2

Supplementary Lecture H

The Switching Lemma

In this lecture we prove the H˚astad switching lemma [56], which can be

used to derive the lower bound on circuit size needed to achieve separation

of PH

and PSPACE

as described in Theorem 30.1.

Any set of variables X generates a free Boolean algebra F

,which

is essentially the set of Boolean formulas over X modulo the axioms of

Boolean algebra. If |X | = n, the algebra F

has 2

elements. There is a

natural partial order ≤ on F

corresponding to propositional implication;

thus ϕ ≤ ψ iﬀ ϕ → ψ is a propositional tautology.

Recall that a term of X is a conjunction of literals, no two of which

form a complementary pair. For terms M and N , M ≤ N if every literal

appearing in N also appears in M. The empty term 1 is the ≤-maximum

element of F

.ForatermM and CNF formula ϕ, M ≤ ϕ if M contains

at least one literal from each clause of ϕ.

A minterm of a formula ϕ is a ≤-maximal term M such that M ≤ ϕ.If

ϕ is a CNF formula, then M is a minterm of ϕ iﬀ M contains at least one

literal from each clause of ϕ and no proper subterm of M has this property

(Miscellaneous Exercise 71). One can show using the distributive laws of

Boolean algebra that the disjunction of all minterms of ϕ is a DNF formula

equivalent to ϕ (Miscellaneous Exercise 72). The set of minterms of ϕ is

denoted m(ϕ).

A partial valuation ρ : X → X ∪{0, 1} gives rise to a Boolean algebra

homomorphism F

→ F

,whereY ⊆ X is the set of variables not as-

The Switching Lemma 205

signed by ρ.IfA ⊆ X,wewriteρ(A)=A if no variable of A is assigned

by ρ,thatis,ifρ(x)=x for all x ∈ A. For any term M,eitherρ(M)=0

or M ≤ ρ(M ).

Because ρ is a homomorphism, it preserves ≤.ThusifM ≤ ϕ, then

ρ(M) ≤ ρ(ϕ). One can show that any minterm N of ρ(ϕ)isρ(M)forsome

minterm M of ϕ (Miscellaneous Exercise 80). However, it is not true that

ρ(M) is a minterm of ρ(ϕ) whenever M is a minterm of ϕ. For example,

if ψ =(x ∨ z) ∧ (y ∨

z)andρ(x)=x, ρ(y)=y,andρ(z)=0,thenxy

is a minterm of ψ and ρ(xy)=xy, but xy is not a minterm of ρ(ψ)=x.

However, we have the following special case.

Lemma H.1 Let ϕ be a formula, C aclause,andM ∈ m(ϕ ∧ C).Letvar(M,C) be the

set of variables that occur in both M and C (not necessarily with the same

polarity ).Letσ :var(M, C) →{0, 1} be the unique valuation such that

σ(M) =0.Thenσ(ϕ ∧ C)=σ(ϕ) and σ(M) is a minterm of σ(ϕ).

Proof. The valuation σ is unique, because there is only one way to assign

values to variables in var(M,C) so that the corresponding literals in M get

the value 1. Because M must contain a literal of C,thesetvar(M,C)is

nonempty and σ(C)=1,thusσ(ϕ ∧C)=σ(ϕ) ∧ σ(C)=σ(ϕ).

The term M can be written as a conjunction of terms M = σ(M)M



where M



contains all the variables in var(M, C). Note that σ(M)contains

no variables in var(M,C). Similarly, ϕ can be written as a conjunction

∧ϕ

,whereϕ

is a CNF formula each of whose clauses contains a literal

of M



and ϕ

is a CNF formula none of whose clauses contains a literal of



.Thenσ(ϕ) ≤ ϕ

and M



≤ ϕ

∧ C.

We now show that σ(M) is a minterm of σ(ϕ). Surely σ(M) ≤ σ(ϕ),

because M ≤ ϕ.IfN were any other term such that σ(M) ≤ N ≤ σ(ϕ),

then

M = σ(M)M



≤ NM



≤ σ(ϕ) ∧ ϕ

∧C ≤ ϕ ∧ C.

But M is a minterm of ϕ ∧ C, therefore M = σ(M)M



= NM



. Because

σ(M)andM



are on disjoint sets of variables, σ(M)=N. 2

Lemma H.2 Let ϕ be a formula and W a set of variables. Let

−W

def



τ :W →{0,1}

τ(ϕ).

(i) If ϕ is written in CNF, then ϕ

−W

is equivalent to a CNF formula

with no more clauses than ϕ.

(ii) If M ∈ m(ϕ) such that var(M,W)=∅,thenM ∈ m(ϕ

−W

(iii) If ρ(W )=W ,thenρ(ϕ)

−W

= ρ(ϕ

−W

206 Supplementary Lecture H

(iv) If ρ(W )=W,thenρ(ϕ)=1iﬀ ρ(ϕ

−W

)=1.

Proof. For (i), let ϕ be written in CNF. We show that ϕ

−W

is equivalent

to ϕ with all literals involving variables in W erased. It suﬃces to show

this for each clause C individually. For each τ : W →{0, 1}, τ (C)iseither

1 or the clause with all literals involving variables in W erased. The former

occurs if τ sets one of these literals to 1. The latter occurs if τ sets all

these literals to 0, and there is at least one τ. Thus the conjunction C

−W

is equivalent to this clause.

For (ii), we use (i). Let ϕ bewritteninCNF.Becausevar(M, W)=∅,

M still has a literal in common with all clauses even after the variables in

W are erased, thus M ≤ ϕ

−W

. Also, because each clause C is a disjunction

of literals, C

−W

≤ C, therefore ϕ

−W

≤ ϕ. Because M ≤ ϕ

−W

≤ ϕ and

M is a minterm of ϕ, it is also a minterm of ϕ

−W

(Miscellaneous Exercise

78).

We leave (iii) and (iv) as exercises (Miscellaneous Exercise 79). 2

Lemma H.3 (Switching Lemma [56]) Let ϕ be a t-CNF formula over variables X.Let

ρ be a random partial valuation in which every variable is independently

assigned 0 or 1 each with probability (1 −p)/2 or left unassigned with prob-

ability p.Then

Pr(ρ(ϕ)isnot equivalent to an s-DNF formula) ≤ α

where α =4pt/ ln 2 ∼ 5.77pt.

Proof. Every formula is equivalent to the disjunction of its minterms,

so it suﬃces to show

Pr(∃M ∈ m(ρ(ϕ)) |M |≥s) ≤ α

The proof is by induction on the number of clauses of ϕ. We actually need

a stronger induction hypothesis, namely that the bound holds even when

conditioned on an arbitrary formula ψ becoming 1 under ρ:

Pr(∃M ∈ m(ρ(ϕ)) |M |≥s | ρ(ψ)=1) ≤ α

. (H.1)

For the basis ϕ = 1, the only minterm is 1, so the probability on the

left-hand side is 0 unless s = 0, in which case the right-hand side is 1.

For the induction step, consider a formula ϕ∧C of at least one nonempty

clause. If the G

are a family of mutually exclusive and exhaustive events,

then to show that Pr(E | F ) ≤ a, it suﬃces to show separately that Pr(E |

∧ F ) ≤ a for all i (Miscellaneous Exercise 73). Thus to show (H.1), it

suﬃces to show separately that

Pr(∃M ∈ m(ρ(ϕ ∧ C)) |M |≥s | ρ(C)=1∧ ρ(ψ)=1) ≤ α

(H.2)

Pr(∃M ∈ m(ρ(ϕ ∧ C)) |M |≥s | ρ(C) =1∧ ρ(ψ)=1) ≤ α

. (H.3)

The Switching Lemma 207

The inequality (H.2) is the easier of the two. This is where we need the

stronger induction hypothesis. Under the conditioning ρ(C)=1,wehave

ρ(ϕ∧C)=ρ(ϕ)∧ρ(C)=ρ(ϕ), and ρ(C ∧ψ)=1iﬀρ(C)=1andρ(ψ)=1,

thus (H.2) is equivalent to

Pr(∃M ∈ m(ρ(ϕ)) |M |≥s | ρ(C ∧ψ)=1) ≤ α

This follows immediately from the induction hypothesis.

Now for (H.3). For a partial valuation ρ, suppose

M ∈ m(ρ(ϕ ∧ C)) ∧|M |≥s.

Let A =var(M,ρ(C)) = ∅. By Lemma H.1, there exist σ : A →{0, 1} and

N ∈ m(σ(ρ(ϕ))) (namely N = σ(M)) such that

•|N | = |M |−|A|≥s −|A|

• var(N, C)=∅

• σ(C)=1.

In addition, ρ(A)=A because A ⊆ var(ρ(C)), and σ and ρ commute,

because they assign disjoint sets of variables.

Similarly, we can express ρ as a composition ρ

◦ ρ

,whereρ

is a

partial valuation on var(C)andρ

is a partial valuation on X − var(C).

Thus ρ

(C)=C, ρ

(X − var(C)) = X − var(C), and ρ

and ρ

commute.

Now we have

N ∈ m(σ(ρ(ϕ)))

⇒ N ∈ m(ρ(σ(ϕ))) because σ and ρ commute

⇒ N ∈ m(ρ

(ρ

(σ(ϕ))))

⇒ N ∈ m(ρ

(ρ

(σ(ϕ)))

−C

) Lemma H.2(ii), var(N,C)=∅

⇒ N ∈ m(ρ

(ρ

(σ(ϕ))

−C

)) Lemma H.2(iii), ρ

(C)=C.

We have shown that under the premise

∃M ∈ m(ρ(ϕ ∧ C)) |M |≥s ∧ var(M,ρ(C)) = A, (H.4)

where A ⊆ var(C)andA = ∅, one can derive the conclusion

∃σ : A →{0, 1}∃N ∈ m(ρ

(ρ

(σ(ϕ))

−C

))

|N |≥s −|A|∧ρ(A)=A ∧ σ(C)=1.

(H.5)

Now we are ready to prove the inequality (H.3). Using the law of sum,

we can rewrite the left-hand side of (H.3) as



A ⊆ var(C)

A=∅

Pr(E(A) | ρ(C) =1 ∧ ρ(ψ)=1), (H.6)

208 Supplementary Lecture H

where E(A) is the event (H.4). Because (H.4) implies (H.5), this is at most



A ⊆ var(C)

A=∅

Pr(F (A) | ρ(C) =1 ∧ ρ(ψ)=1), (H.7)

where F (A) is the event (H.5). By the law of sum, this is at most



A ⊆ var(C)

A=∅



σ:A→{0,1}

σ(C)=1

Pr(G(A) | ρ(C) =1 ∧ ρ(ψ)=1), (H.8)

where G(A) is the event

G(A)

def

= ∃N ∈ m(ρ

(ρ

(σ(ϕ))

−C

)) |N |≥s −|A|∧ρ(A)=A.

To bound Pr(G(A) | ρ(C) =1∧ρ(ψ) = 1), by Miscellaneous Exercise 73 it

suﬃces to bound

Pr(G(A) | ρ(C) =1 ∧ ρ(ψ)=1 ∧ ρ

= τ)

=Pr(G(A) | ρ

(ρ

(ψ)) = 1 ∧ ρ

= τ)(H.9)

for all partial valuations τ of var(C) such that τ(C) = 1. But under the

new condition ρ

= τ, ρ

(ρ

(ψ)) becomes ρ

(τ(ψ)), ρ

(ρ

(σ(ϕ))

−C

)be-

comes ρ

(τ(σ(ϕ))

−C

), and the condition ρ

over, using Lemma H.2(iv), we can replace the condition ρ

(τ(ψ)) = 1 by

(τ(ψ)

−C

) = 1. After all these changes, (H.9) becomes

Pr (∃N ∈ m(ρ

(τ(σ(ϕ))

−C

)) |N |≥s −|A|∧ρ

(A)=A

| ρ

(τ(ψ)

−C

)=1 ∧ ρ

= τ ). (H.10)

Now the conditions involving ρ

and those involving ρ

are independent,

because they refer to the action of ρ on disjoint sets of variables. Thus by

Miscellaneous Exercise 75, (H.10) can be rewritten as a product

Pr(∃N ∈ m(ρ

(τ(σ(ϕ))

−C

)) |N |≥s −|A||ρ

(τ(ψ)

−C

)=1)

· Pr(ρ

(A)=A | ρ

= τ).

The ﬁrst factor is bounded by α

s−|A |

by the induction hypothesis, and the

second is bounded by (2p/(1 + p))

|A |

by direct calculation. Thus (H.8) is

The Switching Lemma 209

at most



A ⊆ var(C)

A=∅



σ:A→{0,1}

σ(C)=1



1+p



|A |

s−|A |

|C |



k=1



|C |



− 1)



1+p



s−k

≤



k=0





− 1)



1+p



s−k

= α



(1 + p)α



−



(1 + p)α



≤ α





− 1

. (H.11)

Substituting 4pt/ ln 2 for α and using the fact that (1 + 1/x)

≤ e for all

positive x, it follows that the larger parenthesized expression in (H.11) is

at most 1, therefore (H.11) is at most α

. 2

Theorem H.4 There are no circuit families for Parity of depth d and size 2

(log n)

for

any constants c and d.

Proof. Suppose there were. Let t =(logn)

c+1

and p =(ln2)/(8t). With-

out loss of generality, assume that the level-2 circuits are all t-CNF (add

another level if necessary). Applying a random partial valuation, the proba-

bility that any given level-2 circuit does not become equivalent to a t-DNF

circuit is bounded by α

. By the law of sum, the probability that there

exists a level-2 circuit that does not become equivalent to a t-DNF circuit

is bounded by

(log n)

· α

(log n)

· 2

−(log n)

c+1

which is vanishingly small as a function of n.

Afterwards, the expected number of unassigned variables is still quite

large:

np =

n ln 2

8(log n)

c+1

≥ 2n(log n)

−(c+2)

for suﬃciently large n. The probability that the actual number of unas-

signed variables is less than half that is also vanishingly small (Miscella-

neous Exercise 86).

210 Supplementary Lecture H

Thus for suﬃciently large n, there is nonzero probability that all t-

CNF level-2 circuits can be replaced by equivalent t-DNF circuits and that

there are still at least n(log n)

−(c+2)

unassigned variables. The size of the

new circuit in terms of the input size m = n(log n)

−(c+2)

is still at most

(log m)

c+3

. Because there is nonzero probability, there must exist a partial

valuation making it true.

Iterating this construction d − 2 times, we obtain a family of circuits

for Parity of depth 2 and size 2

(log m)

for some k such that all level-1

circuits are of degree at most t. But for suﬃciently large n, this contradicts

Lemma 31.7. 2

Corollary H.5 There exists an oracle A such that PH

= PSPACE

Proof. Theorems H.4 and 30.1. 2

Supplementary Lecture I

Tail Bounds

In probabilistic analysis, we often need to bound the probability that a

random variable deviates far from its mean. There are various formulas

for this purpose. These are called tail bounds. The weakest of these is the

Markov bound, which states that for any nonnegative random variable X

with mean µ = EX,

Pr(X ≥ k) ≤ µ/k (I.1)

(Miscellaneous Exercise 83). A better bound is the Chebyshev bound,which

states that for a random variable X with mean µ = EX and standard

deviation σ =

E((X − µ)

), for any δ ≥ 1,

Pr(|X −µ|≥δσ) ≤ δ

−2

(I.2)

(Miscellaneous Exercise 84).

The Markov and Chebyshev bounds converge linearly and quadrati-

cally, respectively, and are often too weak to achieve desired estimates.

In particular, for the special case of Bernoulli trials (sum of independent,

identically distributed 0,1-valued random variables) or more generally Pois-

son trials (sum of independent 0,1-valued random variables, not necessarily

identically distributed), the convergence is exponential.