Kozen D.C. Theory of Computation

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

182 Supplementary Lecture F

so it suﬃces to show

Pr(T ∩ H = ∅) ≤

Because dim <T > =dim<S ∩ E

> ≥ 2, by Miscellaneous Exercise 73,

Pr(T ∩ H = ∅) ≤ max

d≥2

Pr(T ∩ H = ∅ | dim <T > = d), (F.4)

thus it suﬃces to bound

Pr(T ∩ H = ∅ | dim <T > = d)(F.5)

for d ≥ 2. Using the fact that for subspaces A and B of a ﬁnite-dimensional

vector space, codim A ∩ B ≤ codim A +codimB (Miscellaneous Exercise

61),wehavethatifdim<T > = d, then dim(<T > ∩ H)iseitherd or d − 1.

Again by Miscellaneous Exercise 73, (F.5) is bounded by the maximum of

Pr(T ∩ H = ∅ | dim <T > = d ∧ dim(<T > ∩ H)=d)(F.6)

Pr(T ∩ H = ∅ | dim <T > = d ∧ dim(<T > ∩ H)=d − 1). (F.7)

But (F.6) is 0, because dim <T > =dim(<T > ∩ H)=d implies T ⊆ H,

therefore T ∩ H cannot be empty. Thus we must bound (F.7). But this is

the same as the probability, given a set Q of d ≥ 2 linearly independent

vectors and a random hyperplane G in <Q>, that none of the vectors of Q

lie in G:

Pr(Q ∩ G = ∅). (F.8)

Let x be a vector in <Q> such that G = {x}

⊥

. Then (F.8) becomes

Pr(∀y ∈ Qy

•

x =0). (F.9)

To bound this expression, we use the inclusion–exclusion principle (see

Lecture 13). Over the ﬁeld GF

of q elements,

Pr(∀y ∈ Qy

•

x =0) = 1− Pr(∃y ∈ Qy

•

x =0)

=1−

⎛

⎜

⎝

|Q |



m=1

(−1)

m+1



A ⊆Q

|A |=m

Pr(x ∈ A

⊥

)

⎞

⎟

⎠

=1−



m=1

(−1)

m+1





−m



m=0





(−1)

−m



1 −



Unique Satisﬁability 183

This is maximized at d =2,whichforq =2gives1/4. 2

It can be shown that the lower bound 3/4 in Lemma F.1 is the best possible

for all n (Miscellaneous Exercise 62).

Unique Satisﬁability and General Satisﬁability

The class RP (for random polynomial time) was deﬁned in Lecture 13. This

is the class of sets accepted by polynomial-time probabilistic computations

with one-sided error. Recall that RP is deﬁned in terms of probabilistic

machines, which are exactly like nondeterministic Turing machines except

that they make choices probabilistically rather than nondeterministically.

At each choice point, the machine chooses one of its possible next conﬁgu-

rations randomly with uniform probability. Equivalently, we can supply a

deterministic polynomial-time machine with a polynomial-length string of

random bits that it can consult during its computation.

Valiant and Vazirani’s result says that an RP computation supplied

with an oracle USAT for unique satisﬁability can determine general satis-

ﬁability with arbitrarily small one-sided error. The oracle USAT may be

any oracle that answers aﬃrmatively when queried on a Boolean formula

that has exactly one satisfying assignment, negatively when queried on a

formula that has no satisfying assignments, and arbitrarily on any other

query.

Theorem F.2 (Valiant and Vazirani [125]) NP ⊆ RP

USAT

Proof. We show how to decide Boolean satisﬁability by an RP compu-

tation with a USAT oracle. That is, we show that there is a polynomial-

time-bounded probabilistic oracle Turing machine M with oracle USAT

such that

ϕ is satisﬁable ⇒ Pr(M accepts ϕ) ≥

ϕ is unsatisﬁable ⇒ Pr(M accepts ϕ)=0.

Equivalently, encoding the random choices as part of the input, we show

that there is a deterministic polynomial-time oracle machine N such that

for w a string of random bits of suﬃcient polynomial length chosen with

uniform probability among all strings of that length,

ϕ is satisﬁable ⇒ Pr

(N accepts ϕ#w) ≥

ϕ is unsatisﬁable ⇒ Pr

(N accepts ϕ#w)=0.

The machine N uses its random bits w to construct a random tower of

linear subspaces H

⊆ GF

as in Lemma F.1, where n is the number of

184 Supplementary Lecture F

Boolean variables of ϕ. This requires O(n

) random bits. The tower can be

represented as a sequence of n linearly independent vectors, as described

in the proof of Lemma F.1.

Say the variables of ϕ are x

,... ,x

.Foreach0≤ i ≤ n, N constructs

aformulaψ

stating that (x

,... ,x

), regarded as an n-vector in GF

, lies

in H

. This construction is a straightforward encoding of the inner product

of (x

,... ,x

) with the random vectors representing H

.ThemachineN

then queries the oracle on the conjunctions ϕ ∧ψ

and accepts if the oracle

responds “yes” to any of these queries.

Let S be the set of truth assignments satisfying ϕ.Then

(N accepts ϕ#w)=Pr(∃iϕ∧ ψ

∈ USAT),

which by Lemma F.1 is at least

Pr(∃i |S ∩ H

| =1) ≥

if S = ∅ and 0 if S = ∅. 2

The error can be made arbitrarily small by ampliﬁcation (Lemma 14.1).

Supplementary Lecture G

Toda’s Theorem

In this lecture we present Toda’s theorem (Theorem G.1), which states

that the ability to count solutions to instances of NP-complete problems

allows one to solve any decision problem in the polynomial-time hierarchy

PH . This theorem came as quite a surprise when it ﬁrst appeared in 1989

[120, 121], because it showed that the power to count solutions was much

stronger than previously thought. This result is a convergence of several

important ideas and constructions involving various complexity classes and

is a ﬁne example of structural complexity theory at its best.

Counting Classes

The power to count solutions is captured in the class P

. We can deﬁne

the class #P to be the class of all functions f

: {0, 1}

∗

→ N such that

M is a nondeterministic polynomial-time Turing machine and f

(x)gives

the number of accepting computation paths of M on input x.Equivalently,

f ∈ #P iﬀ there is a set A ∈ P and k ≥ 0 such that for all x ∈{0, 1}

∗

f(x)=|{y ∈{0, 1}

|x |

| x#y ∈ A}| (G.1)

(Miscellaneous Exercise 64). For example, the function that returns the

number of satisfying truth assignments to a given Boolean formula is in

#P. Note that unlike other complexity classes we have studied, #P is not

186 Supplementary Lecture G

a class of decision problems, but a class of integer-valued functions. The

class P

is the class of decision problems solvable in polynomial time with

an oracle for some f ∈ #P. The classes #P and P

were introduced by

Valiant [124].

The formulation (G.1) suggests that we can view #P as the set of

functions that give the cardinality of a set of witnesses to an existential

formula. If p : N → N and A is a set of strings, a witness for x with respect

to p and A is a binary string y of length p(|x|) such that x#y ∈ A.Letus

denote the set of all witnesses for x with respect to p and A by W (p, A, x).

Thus

W (p, A, x)

def

= {y ∈{0, 1}

p(|x |)

| x#y ∈ A}.

Many of the complexity classes we have considered in this course can

be deﬁned in terms of the cardinality of witness sets W (p, A, x)forvari-

ous parameters A and p. The deﬁning conditions often do not require full

knowledge of |W (p, A, x) |, but only bounds or certain bits. For example,

L ∈ NP

def

⇐⇒ ∃A ∈ P ∃c ≥ 0 ∀xx∈ L ⇔|W (n

,A,x) | > 0

L ∈ Σ

k+1

def

⇐⇒ ∃A ∈ Π

∃c ≥ 0 ∀xx∈ L ⇔|W (n

,A,x) | > 0

L ∈ RP

def

⇐⇒ ∃A ∈ P ∃c ≥ 0 ∀x

x ∈ L ⇒|W (n

,A,x) |≥

· 2

|x |

x ∈ L ⇒|W (n

,A,x) | =0

L ∈ BPP

def

⇐⇒ ∃A ∈ P ∃c ≥ 0 ∀x

x ∈ L ⇒|W (n

,A,x) |≥

· 2

|x |

x ∈ L ⇒|W (n

,A,x) |≤

· 2

|x |

L ∈ PP

def

⇐⇒ ∃A ∈ P ∃c ≥ 0 ∀xx∈ L ⇔|W (n

,A,x) |≥2

|x |

−1

L ∈⊕P

def

⇐⇒ ∃A ∈ P ∃c ≥ 0 ∀xx∈ L ⇔|W (n

,A,x) | is odd

L ∈ #P

def

⇐⇒ ∃A ∈ P ∃c ≥ 0 ∀xL(x)=|W (n

,A,x) |.

Note that PP and ⊕P are deﬁned in terms of the ﬁrst and last bit, respec-

tively, of |W (n

,A,x) |.

We can generalize further to deﬁne a set of operators BP, R,#,andso

on, on complexity classes C. These operators can be viewed as reducibility

relations. The deﬁnitions are assembled in the following table, which should

be read as follows. The complexity class whose name appears in the left-

hand column is deﬁned to be the class of sets or functions L for which there

exist A ∈ C and k ≥ 0 such that for all x, the condition in the right-hand

To d a’ s T h e ore m 187

column holds.

Class Deﬁning Condition

R · C

x ∈ L ⇒|W (n

,A,x) |≥

· 2

|x |

x ∈ L ⇒|W (n

,A,x) | =0

BP · C

x ∈ L ⇒|W (n

,A,x) |≥

· 2

|x |

x ∈ L ⇒|W (n

,A,x) |≤

· 2

|x |

P · C x ∈ L ⇔|W (n

,A,x) |≥

· 2

|x |

⊕·C x ∈ L ⇔|W (n

,A,x) |≡1(mod2)

· C x ∈ L ⇔|W (n

,A,x) | > 0

· C x ∈ L ⇔|W (n

,A,x) | =2

|x |

log

· C x ∈ L ⇔|W (k log n,A,x)| > 0

log

· C x ∈ L ⇔|W (k log n,A,x)| =2

k log |x |

# · C L(x)=|W (n

,A,x) |

Thus RP = R · P, BPP = BP ·P, PP = P · P, ⊕P = ⊕·P, NP =Σ

·P,

co-NP =Π

· P,Σ

k+1

=Σ

· Π

,and#· P =#P . Note that all of these

operators are monotone with respect to set inclusion.

The characterization of complexity classes in terms of operators and

witnesses reveals an underlying similarity among the classes that is quite

striking. It also provides a common framework in which to carry out the

constructions in the proof of Toda’s theorem. Many of the closure properties

we need are naturally expressed as algebraic properties of these operators,

such as commutativity and idempotence.

Toda’s Theorem

Theorem G.1 (Toda [120]) PH ⊆ P

Much of the proof of Toda’s theorem can be broken down into a series of

inclusions (Lemma G.2(i)–(vi)) that establish basic algebraic properties of

the operators on complexity classes deﬁned in the previous section. These

are combined to show that PH ⊆ BP ·⊕P. In addition, there is a ﬁnal

ingenious argument showing that BP ·⊕P ⊆ P

Lemma G.2 Let C be a complexity class closed downward under the polynomial-time

Turing reducibility relation ≤

.Then

(i) Σ

· C ⊆ R · Σ

log

·⊕·C;

(ii) Π

log

·⊕·C ⊆⊕·C;

(iii) ⊕·BP · C ⊆ BP ·⊕·C;

188 Supplementary Lecture G

(iv) BP ·BP · C ⊆ BP ·C;

(v) ⊕·⊕·C ⊆⊕·C;

(vi) BP ·C and ⊕·C are closed downward under ≤

Proof. Believe it or not, clause (i) is a minor variant of the result of

Valiant and Vazirani presented in Lecture F (Lemma F.1). We prove this

clause explicitly and leave the remaining clauses (ii)–(vi) as exercises (Mis-

cellaneous Exercise 66).

By deﬁnition, L ∈ Σ

· C iﬀ there exist A ∈ C and k ≥ 0 such that for

all x,

x ∈ L ⇔ W (n

,A,x) = ∅.

Let N = n

.AsinLemmaF.1,letH

,0≤ i ≤ N, be a random tower

of linear subspaces of GF

with dim H

= i. Recall that the tower is

speciﬁed by a random nonsingular matrix over GF

,whereH

is the

orthogonal complement of the ﬁrst N −i columns of the matrix. The random

nonsingular matrix in turn is determined by a string w of random bits of

length O(N

). By Lemma F.1,

x ∈ L ⇒ W (N,A,x) = ∅

⇒ Pr

(∃i ≤ N |W (N,A,x) ∩ H

| =1) ≥

⇒ Pr

(∃i ≤ N |W (N,A,x) ∩ H

| is odd) ≥

x ∈ L ⇒ W (N,A,x)=∅

⇒ Pr

(∃i ≤ N |W (N,A,x) ∩ H

| is odd) = 0.

Let p be such that p(|x#w#i |)=|x|

. The function p can be made

to depend only on the length of x#w#i provided we represent i in binary

with k log |x| bits. Similarly, let q be such that q(|x#w |)=k log |x|.

Deﬁne



def

= {x#w#i#y | x#y ∈ A ∧ y ∈ H

}



def

= {z ||W (p, A



,z)| is odd}



def

= {u ||W (q, A



,u)| > 0}.

Because A ∈ C and A



≤

A,wehaveA



∈ C, A



∈⊕·C,andA



∈

log

·⊕·C by deﬁnition of these classes. Then

W (p, A



,x#w#i)={y ∈{0, 1}

|x |

| x#w#i#y ∈ A



}

= {y ∈{0, 1}

|x |

| x#y ∈ A}∩H

= W (N, A, x) ∩ H

To d a’ s T h e ore m 189

therefore

∃i ≤ N |W (N,A,x) ∩ H

| =1

⇒∃i ≤ N |W (N,A,x) ∩ H

| is odd

⇔∃i ≤ N |W (p, A



,x#w#i)| is odd

⇔∃i ≤ Nx#w#i ∈ A



⇔|{i ∈{0, 1}

k log |x |

| x#w#i ∈ A



}|> 0

⇔|W (q, A



,x#w)| > 0

⇔ x#w ∈ A



It follows that

x ∈ L ⇒ W (N,A,x) = ∅

⇒ Pr

(∃i ≤ N |W (N,A,x) ∩ H

| =1)≥

⇒ Pr

(x#w ∈ A



) ≥

x ∈ L ⇒ W (N,A,x)=∅

⇒∀i ≤ N |W (N,A,x) ∩ H

| is even

⇒ Pr

(x#w ∈ A



)=0.

Thus L ∈ R · Σ

log

·⊕·C. 2

Proof of Theorem G.1. We ﬁrst argue that the various inclusions of

Lemma G.2 combine to imply that PH ⊆ BP ·⊕P. The proof is by in-

duction on the level of the polynomial-time hierarchy. Certainly Σ

= P ⊆

BP ·⊕P. Now suppose that Σ

⊆ BP ·⊕P. By Lemma G.2(vi), BP ·⊕P

is closed under complement, therefore Π

⊆ BP ·⊕P .Then

k+1

=Σ

· Π

⊆ Σ

· BP ·⊕P by monotonicity

⊆ R · Σ

log

·⊕·BP ·⊕P by Lemma G.2(i)

⊆ R ·⊕·BP ·⊕P by Lemma G.2(ii) and (vi)

⊆ BP ·⊕·BP ·⊕P because R ·C ⊆ BP · C trivially

⊆ BP ·BP ·⊕·⊕P by Lemma G.2(iii)

⊆ BP ·⊕P by Lemma G.2(iv) and (v).

We have shown that Σ

⊆ BP ·⊕P for all k, therefore

PH =



⊆ BP ·⊕P.

190 Supplementary Lecture G

It remains to show that BP ·⊕P ⊆ P

.LetL ∈ BP ·⊕P. Then there

exist A ∈⊕P and k ≥ 0 such that for all x,

x ∈ L ⇒ Pr

(x#w ∈ A) ≥

x ∈ L ⇒ Pr

(x#w ∈ A) ≤

where the w are chosen uniformly at random among all binary strings of

length |x|

.Equivalently,

x ∈ L ⇒|W (n

,A,x) |≥

· 2

|x |

x ∈ L ⇒|W (n

,A,x) |≤

· 2

|x |

(G.2)

Furthermore, because A ∈⊕P, there exists a polynomial-time nondeter-

ministic TM M such that x#w ∈ A iﬀ f(x#w) is odd, where f(x#w)is

the number of accepting computation paths of M on input x#w.

Now we modify M to obtain a new machine N that on input x#w

has p(f(x#w)) accepting computation paths instead of f(x#w), where

p is a polynomial function represented by a certain polynomial in N[z].

Speciﬁcally, the polynomial p we are interested in is h

(z), where

h(z)

def

=4z

+3z

∈ N[z],

(z)isthei-fold composition of h with itself, that is,

(z)

def

= z

i+1

(z)

def

= h(h

(z)),

and m =log(n

+ 1). One can show inductively that h

(z)isofdegree

=(n

+1)

and has coeﬃcients that can be represented by at most

−1) =

((n

+1)

−1) bits. Moreover, the polynomial h

(z)canbe

constructed from x#w in polynomial time. The construction of N from M

is detailed in Miscellaneous Exercise 67(d).

One can show by induction that h

(z) has the following agreeable prop-

erty:

z is odd ⇒ h

(z) ≡−1(mod2

)

z is even ⇒ h

(z) ≡ 0(mod2

)

(Miscellaneous Exercise 65), thus

z is odd ⇒ p(z) ≡−1(mod2

)

z is even ⇒ p(z) ≡ 0(mod2

(G.3)

This characterization of ⊕P and the characterization involving witness sets are equivalent; this follows

immediately from the corresponding equivalence for #P (Miscellaneous Exercise 64).

To d a’ s T h e ore m 191

Now we can determine membership in L by a P

computation as

follows. Build a new machine K that on input x of length n

(i) generates all possible strings x#w with |w | = n

by nondeterministic

branching, one computation path for each such string;

(ii) for each x#w, runs N on x#w.

The number of accepting computation paths of K on input x is then



|w |=n

p(f(x#w)).

Modulo 2

, this quantity is



|w |=n

p(f(x#w)) ≡



|w |=n

f(x#w)odd

−1by(G.3)

≡ 2

−|{w ||w | = n

∧f (x#w)isodd}|

−|{w ||w | = n

∧x#w ∈ A}|

−|W (n

,A,x) |.

But by (G.2),

x ∈ L ⇒

· 2

≤|W (n

,A,x) |≤2

⇒ 2

≤ 2

−|W (n

,A,x) |≤

· 2

x ∈ L ⇒ 0 ≤|W (n

,A,x) |≤

· 2

⇒

· 2

≤ 2

−|W (n

,A,x) |≤2

and these are disjoint intervals. Thus the number of accepting computation

paths of K, reduced modulo 2

, determines membership in L.Thissays

that L ∈ P

. 2