Kozen D.C. Theory of Computation

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

Lecture 27

Safra’s Construction

In Lecture 26 we gave two incorrect constructions for the determinization

of B¨uchi automata. The ﬁrst constructed a deterministic automaton that

accepted too many strings; the second erred in the opposite direction by

accepting too few strings.

In this lecture we give a third construction due to Safra [107] that is

a compromise between the ﬁrst two. This construction correctly produces

a deterministic Rabin automaton equivalent to a given nondeterministic

B¨uchi automaton.

For a given nondeterministic B¨uchi automaton B =(Q, Σ, ∆,s,F)

with n states, the equivalent deterministic Rabin automaton R will have

O(n log n)

states and n pairs in the acceptance condition.

Say we have a collection of colors, each with an associated bell and

buzzer. There are several tokens of each color, which are placed on the

states of B at various times, moved around, and sometimes removed. A

stack is a pile of tokens on a state. The height of a stack σ is the number

of tokens in σ and is denoted |σ |.

Atokenisin play at time t if it is in some stack on some state at time

t.Acolorisin play at time t if it is the color of a token in play at time t.

A color is visible at time t if it is the color of the top token of some stack

at time t.

The colors in play at time t are ordered by age, which is the time they

last came into play. All tokens of any one color in play will always come into

168 Lecture 27

play at the same time, therefore will have the same age. When we bring a

new token into play, we always place it on top of a stack; when we remove

a token from play, we always remove all the tokens above it; and when we

move tokens around, we always move an entire stack at once. Thus it is an

invariant of the simulation that the tokens on any stack are always ordered

by age from the oldest on the bottom to the youngest on top.

The stacks are linearly ordered at time t as follows: σ $

τ if either

• σ is a proper extension of τ (that is, τ can be obtained by removing

tokens from the top of σ); or

• neither σ nor τ is an extension of the other and σ is lexicographically

older than τ; that is, starting from the bottom and moving up, at the

ﬁrst position where σ and τ diﬀer in color, the color of σ is older.

The ages of colors and the order $

are time-dependent, because colors

cangoinandoutofplay.

The simulation starts with a single white token on the start state s.

Now assume we have stacks of colored tokens on the states of B at time

t. To construct the conﬁguration at time t + 1, execute the following three

steps. (In this construction, the intermediate conﬁgurations are transitory

and do not count as states of the simulating automaton.)

Move Suppose the next input symbol is a. For each state q,removethe

stack currently on q.Foreachp ∈ ∆(q, a), clone the stack that was on q

andtrytoputitonp. If we try to put more than one stack on p,resolve

in favor of the $

-least stack. If any color completely disappears from the

board in this process, buzz its buzzer.

Cover For each accept state q ∈ F , place a token of an unused color on top

of q’s stack. For this purpose we bring k unused colors into play, where k is

the number of distinct visible colors on states q ∈ F . If two stacks on two

diﬀerent accept states have the same visible color, then we cover them with

the same new color. We bring the new colors into play in some arbitrary

order to determine their relative age, but the order is not important.

This is the only way new colors can come into play; thus it is an invariant

of the simulation that if a token of color c in play is directly over a token of

color d, then all tokens of color c in play are directly over a token of color

Audio Check For every invisible color c in play, ring its bell and remove all

tokens above any token of color c. Buzz the buzzers of the removed tokens.

Note that if any token is removed in this process, then all tokens of that

color are removed. There may be more than one invisible color in play, but

the order in which we process them does not matter.

Safra’s Construction 169

After these three steps are executed, there are at most n colors remain-

ing in play; otherwise there must be an invisible one, contradicting the

Audio Check step.

Claim 27.1 B accepts x iﬀ there is a color whose bell rings inﬁnitely often but whose

buzzer buzzes only ﬁnitely often.

Proof. Suppose there is a color, say cyan, whose bell rings inﬁnitely often

but whose buzzer buzzes only ﬁnitely often. Let t

,... be the times at

which cyan’s bell rings after its buzzer has already buzzed for the last time.

From t

on, cyan is continuously in play, otherwise its buzzer would have

buzzed. At the times t

, all cyan tokens are visible. Between t

and t

i+1

each cyan token gets covered with another token of a diﬀerent color, because

the only way cyan’s bell can ring at time t

i+1

is if cyan becomes invisible.

Thus for every state q with a cyan token at time t

i+1

,thereisasegmentof

a run from some state with a visible cyan token at time t

through a state

of F to q. As in the previous lecture, K¨onig’s lemma (Lemma 26.1) can be

used to construct a run with inﬁnitely many occurrences of states in F .

Conversely, suppose there is an accepting run ρ of B.Letσ

be the stack

on the state of ρ at time t.Letm = lim inf |σ

|;thatis,m is the maximum

height such that from some point on, the stacks along ρ reach height m and

then never go below height m again. Note that m ≥ 1 because white (the

oldest color) is always in play, and m ≤ n because there are at most n colors

in play. From some point on, the stack is of height at least m, and inﬁnitely

often exactly m. After that point, the colors on the stack at height m and

below may change due to being replaced by a $

-lesser stack in the Move

step, but this can happen only ﬁnitely often because lexicographic order

on the age space ω

is well-founded. So from some point on, the colors at

height m and below do not change. Say the color at height m at this point

is magenta. Then inﬁnitely often after that point, the run ρ goes through a

state of F , because it is an accepting run, at which point the stack acquires

a new token; but sometime after that the stack must shrink back to height

m again, and the only way that can happen is if magenta’s bell rings. Thus

magenta rings inﬁnitely often and buzzes only ﬁnitely often. 2

A state of the simulating Rabin automaton R will consist of a stack of

tokens (possibly empty) on each state of B, the current ordering $

,and

an indication of which bells rang. Each token conﬁguration can be speciﬁed

by a map Q →{colors}∪{none} giving the top color of the stack on each

state and a map {colors}→{colors}∪{none} telling for each color in play

the color immediately below it. There are at most n!orderings$

and 2

ways the bells can ring. Thus there are at most n

·n

·n! ·2

O(n log n)

states in all. The acceptance condition consists of n pairs, one for each

color.

We have shown

170 Lecture 27

Theorem 27.2 (Safra [107]) Every nondeterministic B¨uchi automaton with n states can

be simulated by a deterministic Rabin automaton with at most 2

O(n log n)

states and n pairs in the acceptance condition.

Lecture 28

Relativized Complexity

Many fundamental questions in complexity theory remain unanswered.

Probably the most important of these is the P = NP question. Although

it is generally believed that P = NP —mainly because it is inconceivable

how one might perform an exhaustive search through exponentially many

candidates in polynomial time—we have up to now been unable to prove

this formally.

In trying to understand this question and similar questions regarding

containment and separation of complexity classes, researchers have looked

at relativized versions, for which answers are somewhat easier to obtain.

Fairly early on, Baker, Gill, and Solovay [10] constructed oracles A and

B such that P

= NP

and P

= NP

(oracle Turing machines and

relativized complexity classes were deﬁned in Lecture 9). We present these

results below.

Rise and Fall of the Random Oracle Hypothesis

Not long after the Baker–Gill–Solovay results, Bennett and Gill [12] showed

that with respect to a random oracle C (every element is either in or out of

C with probability

), P = NP with probability 1. This and similar results

for other classes agreed well with the generally accepted beliefs about what

happens in the corresponding unrelativized cases. These observations led to

the random oracle hypothesis: every containment or separation result that

172 Lecture 28

holds with probability 1 with respect to a random oracle also holds in the

unrelativized case. Intuitively, as the argument went, one should be able to

get no more information from a random oracle than from no oracle at all.

This conjecture went through a series of qualiﬁcations and reformulations

to rule out simple counterexamples that kept popping up, ultimately to be

refuted by Chang et al. in 1994 [27]: with respect to a random oracle C,

= PSPACE

with probability 1.

Relativized P

= NP

Theorem 28.1 There exists a recursive oracle A such that P

= NP

Proof. This is the easier of the two relativized P versus NP results. For

the oracle A we can take QBF, the set of true quantiﬁed Boolean formulas,

a PSPACE -complete set. Then

PSPACE ⊆ P

QBF

⊆ NP

QBF

⊆ NPSPACE

QBF

⊆ NPSPACE ⊆ PSPACE .

The ﬁrst inclusion holds because membership in a set in PSPACE can be

determined by reducing to QBF, then consulting the oracle. The next-to-

last inclusion holds because an NPSPACE machine has enough space to

decide membership in QBF directly without consulting the oracle. The last

inclusion is Savitch’s theorem. 2

The following result is somewhat harder and requires diagonalization.

Theorem 28.2 There exists a recursive oracle B such that P

= NP

Proof. LetΣcontainatleasttwoelements.LetC ⊆ Σ

∗

be any oracle,

and consider the set

def

= {x ∈ Σ

∗

|∃y ∈ C |y | = |x|}.

That is, x ∈ E

if C contains an element of the same length as x.Theset

can be accepted by a nondeterministic oracle machine N with oracle

C that operates as follows. On input x, guess a string y of the same length

as x, then query the oracle C to determine whether y ∈ C. Regardless of

the oracle, this is a nondeterministic polynomial time algorithm, therefore

∈ NP

for any C.

Now we construct by diagonalization an oracle B such that E

=

L(M

) for any deterministic polynomial time oracle machine M.This

says that E

∈ NP

− P

. The idea behind the construction is that a

polynomial-time-bounded oracle machine M has only time enough to ask

Relativized Complexity 173

polynomially many questions of the oracle, but there are exponentially

many strings of length n. This allows us to adjust the oracle by throwing

in or leaving out elements that M never looks at, thereby causing M to

have been wrong.

Let M

,... be a list of all deterministic polynomial time bounded

oracle machines. Assume without loss of generality that each M

is equipped

with a uniform clock and parameter c such that M

shuts itself oﬀ after n

steps; thus for each i, the time bound n

of M

is recognizable from the

description of M

We construct the oracle B as the limit of a sequence of ﬁnite approx-

imations. Each approximation B

is a partial function B

:Σ

∗

→{0, 1}

with ﬁnite domain. B

(x)=1meansx ∈ B, B

(x)=0meansx ∈ B,and

(x) undeﬁned means it has not yet been determined whether x ∈ B.The

approximations B

become more deﬁned at later stages of the construction;

that is, B

 B

k+1

, which means that B

k+1

is deﬁned wherever B

is, and

where both are deﬁned, they take equal values.

In this construction, we maintain the invariant that, just before

commencing stage k, we have successfully diagonalized away from

,... ,M

k−1

; that is, we have built B

such that for any total exten-

sion C of B

and for any i<k,thereexistsanx such that

accepts x ⇔ x ∈ E

⇔ C contains no elements of length |x|. (28.1)

We start at stage 0 with B

completely undeﬁned. Now say at stage

k we have constructed B

satisfying (28.1). We now look at M

.Saythe

time bound of M

is n

.Pickn greater than the length of all elements in

the domain of B

—this is possible because the domain of B

is ﬁnite—and

large enough that 2

. Initially set B

k+1

:= B

Now simulate M

on some input of length n,saya

. Whenever M

attempts to query its oracle on some string y,ifB

k+1

is already deﬁned

on y, we supply the value of B

k+1

(y). If B

k+1

is undeﬁned on y,weset

k+1

(y) := 0 and supply the value 0. The machine runs to completion and

either accepts or rejects.

Now we adjust the oracle so that M

is guaranteed to have been wrong

in its attempt to accept E

. Note that because M

runs in time n

< 2

there must be at least one string of length n that was never the subject

of an oracle query by M

during the computation, therefore B

k+1

is still

undeﬁned on those strings. If M

accepted, we set B

k+1

(y):=0forall

remaining strings y of length n on which B

k+1

is still undeﬁned. In this

case B

k+1

(y) = 0 for all strings y of length n.IfM

rejected, we set

k+1

(y) := 1 for all remaining strings y of length n on which B

k+1

is still

undeﬁned, and there is at least one such string. These adjustments do not

174 Lecture 28

aﬀect the computation of M

on input a

, because they were never the

subject of an oracle query.

Then for any total extension C of B

k+1

, (28.1) holds, therefore

L(M

) = E

.IfwetakeB to be any total extension of all the B

for

k ≥ 0, then we are guaranteed that L(M

) = E

for any M

.Thus

∈ NP

− P

. 2

Supplementary Lecture F

Unique Satisﬁability

In this lecture and the next, we study some interesting reducibility rela-

tions involving randomness and counting and prove two notable results in

structural complexity theory. The ﬁrst is a result of Valiant and Vazirani

[125] that Boolean satisﬁability is no easier for formulas that are guaranteed

to have at most one solution than for arbitrary formulas. The second is a

result of Toda [120] that the ability to count solutions to instances of NP-

complete problems allows one to compute any set in the polynomial-time

hierarchy. In this lecture we prove the Valiant–Vazirani result, on which

Toda’s theorem is partly based.

As shown in Theorem 10.2, problems in NP can be deﬁned in terms

of the existence of polynomial-size witnesses that can be recognized easily.

For instance, Boolean satisﬁability (SAT) is characterized by the existence

of satisfying truth assignments. The number of witnesses for diﬀerent in-

stances of the problem can vary over an exponential range, and one might

ask whether this variation is at least partly responsible for the diﬃculty of

NP-complete problems.

Valiant and Vazirani [125] answered this question in the negative. They

showed that the general satisﬁability problem SAT reduces by an eﬃcient

randomized reduction to USAT, the satisﬁability problem for Boolean for-

mulas that are promised to have at most one satisfying assignment.

The proof is based on the following idea. Consider the vector space F

of dimension n over a ﬁnite ﬁeld F. One can construct a random tower of

Unique Satisﬁability 181

linear subspaces

{0} = E

⊂ E

⊂ ··· ⊂ E

= F

(F.1)

such that E

has dimension i, all such towers equally likely. This can be

done by choosing a random basis x

,... ,x

of F

and deﬁning E

,... ,x

n−i

}

⊥

,where

⊥

def

= {y |∀x ∈ Ax

•

y =0},

the orthogonal complement of A, and where

•

denotes inner product. A

random basis x

,... ,x

can be obtained eﬃciently (Miscellaneous Exercise

60(b)).

For F = GF

, the ﬁeld on two elements, Valiant and Vazirani [125,

Theorem 4(ii)] show that for any nonempty set S ⊆ GF

, for a randomly

chosen tower (F.1), some S ∩ E

contains exactly one vector with proba-

bility at least 1/2. This leads to a randomized reduction from the general

satisﬁability problem to the unique satisﬁability problem.

The proof of this result as given in [125] is inductive on dimension. We

give an alternative proof here that achieves a slightly better lower bound

of 3/4.

Lemma F.1 Let S be a nonempty subset of GF

.LetE

,... ,E

be a random tower of

linear subspaces of GF

with dim E

= i.Then

Pr(∃i |S ∩ E

| =1) ≥

. (F.2)

Proof. If 0 ∈ S, then the probability is 1, because S ∩ E

= {0}. Simi-

larly, if |S | = 1, then the probability is 1, because |S | = |S ∩ E

| =1.Rul-

ing out these two cases, we can assume that |S ∩ E

|≥2and|S ∩ E

| =0.

Because S ∩ E

⊆ S ∩ E

i+1

for 0 ≤ i ≤ n −1, we have that |S ∩ E

|≤

|S ∩ E

i+1

| for 0 ≤ i ≤ n − 1. Thus there exists a least k ≥ 1 such that

|S ∩ E

|≥2. Here k is a random variable whose value depends on the

choice of the random tower E

as well as S.

If A is a set of vectors, let <A> denote the linear span of A in GF

.Over

, any pair of distinct nonzero vectors x, y are linearly independent,

because there are only three nonzero linear combinations, namely x, y,and

x + y,andthelastis0iﬀx = y.Thusdim<S ∩ E

> is at least 2.

Now (F.2) is equivalent to the statement

Pr(S ∩ E

k−1

= ∅) ≤

, (F.3)

and this is what we would like to show. Let H = {x

n−k+1

}

⊥

, the hyperplane

consisting of all vectors orthogonal to x

n−k+1

,andletT be a maximal

linearly independent subset of S ∩ E

.ThenE

k−1

= E

∩ H and

T ∩ H ⊆ S ∩ E

∩ H = S ∩ E

k−1