Kozen D.C. Theory of Computation

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

Lecture 9

The Polynomial-Time Hierarchy

The polynomial-time hierarchy (PH ) is a hierarchy of complexity classes

lying over P and inside PSPACE. It was ﬁrst identiﬁed by Stockmeyer [117].

It is most easily deﬁned in terms of alternating polynomial-time-bounded

TMs, although it was originally deﬁned in terms of oracle Turing machines.

The hierarchy is analogous in many ways to the arithmetic hierarchy, which

we introduce later in Lecture 35. However, unlike the arithmetic hierarchy,

it is not known whether PH is strict.

In this lecture and the next, we deﬁne PH in two diﬀerent ways, in terms

of ATMs and oracle TMs, and prove the equivalence of the two deﬁnitions.

We also give generic ≤

log

-complete problems for each level of the hierarchy.

Deﬁnition of PH in Terms of ATMs

Informally, a Σ

-machine (respectively, Π

-machine) is an ATM without

negations that on any input makes at most k alternations of ∨-and∧-

conﬁgurations along any computation path, beginning with ∨ (respectively,

∧).

Deﬁnition 9.1 A Σ

-machine is an ATM such that on any input, every computation path

can be divided into contiguous intervals such that

(i) in any interval, all conﬁgurations are either ∨-conﬁgurations or all

are ∧-conﬁgurations;

58 Lecture 9

(ii) there are at most k intervals; and

(iii) the ﬁrst interval consists of ∨-conﬁgurations.

A Π

-machine is similar, except we change (iii) to:

(iii



) the ﬁrst interval consists of ∧-conﬁgurations.

A Σ

-machine is just a nondeterministic TM. By convention, Σ

-andΠ

machines are deterministic TMs.

Deﬁnition 9.2 The complexity classes Σ

and Π

are deﬁned as follows.

def

= {L(M) | M is a polynomial-time-bounded Σ

-machine},

def

= {L(M) | M is a polynomial-time-bounded Π

-machine}.

Thus Σ

= NP,Π

=co-NP,andΣ

=Π

= P.

Lemma 9.3

=co-Σ

= {∼A | A ∈ Σ

∪ Π

⊆ Σ

k+1

∩ Π

k+1



⊆ PSPACE.

Here ∼A denotes the complement of A.

Proof. The ﬁrst equation is obtained by interchanging ∨-and∧-states.

This gives the dual machine, which accepts the complement of the set

accepted by the original machine (provided the machine halts along all

computation paths, which it does in this case because it is polynomial-

time-bounded). The second inclusion is immediate from the deﬁnition. The

third inclusion follows from the fact that PSPACE = APTIME ,inwhich

there are no restrictions on the number of alternations. 2

It is not known whether any of the inclusions in Lemma 9.3 are strict.

Generic Complete Problems

We can deﬁne generic problems that are complete for the various levels of

the polynomial-time hierarchy. Deﬁne

def

= {M#x#

| M

accepts x},

where M is any ATM and M

is M modiﬁed so as to halt on any com-

putation path that tries to alternate between ∨ and ∧ states more than k

The Polynomial-Time Hierarchy 59

times, beginning with an ∨, or tries to take more than m steps. In other

words, the computation tree of M

on any input is essentially the same as

that of M, except that it is artiﬁcially truncated to depth m and k alterna-

tions. Any leaves of the computation tree of M

that are not leaves of the

computation tree of M are either accept or reject conﬁgurations of M

according as the corresponding conﬁguration of M is an ∧-conﬁguration or

an ∨-conﬁguration, respectively.

Theorem 9.4 The set H

is ≤

log

-complete for Σ

Proof. To show that H

is in Σ

, we describe a polynomial-time-bounded

-machine N that accepts H

. The machine N ﬁrst checks that its input

is of the form M#x#

,whereM is a valid ATM description and x is a

valid encoding of a string over M’s input alphabet. It then simulates M

on input x, counting the number of simulated steps of M and the number

of alternations. In the simulation, N makes ∨-branches whenever M would

and ∧-branches whenever M would. Because the branching degree of M

may be arbitrarily large and that of N must be ﬁxed, it may take several

branches of N to simulate one branch of M; but this is ok, because the

number of alternations is the same. If during the simulation, the number

of steps of M exceeds m (the number provided in the input to N), or if M

tries to make more than k alternations, N halts on that computation path.

Otherwise, N accepts or rejects as M does.

It takes a small polynomial in the length of M#x#

to simulate one

step of M,andthereareatmostm steps simulated, so N runs in polynomial

time; moreover, the computation is Σ

.ThusH

∈ Σ

To show that H

is ≤

log

-hard for Σ

,letA ∈ Σ

be arbitrary. Then there

is a Σ

-machine M accepting A with time bound n

.Thusform = |x|

the computation trees of M and M

are essentially the same on input x;

that is, no truncation takes place. Thus M accepts x iﬀ M

accepts x iﬀ

M#x#

∈ H

. Therefore the map

x → M#x#

|x |

constitutes a reduction from A to H

, and this map is easily computed in

logspace. 2

Corollary 9.5 The set ∼H

is ≤

log

-complete for Π

Oracle Machines and Relativized Complexity Classes

Originally, the polynomial-time hierarchy was deﬁned in terms of ora-

cleTuringmachines.Anoracle TM is like an ordinary TM, except it

is equipped with an oracle, a means of answering membership questions

60 Lecture 9

about some set B in one step. It is useful for studying computation relative

to free knowledge about the set B.

There are a few equivalent ways of deﬁning oracle machines formally.

In one deﬁnition, the machine is equipped with a special write-only oracle

query tape on which ﬁnite strings can be written. The ﬁnite control also

contains a special oracle query state as well as a special “yes” state and a

special “no” state. When the machine enters the oracle query state, it is

asking whether the string y currently written on the oracle tape is in B.

The machine magically moves to the “yes” state if y ∈ B and to the “no”

state if y ∈ B. There is no explicit representation of the set B. The oracle

must give the same answer if queried with y again in the future. Note that

the same oracle machine may be used with diﬀerent oracles; the results of

the oracle queries will be diﬀerent.

Here is another equivalent deﬁnition. An oracle machine is a TM that in

addition to its ordinary input and worktapes is equipped with a special one-

way-inﬁnite read-only input tape on which some inﬁnite string is written.

The extra tape is called the oracle tape, and the string written on it is called

the oracle. The machine can move its oracle tape head one cell in either

direction in each step and make decisions based on the symbols written on

the oracle tape. Other than that, it behaves exactly like an ordinary Turing

machine.

In the latter deﬁnition, we usually think of the oracle as a speciﬁcation

of a set B ⊆ N. If the oracle is an inﬁnite string over {0, 1},thenwecan

regard it as the characteristic function of B,wherethenth bit of the oracle

string is 1 iﬀ n ∈ B.

Deﬁnition 9.6 Let B be a set and let C be a complexity class.

def

= {L(M) | M is a deterministic polynomial-time-bounded

oracle machine with oracle B},

def

= {L(M) | M is a nondeterministic polynomial-time-

bounded oracle machine with oracle B},

def



B∈C

def



B∈C

Other relativized complexity classes such as PSPACE

and PSPACE

can

be deﬁned similarly. These classes are called relativized complexity classes.

If B is ≤

-complete for C,thenP

= P

and NP

= NP

.Thisis

because the reduction from some arbitrary A ∈ C to B can be performed

before an oracle query is made. For example, P

= P

SAT

and NP

SAT

The Polynomial-Time Hierarchy 61

Deﬁnition 9.7 We write A ≤

B if A ∈ P

. The relation ≤

is called polynomial-time

Turing reducibility or Cook reducibility.

Essentially, A ≤

B means that A can be computed in polynomial time,

given free information about B.IfA ≤

B then A ≤

B, but the converse

would imply NP =co-NP, because SAT ≤

∼SAT.

Deﬁnition of PH in Terms of Oracle Machines

Theorem 9.8 Consider the hierarchy

NP ⊆ NP

⊆ NP

⊆ ··· .

More formally, deﬁne

def

= NP,

k+1

def

= NP

Then NP

=Σ

for all k ≥ 1.

We prove this theorem next time.

Lecture 10

More on the Polynomial-Time Hierarchy

Recall from the last lecture the hierarchy

NP ⊆ NP

⊆ NP

⊆ ···

deﬁned in terms of oracle machines. Formally, we deﬁned

def

= NP

k+1

def

= NP

Recall also that Σ

is the class of sets accepted by polynomial-time-

bounded alternating TMs that make at most k alternations of ∨-and

∧-conﬁgurations along any computation path, beginning with ∨.Inthis

lecture we show that these two deﬁnitions characterize the same hierarchy

of complexity classes.

Theorem 10.1 NP

=Σ

for all k ≥ 1.

Proof. This is proved by induction on k. The basis k = 1 is immediate

from the deﬁnitions: NP

=Σ

= NP.

For the induction step, we need only show that NP

=Σ

k+1

.Weshow

the inclusion in both directions separately, the easier direction ﬁrst.

(⊇) For this inclusion, assume that we have a Σ

k+1

-machine M run-

ning in time n

, A = L(M ). We wish to show that A ∈ NP

. Let the

More on the Polynomial-Time Hierarchy 63

conﬁgurations of M be encoded as strings over a ﬁnite alphabet ∆ in some

reasonable way. We can assume that all conﬁgurations reachable from the

start conﬁguration on any input x, |x| = n, are represented as strings in

∆

Now consider the set

def

= {α | α is an ∧-conﬁguration of M, |α| = n

,andα leads to

acceptance via a Π

computationintimeatmostn

Membership in D can be determined by a polynomial-time-bounded Π

machine that just simulates M starting from the conﬁguration α; therefore,

D ∈ Π

and ∼D ∈ Σ

.Moreover,M accepts x iﬀ there exists a computation

path leading from the start conﬁguration through only ∨-conﬁgurations to

some α ∈ D.

Thus A can be accepted by a nondeterministic polynomial-time-

bounded oracle machine with oracle ∼D that on input x guesses a computa-

tion path from the start conﬁguration of M through only ∨-conﬁgurations

to some ∧-conﬁguration α, then consults the oracle to check whether α ∈ D.

( ⊆) For this inclusion, assume that we have a nondeterministic n

time-bounded oracle machine M with oracle B ∈ Σ

, and let A = L(M).

We wish to show that A ∈ Σ

k+1

Build a Σ

k+1

machine N that works as follows. On input x, N will begin

by simulating M on input x, except that every time M wants to query the

oracle on some string y, N nondeterministically guesses the answer that

the oracle would return (that is, whether y ∈ B) and remembers y and the

guessed answer. It continues the simulation until M arrives at an accept

or reject state, which must happen by time n

.IfM wants to reject at

that point, N just rejects. If M wants to accept, N has to verify that the

guessed oracle answers were correct.

So far the computation tree of N looks like the computation tree of M,

exceptthatateachoraclequery,N has a nondeterministic branch for the

two possible responses of the oracle. Up to this point N has made only

existential branches. At each leaf there is a process with a list of oracle

queries and guessed responses that need to be veriﬁed. The lists may be

diﬀerent for diﬀerent computation paths, because later queries may depend

on the responses to earlier queries, but all lists are at most n

in length.

Thus each process has a list y

,... ,y

of oracle queries for which the

guessed response from the oracle was positive and a list z

,... ,z



for which

the guessed response was negative. The total combined length of the y

and

concatenated together is at most n

, because the machine had to write

them all down on its oracle query tape. It must now verify with a Σ

k+1

computation in polynomial time that y

∈ B,1≤ i ≤ m,andz

∈ B,

1 ≤ j ≤ .ThatΣ

k+1

computation combined with the Σ

computation up

to this point is still a Σ

k+1

computation.

64 Lecture 10

We have reduced the problem to showing that for B ∈ Σ

,theset

# ···#y

##z

# ···#z



| y

∈ B,1≤ i ≤ m; z

∈ B,1≤ j ≤ }

is in Σ

k+1

.Eachguessy

∈ B can be veriﬁed with a Σ

computation, and

each guess z

∈ B can be veriﬁed with a Π

computation.

Our ﬁrst thought might be to make an (m + )-way ∧-branch, each

process taking a y

or z

and independently verifying y

∈ B with a Σ

computation and z

∈ B with a Π

computation. Unfortunately, this does

not work, because it results in a Π

k+1

computation, which cannot in general

be simulated by a Σ

k+1

computation.

Instead, we do the ﬁrst round of existential guessing for all the y

se-

quentially. Let n

be the time bound on a Σ

-machine for B. Nondeter-

ministically guess binary strings w

,... ,w

, each of length n

.Thistakes

time at most mn

≤ n

c+d

. These strings will direct the ﬁrst round of ex-

istential guesses in the Σ

computations to verify y

∈ B.Nowmakean

(m + )-way universal branch, each process taking a positive query y

or a

negative query z

. So far the computation is Σ

. For each negative query

,wejustverifyz

∈ B usingaΠ

computation for ∼B. This combines

with the preceding Σ

computation to give a Σ

k+1

computation. For each

positive query y

, we simulate the Σ

computation for B to verify y

∈ B,

but use the guessed w

to direct the ﬁrst level of existential branches, thus

making the ﬁrst level deterministic. The remaining computation is Π

k−1

so the total computation is Σ

k+1

. 2

The trick we used at the end is essentially an instance of skolemization,

acommontechniqueusedinlogic:



i∈A



w∈B

ϕ(i, w)=



f:A→B



i∈A

ϕ(i, f(i)).

This is actually a generalized version of the distributive law of Boolean al-

gebra. In our application, A = {1, 2,... ,m}, B = {0, 1}

,andϕ(i, w)says

that y

is accepted by a Π

k−1

machine that simulates the Σ

computation

of B, but uses w to direct the ﬁrst level of nondeterministic choices.

Ordinarily an application of skolemization or the distributive law results

in an exponential blowup in the size of the formula: if |A| = m and |B | = r,

then |A → B | = r

. However, here we are ok, because |A| = m ≤ n

and |B | =2

,so|A → B | =(2

)

≤ (2

)

c+d

. The functions

f : A → B in our application represent the possible choices of binary strings

,... ,w

, and these can be guessed in time at most n

c+d

Another characterization of the polynomial time hierarchy can be given

in terms of quantiﬁed expressions. Let t be a numeric term. Deﬁne the

bounded quantiﬁers ∃

and ∀

that limit the quantiﬁcation to range over

More on the Polynomial-Time Hierarchy 65

those strings whose length is bounded by the value of t. We can consider

∃

and ∀

to be abbreviations for

∃

yϕ(y)

def

⇐⇒ ∃y |y |≤t ∧ ϕ(y)

∀

yϕ(y)

def

⇐⇒ ∀y |y |≤t → ϕ(y).

Theorem 10.2 AsetA is in Σ

if and only if there is a deterministic polynomial-time

computable (k +1)-ary predicate R and constant c such that

A = {x |∃

|x |

∀

|x |

∃

|x |

··· Q

|x |

R(x, y

,... ,y

)},

where Q = ∃ if n is odd, ∀ if n is even.

Proof. Miscellaneous Exercise 32. 2

Lecture 11

Parallel Complexity

In this lecture we take a look at parallel computation from a complexity-

theoretic point of view. Many machine models have been developed to

study parallelism, perhaps the most prominent of which are parallel ran-

dom access machines (PRAMs) and uniform families of circuits. Many of

these models can simulate one another with relatively low overhead, so the

parallel complexity classes they deﬁne are robust and natural.

Uniform Families of Circuits and NC

Uniform families of circuits were ﬁrst deﬁned and studied as a model of

parallel complexity by Allan Borodin [22]. The most popular parallel com-

plexity class deﬁned in terms of uniform circuits is NC ,forNick’s class,

named after Nicholas Pippenger. The class ﬁrst appeared in print under

that name in a paper of Stephen Cook [32], who attributed the deﬁnition

of the class to Pippenger, except for the uniformity condition.

NC lies between NLOGSPACE and P . It is to parallel computation as

P is to sequential computation—a robust and natural (albeit imperfect)

approximation to the notion of eﬃciently parallelizable.

Many eﬃcient NC algorithms have been developed for important prob-

lems. In particular, it has been shown that virtually all of linear algebra

can be done in NC . Other problems have deﬁed parallelization; for ex-

ample, there is no known eﬃcient parallel algorithm for the circuit value