Kozen D.C. Theory of Computation

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

Parallel Complexity 67

problem or for calculating integer greatest common divisors (gcd); however,

polynomial gcd is in NC .

The P = NP question asks whether a host of important combinatorial

problems have eﬃcient sequential solutions. The NC = P question, in

turn, asks whether a host of problems that are known to have eﬃcient

sequential solutions have eﬃcient parallel solutions. Any problem that is

≤

log

-complete for P,suchasCVP,isinNC iﬀ P = NC .

One popular deﬁnition of NC is in terms of PRAMs: a set is in NC if it

has a (log n)

O(1)

-time (polylog-time) solution on a PRAM using polynomi-

ally many processors. This model is well suited to the analysis of parallel

graph algorithms and other combinatorial problems. We concentrate on an

alternative deﬁnition in terms of uniform families of circuits, which is more

useful in algebraic problems. In this deﬁnition, a set is in NC if it has a

logspace-uniform family of Boolean circuits of polylog depth and polyno-

mial size. Formally:

Deﬁnition 11.1 (Cook [32]) A family of Boolean circuits C

,... is a logspace-

uniform family of Boolean circuits of polylog depth and polynomial size

if:

(i) C

has n input wires and is composed of ∨-, ∧-, and ¬-gates;

(ii) C

is of depth at most (log n)

O(1)

(polylog depth), where the depth is

the length of the longest path from an input to an output;

(iii) C

is has no more than n

O(1)

gates (polynomial size); and

(iv) the family is logspace-uniform, which means that there is a logspace

transducer that produces the circuit C

on input 0

AsetA ⊆{0, 1}

∗

is in NC if there exists such a family in which each C

has one output wire, and for all x ∈{0, 1}

∗

, x ∈ A iﬀ C

|x |

(x)=1.

The uniformity condition (iv) is there mostly for technical reasons. It

allows PRAMs and other models to simulate circuits. It is a very reasonable

restriction, because in most applications the circuits can be constructed

that easily. Note that without some kind of uniformity condition, there

would exist trivial circuit families that decide undecidable problems; for

example, take C

to be a circuit with a single gate that outputs 1 if TM

halts on input n, 0 otherwise.

Boolean Matrix Multiplication

Here is an example of a family of logspace-uniform, polylog-depth circuits

to compute the Boolean matrix product of two n × n matrices. The nth

circuit has 2n

input wires and n

output wires and computes the Boolean

68 Lecture 11

matrix product of two given n × n input matrices. (For the other input

sizes, take some trivial circuit.) The size of the nth circuit will be O(n

)

and the depth will be log n.

The inputs supplied to the nth circuit are the entries of the two given

matrices A, B. In the ﬁrst step, the circuit computes A

∧ B

in parallel

for all choices of i, j, k. This takes one step and n

∧-gates. Then for each

i and k, the Boolean sums



∧ B

) are computed in parallel in a

treelike fashion. This requires depth log n and O(n) gates for each i and k,

or O(n

) in all. The outputs are

(AB)



∧B

). (11.1)

The family is logspace-uniform, because the circuits are quite simple to

describe and could be created by a logspace transducer. Note that the n

subcircuits that produce (11.1) are identical except for the indices i, k,

which take only logspace to write down in binary.

Reﬂexive Transitive Closure

Here is another example. We describe a family of logspace-uniform, polylog-

depth, and polynomial-size circuits to compute the reﬂexive transitive clo-

sure R

∗

of a given binary relation R on a set of size n. Recall that R

∗

consists of pairs (u, v) such that there exists an R-path of length zero or

greater from u to v.

Suppose R is given by its n × n adjacency matrix. Note that

∗



i≥0



n−1

i=0

=(R ∨ I)

n−1

(11.2)

where I = R

is the n × n identity matrix. Note that (R

)

=1ifthere

is an R-path of length exactly i from u to v. We can limit the powers of R

in the Boolean sum (11.2) to n − 1 (or any greater ﬁnite number) because

if there exists a path at all from u to v, then there exists one of length at

most n − 1 obtained by cutting out loops.

The circuit that computes R

∗

from R has n

input wires, on which are

supplied the Boolean entries of the adjacency matrix of R. The circuit ﬁrst

computes R ∨I, then repeatedly squares the matrix log n times to obtain

∗

(R ∨ I)

, (R ∨ I)

, ... .

Each squaring step takes log n depth and polynomial size by the previous

example, and there are log n squaring steps, so the total depth is (log n)

Again, the family is logspace-uniform, because the circuits are quite

simple to describe and could be constructed by a logspace transducer.

Parallel Complexity 69

Relation to Time-Space Classes

In order to describe the relationship of NC to conventional time and space

complexity, we need to deﬁne a family of complexity classes for alternating

machines that simultaneously keep track of time, space, and number of

alternations.

Deﬁnition 11.2 The class

STA(S(n),T(n),A(n))

is the class of all sets accepted by ATMs that are simultaneously S(n)-space-

bounded, T (n)-time-bounded, and make at most A(n) alternations on inputs

of length n.A

∗

in any position means “don’t care.” In other words, no

bound is imposed. We also write Σ or Π in the third position if we need to

specify that the alternations should start with an ∨ or ∧, respectively.

For example,

LOGSPACE = STA(log n, ∗, 0),

NLOGSPACE = STA(log n, ∗, Σ1),

P = STA(log n, ∗, ∗)=STA(∗,n

O(1)

, 0),

NP = STA(∗,n

O(1)

, Σ1),

= STA(∗,n

O(1)

, Σk),

= STA(∗,n

O(1)

, Πk),

PSPACE = STA(∗,n

O(1)

, ∗)=STA(n

O(1)

, ∗, 0),

and so on.

The following theorem of Ruzzo relates NC to more conventional com-

plexity classes.

Theorem 11.3 (Ruzzo [106]) NC = STA(log n, ∗, (log n)

O(1)

One can see from this theorem that NLOGSPACE ⊆ NC ⊆ P ,be-

cause

NLOGSPACE = STA(log n, ∗, Σ1),

NC = STA(log n, ∗, (log n)

O(1)

P = STA(log n, ∗, ∗).

We prove this theorem next time.

Lecture 12

Relation of NC to Time-Space Classes

Recall that NC is the class of sets computable by polylog-depth,

polynomial-size, logspace-uniform families of Boolean circuits C

,... .

The following theorem relates this class to more conventional time-space

classes and places NC between NLOGSPACE and P.

Theorem 12.1 (Ruzzo [106]) NC = STA(log n, ∗, (log n)

O(1)

Proof. We show the inclusion in both directions.

( ⊆) We said before that logspace-uniform means that there is a logspace

transducer M that on input 0

produces the nth circuit C

. Let us be a

little more careful about what we mean by this.

Because C

has only polynomially many gates, there is a naming scheme

in which each gate can be named with a string of length O(log n). We

reserve the names 1, 2,... ,n in binary for the names of the n input ports.

On input 0

, the logspace transducer M must produce

(i) an enumeration of the names of all gates in the circuit C

;

(ii) for each gate c, a tag indicating whether c is an ∧-gate, an ∨-gate, a

¬-gate, or an input port;

(iii) a list of all wires (c, d) in the circuit, where c and d are legal gate

names enumerated in (i); and

Relation of NC to Time-Space Classes 71

(iv) for one of the gates c, a tag indicating that c is the output gate.

We assume for simplicity that ∨-and∧-gates have exactly two inputs, ¬-

gates exactly one, and input ports none. Circuits with unbounded fan-in

can be simulated with at most an O(log n) factor increase in depth and at

most double the size.

Because we can construct the dual circuit in logspace (the construction

is similar to the proof of Lemma 7.3), we can assume without loss of gen-

erality that C

has no negate gates other than those applied immediately

to inputs. That is, if d is a negate gate and (c, d) is the unique wire coming

into d,thenc is an input port.

Now we design an alternating logspace machine N to simulate this

family of circuits. On input x of length n,themachineN will use M to

produce C

on the ﬂy and evaluate C

(x). First N runs M to ﬁnd the

name of the output gate and its type, which it writes on its worktape. Now

suppose some process of N has the name and type of a gate d written on

its worktape.

• If d is an ∧-oran∨-gate, it starts M from scratch, enumerating wires

to ﬁnd the two wires (c, d), (c



,d) coming into d. When it has found

these wires, it makes an existential or universal branch according as

d is an ∨-or∧-gate, respectively. Each of the two subprocesses takes

one of c and c



and repeats.

• If d is an input port 1 ≤ d ≤ n, N accepts or rejects according as the

dth bit of the input x is 1 or 0, respectively.

• If d is a ¬-gate, N runs M to ﬁnd the input port c such that (c, d)is

the unique wire coming into d. It accepts or rejects according as the

cth bit of the input x is 0 or 1, respectively.

The machine N needs no more than logarithmic space to do any of these

tasks, because all it has to remember at any time is the name of the current

gate c it is visiting. Moreover, the number of alternations that N makes is

bounded by the depth of the circuit it is simulating, which is (log n)

O(1)

(⊇) For this inclusion, assume that we are given an alternating logspace

machine N making at most (log n)

alternations on inputs of length n.We

wish to construct a logspace-uniform family of circuits of polylog depth

and polynomial size simulating N.

As argued in Theorem 7.4, we can assume without loss of generality that

N runs in polynomial time. Encoding conﬁgurations in some reasonable

way as strings over a ﬁnite alphabet, each conﬁguration reachable from the

start conﬁguration on an input of length n can be represented as a string

of length log n,andthereareonlyn

such conﬁgurations for some constant

72 Lecture 12

For inputs x ∈{0, 1}

, we can represent the next-conﬁguration rela-

tion of N on input x as an n

× n

Boolean matrix R

whose rows and

columns are indexed by conﬁgurations; thus R

(α, β) = 1 if conﬁguration

β is an immediate successor of conﬁguration α on input x according to the

transition rules of N.

The circuit C

will ﬁrst compute the entries of R

. Because conﬁgu-

rations are encoded as strings of length O(log n), the pairs (α, β) can also

serve as the names of the gates for purposes of generating the circuit uni-

formly in logspace. A logspace machine can easily compare α and β and

determine whether there is a possible transition from α to β and build a

trivial circuit to output the value of R

(α, β). This will depend on the in-

put symbol being scanned in conﬁguration α, so the circuit will access the

ith input port of C

,wherei is the position of N’s input head encoded in

the conﬁguration α. The depth of the circuit constructed so far is 1.

Once C

has computed R

, it constructs matrices for the relations

def

= {(α, β) | R

(α, β) = 1 and type(α)=type(β)},

def

= {(α, β) | R

(α, β) = 1 and type(α) =type(β)},

∗

def

= reﬂexive transitive closure of S

and the product S

∗

. A pair (α, β)isinS

∗

if there is a computation

path in N of length zero or greater on input x from α to β such that all

conﬁgurations on the path have the same type. A pair (α, β)isinS

∗

there is a computation path from α to β such that all conﬁgurations on the

path except β havethesametypeasα,andβ has a diﬀerent type.

The matrices S

and T

are just the componentwise Boolean meet of

with the relation {(α, β) | type(α)=type(β)} and its complement,

respectively. The reﬂexive transitive closure S

∗

and the product S

∗

can

be computed using constructions given in Lecture 11.

Now think of the computation tree of N on input x, |x| = n,asdi-

vided into (log n)

levels. Within each level, either all conﬁgurations are

existential or all are universal.



∨

∧

∨

∧

Number the levels 0, 1, 2,... from bottom to top. An existential conﬁg-

uration α at level i + 1 is an accepting conﬁguration iﬀ there exists a

conﬁguration β at level i such that S

∗

(α, β)=1andβ is an accepting

Relation of NC to Time-Space Classes 73

conﬁguration. A universal conﬁguration α at level j + 1 is an accepting

conﬁguration iﬀ for all existential conﬁgurations β at level j such that

∗

(α, β)=1,β is an accepting conﬁguration.

Now the circuit computes a series of Boolean vectors b

,...,eachof

length n

and indexed by conﬁgurations, such that b

(α)=1iﬀα is an

accepting conﬁguration at the ith level.

For existential levels i+1, the circuit computes the matrix–vector prod-

uct

i+1

:= S

∗

For universal levels i + 1, the circuit computes

i+1

:= ¬(S

∗

(¬b

)),

where ¬ applied to a vector is interpreted componentwise.

We can take the initial vector b

to be the zero vector. Recalling our

convention that an accept conﬁguration is an ∧-conﬁguration with no suc-

cessors and a reject conﬁguration is an ∨-conﬁguration with no successors,

this does the right thing. For example, an ∧-conﬁguration α at level 1 is an

accepting conﬁguration if there does not exist a computation path leading

to an ∨-conﬁguration, in which case b

(α)=1.

One can show by induction that a conﬁguration α of the appropriate

type is an accepting conﬁguration at the ith level iﬀ b

(α) = 1. The output

value is b

(log n)

(start), where start is the start conﬁguration.

There are at most (log n)

levels, and each level requires log n depth

and polynomial size for the matrix–matrix and matrix–vector products and

other Boolean operations. Moreover, the circuit is uniform at each level and

can be generated by a logspace transducer. 2

Lecture 13

Probabilistic Complexity

There are many instances of problems with eﬃcient randomized or proba-

bilistic algorithms for which no good deterministic algorithms are known.

In the next few lectures we take a complexity-theoretic look at probabilistic

computation. We deﬁne a simple model of randomized computation, the

probabilistic Turing machine, deﬁne some basic probabilistic complexity

classes, and outline the relationship of these classes to conventional time

and space classes. Our main result, which we prove next time, is that the

class BPP of sets accepted by polynomial-time probabilistic algorithms

with error probability bounded below

is contained in Σ

∩ Π

[112].

Many probabilistic algorithms have only a one-sided error; that is, if the

input string is in the set, then the algorithm accepts with high probability;

but if the string is not in the set, then the algorithm rejects always. The

corresponding probabilistic complexity class is known as RP and is called

random polynomial time.

Discrete Probability

Before we begin, let us recall some basic concepts from discrete probability

theory.

Law of Sum The law of sum says that if A is a collection of pairwise

disjoint events, that is, if A ∩ B = ∅ for all A, B ∈ A, A = B, then the

Probabilistic Complexity 75

probability that at least one of the events in A occurs is the sum of the

probabilities:

Pr(



A)=



A∈A

Pr(A).

Expectation The expected value EX of a discrete random variable X is the

weighted sum of its possible values, each weighted by the probability that

X takes on that value:

EX =



n · Pr(X = n).

For example, consider the toss of a coin. Let

X =



1, if the coin turns up heads

0, otherwise.

(13.1)

Then EX =

if the coin is unbiased. This is the expected number of heads

in one ﬂip. Any function f(X) of a discrete random variable X is a random

variable with expectation

Ef(X)=



n · Pr(f(X)=n)=



f(m) · Pr(X = m).

It follows immediately from the deﬁnition that the expectation function

E is linear. For example, if X

are the random variables (13.1) associated

with n coin ﬂips, then

E(X

+ X

+ ···+ X

)=EX

+ EX

+ ···+ EX

and this gives the expected number of heads in n ﬂips. The X

need not be

independent; in fact, they could all be the same ﬂip.

Conditional Probability and Conditional Expectation The conditional prob-

ability Pr(A | B) is the probability that event A occurs given that event B

occurs. Formally,

Pr(A | B)=

Pr(A ∩B)

Pr(B)

The conditional probability is undeﬁned if Pr(B)=0.

The conditional expectation E(X | B) is the expected value of the ran-

dom variable X given that event B occurs. Formally,

E(X | B)=



n · Pr(X = n | B).

If the event B is that another random variable Y takes on a particular

value m, then we get a real-valued function E(X | Y = m)ofm.Composing

76 Lecture 13

this function with the random variable Y itself, we get a new random

variable, denoted E(X | Y ), which is a function of the random variable Y .

The random variable E(X | Y ) takes on value n with probability



E(X|Y =m)=n

Pr(Y = m),

where the sum is over all m such that E(X | Y = m)=n. The expected

value of E(X | Y )isjustEX:

E(E(X | Y )) =



E(X | Y = m) · Pr(Y = m)



n · Pr(X = n | Y = m) · Pr(Y = m)



n ·



Pr(X = n ∧ Y = m) (13.2)



n · Pr(X = n)

= EX

(see [39, p. 223]).

Independence and Pairwise Independence A set of events A are independent

if for any subset B ⊆ A,

Pr(



B)=



A∈B

Pr(A).

They are pairwise independent if for every A, B ∈ A, A = B,

Pr(A ∩B)=Pr(A) · Pr(B).

For example, the probability that two successive ﬂips of a fair coin both

come up heads is

Pairwise independent events need not be independent. Consider the

following three events:

• The ﬁrst ﬂip gives heads.

• The second ﬂip gives heads.

• Of the two ﬂips, one is heads and one is tails.

The probability of each pair is

, but the three cannot happen simultane-

ously.

If A and B are independent, then Pr(A | B)=Pr(A).