Kozen D.C. Theory of Computation

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

Probabilistic Complexity 77

Inclusion–Exclusion Principle It follows from the law of sum that for any

events A and B, disjoint or not,

Pr(A ∪B)=Pr(A)+Pr(B) − Pr(A ∩ B).

More generally, for any collection A of events,

Pr(





A∈A

Pr(A) −



B ⊆A

|B |=2

Pr(



B)+



B ⊆A

|B |=3

Pr(



B) −···±Pr(



A).

This equation is often used to estimate the probability of a join of several

events. The ﬁrst term alone gives an upper bound and the ﬁrst two terms

give a lower bound:

Pr(



A) ≤



A∈A

Pr(A)

Pr(



A) ≥



A∈A

Pr(A) −



A,B∈A

A=B

Pr(A ∩B).

Probabilistic Turing Machines

Intuitively, we can think of a probabilistic Turing machine as an ordinary

deterministic TM, except that at certain points in the computation it can

ﬂip a fair coin and make a binary decision based on the outcome. The prob-

ability of acceptance is the probability that its computation path, directed

by the outcomes of the coin tosses, leads to an accept state.

Formally, we deﬁne a probabilistic Turing machine to be an ordinary

deterministic TM with an extra semi-inﬁnite read-only tape containing a

binary string called the random bits. The machine runs as an ordinary

deterministic TM, consulting its random bits in a read-only fashion. We

write M (x, y) for the outcome, either accept or reject, of the computation

of M on input x with random bits y.WesaythatM is T (n) time bounded

(respectively, S(n) space bounded) if for every input x of length n and

every random bit string, it runs for at most T (n) steps (respectively, uses

at most S(n) worktape cells).

In this model, the probability of an event is measured with respect to

the uniform distribution on the space of all sequences of random bits. This

is the measure that would result if a fair coin were ﬂipped inﬁnitely many

times with the ith random bit determined by the outcome of the ith coin

ﬂip.

In practice, we consider only time-bounded computations, in which case

the machine can look at only ﬁnitely many random bits. This makes the

78 Lecture 13

calculation of the probabilities of events easier. For example, if M is T (n)

time bounded, then the probability that M accepts its input string x is

(M(x, y) accepts) =

|{y ∈{0, 1}

| M (x, y) accepts}|

where k is any number exceeding T (|x|). The notation Pr

(E) refers to

the probability of event E with a bit string y chosen uniformly at random

among all strings of length k.

Randomness can be regarded as a computational resource, much like

time and space. One can measure the number of random bits consulted in

a computation. We show some examples of this in Lectures 18 to 20.

The following are two basic complexity classes deﬁned for probabilistic

Turing machines.

Deﬁnition 13.1 AsetA is in RP if there is a probabilistic Turing machine M with poly-

nomial time bound n

such that

• if x ∈ A,thenPr

(M(x, y) accepts) ≥

;and

• if x ∈ A,thenPr

(M(x, y) accepts)=0.

The deﬁnition of BPP is the same, except we replace the second condition

with:

• if x ∈ A,thenPr

(M(x, y) accepts) ≤

Equivalently, a set A is in BPP if there is a probabilistic Turing machine

M with time bound n

such that for all inputs x,

(M(x, y) errs in deciding whether x ∈ A) ≤

We have used

and

in the deﬁnition of RP and BPP , but actually

any

− ε and

+ ε will do. It matters only that the probabilities be

bounded away from

by a positive constant ε independent of the input

size.

Also, as previously observed, the length of the random bit string is not

important; any set of strings of suﬃcient length will do, as long as the

machine has access to as many random bits as it needs.

It is easy to see that P ⊆ RP ⊆ NP, RP ⊆ BPP,andBPP is closed

under complement. We show next time that BPP ⊆ Σ

∩ Π

Other classes such as RPSPACE and RNC can be deﬁned similarly.

Probabilistic Tests with Polynomials

Here is an example of a probabilistic test for which no equally eﬃcient de-

terministic test is known: determining whether a given multivariate poly-

nomial p(x

,... ,x

) of low degree with integer coeﬃcients is identically

Probabilistic Complexity 79

We assume that p is given in the form of a straight-line program with

operations +, ·, and scalar operations, or equivalently, in the form of an

arithmetic circuit. We could check deterministically if p is identically 0 by

multiplying it out to represent it as a sum of terms and checking whether

all the terms cancel, but this would take exponential time in general.

Alternatively, we can evaluate p on some a

,... ,a

chosen at ran-

dom from some suﬃciently large set of integers. If p is identically 0, then

p(a

,... ,a

) = 0. If not, then p(a

,... ,a

) = 0 with high probability. The

reason for this is that the zero set of a nonzero polynomial is sparse.

This works even over ﬁnite ﬁelds, provided the ﬁeld is large enough and

the degree of the polynomial is not too large. Here we can use the following

result, commonly known as the Schwartz–Zippel lemma, but also discovered

independently by DeMillo and Lipton [36, 110, 127] (see [75] for a proof):

Theorem 13.2 (Schwartz–Zippel Lemma) Let F be a ﬁeld and let S ⊆ F be an arbitrary

subset of F.Letp(

x) be a nonzero polynomial of n variables x = x

,... ,x

and total degree

d with coeﬃcients in F. Then the equation p(x)=0has

at most d ·|S |

n−1

solutions in S

Corollary 13.3 Let p(x

,... ,x

) be a nonzero polynomial of total degree d with coeﬃcients

in a ﬁeld F,andletS ⊆ F.Ifp is evaluated on an element (s

,... ,s

)

chosen uniformly at random from S

,then

Pr(p(s

,... ,s

)=0) ≤

|S |

This lemma is useful in quite a number of combinatorial applications.

Here are two examples.

Example 13.4 A perfect matching in a bipartite graph is a subset M of the edges such

that

(i) no two edges in M share a common vertex, and

(ii) every vertex is the endpoint of some edge in M.

It is known how to test for the existence of a perfect matching in a bipartite

graph G and ﬁnd one if it exists in polynomial time [62]. It is unknown

whether this problem is in NC . However, the following approach, based on

an observation of Lov´asz [80], gives a random NC algorithm.

Assign to each edge (i, j)ofG an indeterminate x

and consider the

n × n bipartite adjacency matrix X with these indeterminates instead of

1. For example,

Maximum degree of any term.

80 Lecture 13





⎡

⎣

0 x

⎤

⎦

The determinant det X is a polynomial of degree n in the indeterminates

with one term for each perfect matching, and none of these terms cancel.

For example, the graph above has two perfect matchings





corresponding to the two terms of the determinant

det X = x

− x

Thus G has a perfect matching iﬀ det X does not vanish identically. This

is diﬃcult to test deterministically, because det X may be quite large.

However, the determinant of an integer matrix can be calculated in

NC using Csanky’s algorithm [34] (see [75] for a proof), and we can use

this to test in RNC whether det X is identically 0. We can simply assign

randomly chosen elements of a large enough ﬁnite ﬁeld (say Z

,wherep is

some prime greater than 2n)tothex

, then ask whether the determinant

evaluated at those random elements is 0. This will happen with probability

1ifdetX is indeed identically 0, and with probability at most

not, by Corollary 13.3.

Given the ability to test for the existence of a perfect matching, we can

then ﬁnd one by deleting edges and their endpoints one by one and testing

for the existence of a perfect matching without that edge. 2

Example 13.5 Here is an eﬃcient probabilistic test for deciding whether two unordered

directed trees of height h and size n are isomorphic. Associate with each

vertex v a polynomial f

in the variables x

,... ,x

inductively, as

follows. For each leaf v,setf

= x

. For each internal node v of height k

with children v

,... ,v

,set

=(x

− f

)(x

− f

) ···(x

− f

The degree of f

is equal to the number of leaves in the subtree rooted at v.

Using the fact that polynomial factorization is unique, it can be shown that

two trees are isomorphic iﬀ the polynomials associated with the roots of

A directed tree is ordered if the left-to-right order of each node’s children is given.

Probabilistic Complexity 81

the trees are equal. This gives an eﬃcient probabilistic test for isomorphism

of unordered trees: test whether the diﬀerence of these two polynomials is

identically zero by evaluating it on a random input. 2

Another example of a problem with an eﬃcient probabilistic solution

is primality testing: given a positive integer, is it prime? For many years,

this problem was known to be in P only under the assumption of the

extended Riemann hypothesis, an unproved conjecture of analytic number

theory [86], but was known to be in RP via the Miller–Rabin test [86, 100]

(see [75]). This test is quite eﬃcient and always answers “prime” if the

given number is prime and “composite” with high probability if the given

number is composite. An improved probabilistic primality test was given

recently by Agrawal and Biswas [2]. The problem was also known to be in

NP ∩ co-NP (Theorem C.4).

Quite recently, Agarwal, Kayal, and Saxena have shown that primality

testing is in P unconditionally [3]. However, their algorithm runs in time

O(n

) and is currently not yet competitive with the best probabilistic

methods in practice.

Lecture 14

BPP ⊆ Σ

∩ Π

In this lecture we prove that BPP ⊆ Σ

∩ Π

. It suﬃces to show that

BPP ⊆ Σ

, because BPP is closed under complement. This result is due

to Sipser [112].

Ampliﬁcation

By repeating trials in an RP or BPP computation, we can cause the prob-

ability of error to diminish exponentially.

Lemma 14.1 (Ampliﬁcation Lemma) If A ∈ RP, then for any polynomial n

there is

a probabilistic polynomial-time-bounded Turing machine M such that for

inputs x of length n,

(i) if x ∈ A,thenPr

(M(x, y) accepts) ≥ 1 −2

−n

;and

(ii) if x ∈ A,thenPr

(M(x, y) accepts)=0.

If A ∈ BPP, then for any polynomial n

there is a probabilistic

polynomial-time-bounded Turing machine M such that for inputs x of

length n,

(M(x, y) errs in deciding whether x ∈ A) ≤ 2

−n

BPP ⊆ Σ

∩ Π

Proof. For RP,letM be a probabilistic polynomial-time-bounded TM

such that for all x,

• if x ∈ A then Pr

(M(x, y) accepts) ≥

;and

• if x ∈ A then Pr

(M(x, y) accepts) = 0.

Build another probabilistic TM N that on input x just runs M on xn

times, using a new block of random bits for each trial, and accepts if any

one of the trials accepts. If M is time-bounded by n

, hence uses at most

random bits, then N will be n

c+d

-time-bounded and use at most n

c+d

random bits, which is still polynomial. If x ∈ A,thenM always rejects, so

N rejects; and if x ∈ A, then the probability that N errs is

,... ,y

(N(x, y

,... ,y

d ) rejects) =



i=1

(M(x, y

) rejects)

=Pr

(M(x, y) rejects)

≤ 4

−n

For BPP, the construction of N is exactly the same, except that to de-

cide whether to accept or reject, N does n

d+1

trials and picks the majority

outcome. The probability of error is the probability that at most half of

the n

d+1

outcomes are correct; this is bounded by

d+1



k=0



d+1









d+1

−k

≤ 4

−n

d+1



k=0



d+1



−n

d+1

−1

≤





d+1

≤ 2

−n

d+1

≤ 2

−n

for suﬃciently large n. 2

BPP ⊆ Σ

∩ Π

Let A ∈ BPP . By the ampliﬁcation lemma (Theorem 14.1), there is a c>1

and a deterministic polynomial-time-bounded TM M running in time n

such that for all inputs x,

• if x ∈ A,thenPr

(M(x, y) accepts) ≥ 1 − 2

−n

,and

84 Lecture 14

• if x ∈ A,thenPr

(M(x, y) accepts) ≤ 2

−n

where Pr

(E) denotes the probability of the event E taken over all strings

y chosen uniformly at random from the set {0, 1}

Fix an input string x of length n, and let m = n

. Deﬁne

def

= {y ∈{0, 1}

| M (x, y) accepts}

def

= {y ∈{0, 1}

| M (x, y) rejects} = {0, 1}

− A

Then for x ∈ A,

|≥2

− 2

m−n

and |R

|≤2

m−n

and for x ∈ A,

|≥2

− 2

m−n

and |A

|≤2

m−n

Claim 14.2 The string x is in A if and only if there exist m strings z

,... ,z

,eachof

length m, such that

{y ⊕ z

| 1 ≤ j ≤ m, y ∈ A

} = {0, 1}

where ⊕ denotes exclusive-or or bitwise mod 2 sum.

The idea here is that if x ∈ A, then the set A

is so big that by mapping

it around with some small set of permutations of the form y → y ⊕ z,we

hit every string; and if x ∈ A,thenA

is so small that no small collection

of such permutations does this.

If the claim is true, then this is all we need to show A ∈ Σ

: to determine

whether x ∈ A,

(i) guess z

,... ,z

using existential branching;

(ii) generate all w of length m using universal branching; and

(iii) check that w ∈{y ⊕ z

| 1 ≤ j ≤ m, y ∈ A

},orequivalentlythat

{w ⊕ z

| 1 ≤ j ≤ m} intersects A

, by running M (x, w ⊕ z

) for all

1 ≤ j ≤ m.

Part (iii) of the computation can be done deterministically, so this is a Σ

computation.

Proof of Claim 14.2. We can prove this lemma just by counting. First,

assume that x ∈ A.Then|A

|≤2

m−n

. For any choice of z

,... ,z

{y ⊕ z

| 1 ≤ j ≤ m, y ∈ A

} =



j=1

{y ⊕ z

| y ∈ A

BPP ⊆ Σ

∩ Π

An upper bound on the size of this set is



j=1

|{y ⊕ z

| y ∈ A

}| =



j=1

|≤m2

m−n

< 2

for suﬃciently large n.Thus

{y ⊕ z

| 1 ≤ j ≤ m, y ∈ A

} = {0, 1}

Now suppose x ∈ A.Then|R

|≤2

m−n

. Let us call z

,... ,z

bad if

for some w,

{w ⊕ z

| 1 ≤ j ≤ m}⊆R

good otherwise. We wish to show that there exists a good z

,... ,z

.But

each bad z

,... ,z

is determined by a subset of R

of size m,ofwhich

there are at most (2

m−n

)

,andastringw ∈{0, 1}

,ofwhichthereare

. Thus an upper bound on the number of bad z

,... ,z

m−n

)

m(m−n+1)

< 2

and the right-hand side is the total number of choices of z

,... ,z

,so

some z

,... ,z

must be good. 2

Supplementary Lecture B

Chinese Remaindering

The following is a very useful theorem with many applications in computer

science. It says that a large number can be faithfully represented as a

sequence of remainders modulo a list of small relatively prime moduli.

Let Z

denote the ring of integers modulo n. Recall that two positive

integers are relatively prime if they have no common factor except 1.

Theorem B.1 (Chinese Remainder Theorem) Let n

,... ,n

be pairwise relatively prime

positive integers, and let n =



i=1

.TheringZ

and the direct product

of rings Z

×···×Z

are isomorphic under the function

σ : Z

→ Z

×···×Z

σ(x)

def

=(x mod n

,... ,xmod n

This just says that the numbers modulo n and the k-tuples of numbers mod-

ulo n

,1≤ i ≤ k, are in one-to-one correspondence, and that arithmetic is

preserved under the map f . For example, the following table compares Z

to Z

× Z

x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

x mod 3 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2

x mod 5 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4