Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms

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

178 12 The PCP Theorem and the Complexity of Approximation Problems

Max-Sat 1.2987-approximable and APX-complete

Max-k-Sat 1/(1 − 2

−k

)-approximable for k ≥ 3, if all

the clauses have k diﬀerent literals, but not

(1/(1 − 2

−k

) − ε)-approximable

Max-3-Sat 1.249-approximable, even if literals are allowed

to appear more than once in a clause

Max-2-Sat 1.0741-approximable, but not 1.0476-

approximable; literals may appear in a clause

more than once

Min-VertexCover 2-approximable, but not 1.3606-approximable

Min-GC O(n(log log n)

/log

n)-approximable, but

not n

1/7−ε

-approximable; not even n

1−ε

approximable, if NP = ZPP

Max-Clique O(n/ log

n)-approximable, but not n

1/2−ε

approximable; not even n

1−ε

-approximable, if

NP = ZPP

Min-TSP NPO-complete

Min-TSP

sym,∆

3/2-approximable and APX-complete

Max-3- DM (3/2+ε)-approximable and APX-complete

Min-BinPacking 3/2-approximable, but not even (3/2 − ε)-

approximable

(71/60 + 78/(71opt))-approximable and also

(1 + (log

opt)/opt)-approximable where opt de-

notes the value of an optimal solution

Min-SetCover (1 + ln n)-approximable, where n is the cardinal-

ity of the underlying set, but for some c>0

not (c ·ln n)-approximable, and not ((1 − ε)lnn)-

approximable, if polynomial-time nondeterminis-

tic algorithms can’t be replaced by deterministic

algorithms that run in time O(n

log log n

)

Table 12.3.1. Best known approximability and inapproximability results. The ap-

proximation ratios are with respect to polynomial-time algorithms, ε is always an

arbitrary positive constant, and the negative results assume that NP = P unless we

mention otherwise.

12.4 The PCP Theorem and APX-Completeness 179

assignment consisting entirely of 0’s and the assignment consisting entirely

of 1’s. Whichever of these two assignments satisﬁes the most clauses has an

approximation ratio bounded by 2.

Now let A ∈

Max-APX and let r

∗

be a constant approximation ratio achiev-

able by an algorithm G. We want to show that A ≤

PTAS

B = Max -3- Sat.

In the deﬁnition of ≤

PTAS

-reducibility (Deﬁnition 8.4.1), the demands on the

approximation ratio of the approximate solution for A that comes from the

approximate solution for B are given by

(f(x),y) ≤ 1+α(ε) ⇒ r

(x, g(x, y, ε)) ≤ 1+ε.

For α: Q

→ Q

we will use a linear function α(ε)=ε/β with β>0.

Then 1 + α(ε) can take on every rational value r>1, ε = α(ε) · β, and for

r =1+α(ε), 1 + ε =1+α(ε) · β =1+(r − 1) · β. The demand on the

approximation ratio of g(x, y, ε) given above is equivalent to

(f(x),y) ≤ r ⇒ r

(x, g(x, y, r)) ≤ 1+β · (r − 1) .

The following choice of the parameter β turns out to be suitable:

β := 2(r

∗

log r

∗

+ r

∗

− 1) · (1 + ε)/ε ,

where ε>0 is now a constant for which Theorem 12.3.1 is satisﬁed. Further-

more, ε is chosen so that β is rational. The smaller the “diﬃcult gap” for

Max-3-Sat, and the worse the given approximation ratio for A is, the larger

β will be and the weaker the demands will be for the approximate solution

for A that must be computed.

The case r

∗

≤ 1+β · (r − 1) can be handled easily. The approximation

algorithm G already provides a suﬃciently good approximate solution. For

all instances x of the problem A,letf(x) be the same arbitrary instance of

B. That is, we will deﬁne g(x, y, r) independently of y.Letg(x, y, r)bethe

solution s(x) that algorithm G computes for instance x. Its approximation

ratio is bounded by r

∗

≤ 1+β·(r−1) and so the demand on the approximation

ratio g(x, y, r)ismet.

We can now assume that b := 1 + β · (r − 1) <r

∗

. Unfortunately there

is no way to avoid a few arithmetic estimations in this proof. First, let k be

deﬁned by k := log

∗

.Fromb<r

∗

and the inequality log z ≥ 1 − z

−1

for

z ≥ 1 it follows that

k ≤

log r

∗

log b

+1≤

log r

∗

1 − 1/b

b · log r

∗

b − 1

∗

log r

∗

+ r

∗

− 1

b − 1

β · ε

2 · (1 + ε)

and

180 12 The PCP Theorem and the Complexity of Approximation Problems

b − 1

2k(1 + ε)

From b =1+β · (r − 1) it follows that

r =

b − 1

+1<

2k(1 + ε)

+1.

We again let s(x) denote the solution computed by algorithm G for in-

stance x,weletv

(x, s) denote the value of this solution, and we let v

opt

(x)

denote the value of an optimal solution for x.Then

(x, s) ≤ v

opt

(x) ≤ r

∗

· v

(x, s) ≤ b

· v

(x, s) ,

where the last inequality follows from the deﬁnition of k. Now we partition

the interval of solution values into k intervals of geometrically growing sizes,

that is, into the intervals I

=[b

· v

(x, s),b

i+1

· v

(x, s)] for 0 ≤ i ≤ k − 1.

First we deal with the intervals individually. For 0 ≤ i ≤ k − 1 we consider

the following nondeterministic polynomial-time algorithm G

for instances of

• Nondeterministically generate a solution s



∈ S(x) (the deﬁnitions in Sec-

tion 8.1 imply that this is possible in polynomial time).

• Accept the input if v

(x, s



) ≥ b

· v

(x, s). In this case, leave s



and

(x, s



)ontheworktape.

Now we can apply the methods of the proof of Cook’s Theorem to express

the language accepted by this algorithm as a 3-

Sat formula γ

. It is important

to note that we can compute s



and its value v

(x, s



) in polynomial time

from a satisfying assignment for γ

. This is because the satisfying assignment

also codes the accepting conﬁguration. We can design the algorithms A

that they all have the same runtime. This means that all of the formulas γ

(0 ≤ i ≤ k − 1) will have the same number of clauses. Finally we deﬁne ϕ

as the result of the transformation of γ

as described in Theorem 12.3.1 and

f(x) as the conjunction ϕ of all ϕ

for 0 ≤ i ≤ k − 1. Using the construction

from Theorem 12.3.1 we have also obtained that all the formulas ϕ

have the

same number m of clauses.

So we have a

Max-3-Sat instance with km clauses and therefore v

opt

(ϕ) ≤

km.Nowleta be an assignment of the variables in this formula. We assume

that the approximation ratio of a is bounded by r.Thenv

opt

(ϕ) ≤ r · v

(ϕ, a)

and

opt

(ϕ) − v

(ϕ, a) ≤ (1 − 1/r) · v

opt

(ϕ) ≤ (1 − 1/r) · km .

Now let r

be the approximation ratio for the assignment a if we use a as a

solution for the

Max-3-Sat instance ϕ

. Since the formulas ϕ

for 0 ≤ j ≤ k−1

come from diﬀerent algorithms, they are deﬁned on disjoint sets of variables.

Optimal assignments for the subproblems can be selected independently and

12.4 The PCP Theorem and APX-Completeness 181

form an optimal solution to the combined problem. So for all i ∈{0,...,k−1},

opt

(ϕ) − v

(ϕ, a)=



0≤j≤k−1

opt

(ϕ

) − v

(ϕ

,a))

≥ v

opt

(ϕ

) − v

(ϕ

,a)

= v

opt

(ϕ

) · (1 − 1/r

) ,

where the last equality follows from the deﬁnition of r

. In the proof that

Max -3- Sat ∈ APX we saw that it is always possible to satisfy half of the

clauses, so v

opt

(ϕ

) ≥ m/2and

opt

(ϕ) − v

(ϕ, a) ≥ m · (1 − 1/r

)/2 .

We combine the two bounds for v

opt

(ϕ) − v

(ϕ, a)andobtain

m · (1 − 1/r

)/2 ≤ (1 − 1/r) · km .

With a simple transformation we get

1 − 2k(1 − 1/r) ≤ 1/r

Now we go back and use our previously proven inequality

2k(1 + ε)

+1=

ε +2k(1 + ε)

2k(1 + ε)

and obtain

1 − 2k(1 − 1/r) > 1 − 2k ·

ε +2k(1 + ε)

=1−

1+ε + ε/(2k)

1+ε/(2k)

1+ε + ε/(2k)

Together it follows that

1+ε + ε/(2k)

1+ε/(2k)

=1+

1+ε/(2k)

< 1+ε.

This approximation ratio even guarantees that we get a satisfying assign-

ment for ϕ

when one exists. In our consideration of NP ⊆ PCP(n

, 1), we saw

that from the always accepted proof that a

3-Sat formula is satisﬁable we can

compute in polynomial time (with respect to the length of the proof) a satis-

fying assignment. This is also true for the proofs of the actual PCP Theorem,

which only have polynomial length.

182 12 The PCP Theorem and the Complexity of Approximation Problems

By construction there is a j such that ϕ

,...,ϕ

are satisﬁable but

j+1

,..., ϕ

k−1

are not satisﬁable. Then v

opt

(x) ∈ I

,so

· v

(x, s) ≤ v

opt

(x) ≤ b

j+1

· v

(x, s) .

From the satisfying assignment of ϕ

we can compute in polynomial time a

solution s

∗

for the instance x of A that has a value that lies in the interval

. We deﬁne the result of this computation as g(x, a, r). Since v

opt

(x)and

(x, s

∗

) lie in I

opt

(x)/v

(x, s

∗

) ≤ b =1+β · (r − 1) ,

and so r

(x, g(x, a, r)) ≤ 1+β · (r − 1). This proves the lemma. 

Now we only have to derive the announced relationship between minimiza-

tion problems and maximization problems.

Lemma 12.4.2. For every minimization problem A ∈

APX there is a maxi-

mization problem B ∈

APX such that A ≤

PTAS

Proof. The basic idea is to set up a maximization problem based on the min-

imization problem by altering the evaluation function so that the direction

of the goal is reversed. The obvious idea of replacing v(x, s)with−v(x, s)is

not allowed because the values must be positive (see Section 8.1). The next

obvious idea is to replace v(x, s)withb − v(x, s) for a large enough b.This

is problematic since for instances x for which v

opt

(x) is much smaller than

b, solutions for the given problem A that have a poor approximation ratio

suddenly have a good approximation ratio after the transformation. Thus the

value of b would have to depend on x.

Since A ∈

APX, there is a polynomial-time approximation algorithm G for

A with a worst-case approximation ratio bounded above by a constant r

∗

≥ 1.

We can choose r

∗

to be an integer. Let s

∗

(x) denote the solution computed by

algorithm G for instance x. Our maximization problem B will have the same

set of instances as A, and for each instance the same allowable solutions. The

value of a solution for x is deﬁned by

(x, y) ≤ v

(x, s

∗

(x)) ⇒ v

(x, y):=(r

∗

+1)· v

(x, s

∗

(x)) − r

∗

· v

(x, y),

(x, y) >v

(x, s

∗

(x)) ⇒ v

(x, y):=v

(x, s

∗

(x)) .

This evaluation function v

can be computed in polynomial time. We can

use the approximation algorithm G as an approximation algorithm for the

maximization problem B. By the deﬁnition of v

, v

(x, s

∗

(x)) = v

(x, s

∗

(x))

and

(x, s

∗

(x)) ≤ v

opt,B

(x) ≤ (r

∗

+1)· v

(x, s

∗

(x)) .

From this it follows that v

opt,B

(x)/v

(x, s

∗

(x)) ≤ r

∗

+ 1 and for the maxi-

mization problem B, G yields an approximation ratio bounded by r

∗

+1, and

so B ∈ APX.

12.4 The PCP Theorem and APX-Completeness 183

Now we need to design a ≤

PTAS

-reduction from A to B. For this we de-

ﬁne f (x)=x, so we consider the same instance for A and for B. The back

transformation depends only on the instance x and the solution y but not on

the approximation ratio r. As in the proof of Lemma 12.4.1, we measure the

approximation ratio with r and not with ε. Then we deﬁne g by

(x, y) ≤ v

(x, s

∗

(x)) ⇒ g(x, y, r):=y,

(x, y) >v

(x, s

∗

(x)) ⇒ g(x, y, r):=s

∗

(x) .

So g is polynomial-time computable. Finally, we let β := r

∗

+1.

Now we need to check the following condition:

(f(x),y) ≤ r ⇒ r

(x, g(x, y, r)) ≤ 1+β · (r − 1) .

As in the deﬁnition of the evaluation function and the deﬁnition of g,we

distinguish between two cases. The simpler case is the case that v

(x, y) >

(x, s

∗

(x)). Then s

∗

(x) is chosen as the result and s

∗

(x)isbetterthany.

Thus

(x, g(x, y, r)) = r

(x, s

∗

(x)) ≤ r ≤ r +(β − 1)(r − 1) = 1 + β · (r − 1) ,

where the last inequality follows because β ≥ 1andr ≥ 1.

Now suppose v

(x, y) ≤ v

(x, s

∗

(x)) so that g(x, y, r)=y.Wehavede-

ﬁned v

just so that the condition we must show will be fulﬁlled. We have

(x, g(x, y, r)) = r

(x, y)=v

(x, y)/v

opt,A

(x)

and so it suﬃces to bound v

(x, y)fromaboveby(1+β · (r − 1)) · v

opt,A

(x).

By the deﬁnition of v

(x, y),

(x, y)=((r

∗

+1)· v

(x, s

∗

(x)) − v

(x, y))/r

∗

By our assumption r

(f(x),y)=r

(x, y)=v

opt,B

(x)/v

(x, y) ≤ r, and thus

(x, y) ≥ v

opt,B

(x)/r .

A simple computation shows that 1/r ≥ 2 − r if r ≥ 1. Together we get

(x, y) ≤ ((r

∗

+1)· v

(x, s

∗

(x)) − (2 − r)v

opt,B

(x))/r

∗

=((r

∗

+1)· v

(x, s

∗

(x)) − v

opt,B

(x))/r

∗

+(r − 1) · v

opt,B

(x)/r

∗

First we give an estimate for the second summand. By the deﬁnition of v

opt,B

(x) ≤ (r

∗

+1)· v

(x, s

∗

(x)) .

Since β = r

∗

+ 1 and s

∗

(x)isr

∗

-optimal for A, it follows that

(r − 1) · v

opt,B

(x)/r

∗

≤ (r − 1) · β · v

(x, s

∗

(x))/r

∗

≤ β · (r − 1) · v

opt,A

(x) .

184 12 The PCP Theorem and the Complexity of Approximation Problems

So the claim reduces to

((r

∗

+1)· v

(x, s

∗

(x)) − v

opt,B

(x))/r

∗

≤ v

opt,A

(x) .

This inequality is even correct as an equality. Here we make use of the special

choice of v

which for a given instance x causes the same solution y

∗

to be

optimal for both A and B.Sov

(x, y

∗

)=v

opt,A

(x), v

(x, y

∗

)=v

opt,B

(x),

and

(x, y

∗

)=(r

∗

+1)· v

(x, s

∗

(x)) − r

∗

· v

(x, y

∗

) .

From this it follows that

((r

∗

+1)· v

(x, s

∗

(x)) − v

opt,B

(x))/r

∗

= v

opt,A

(x) .

Together we have

(x, y) ≤ (1 + β · (r − 1)) · v

opt,A

(x)

and the lemma is proved. 

From Lemmas 12.4.1 and 12.4.2 we obtain our main result.

Theorem 12.4.3.

Max-3-Sat is APX-complete. 

This result is the starting point for using approximation-preserving reduc-

tions to obtain more

APX-completeness results.

The PCP Theorem contains a new characterization of the complexity

class

NP. The one-sided error and error-probability of 1/2 allowed in

this characterization give rise to a large “gap” between the instances

that are accepted and those that are rejected. This gap facilitates new

applications of the gap technique for proving inapproximability results

and completeness results for classes of approximation problems.

Further Topics From Classical Complexity

Theory

13.1 Overview

As was emphasized already in the introduction, the main focus of this text is

on particular complexity theoretical results for important problems. So newer

aspects like the complexity of approximation problems or interactive proofs

have been placed in the foreground while structural aspects have been reduced

to the bare essentials required for the desired results. But there are additional

classical topics of complexity theory with results of fundamental importance.

A few of these will be presented in this chapter.

The complexity classes we have investigated to this point have been based

on the resource of computation time. An obvious thing to try is to develop

an analogous theory for the resource of storage space. The resulting classes

are deﬁned in Section 13.2. It can be shown that all decision problems that

are contained in the polynomial hierarchy can be decided using only polyno-

mially bounded space and so are contained in the class

PSPACE. This means

that problems that are complete for

PSPACE with respect to polynomial re-

ductions do not belong to Σ

unless Σ

= PSPACE. So these problems are also

diﬃcult with respect to the resource of time.

PSPACE-complete problems will

be introduced in Section 13.3.

The next natural question is whether there is a hierarchy of classes analo-

gous to polynomial hierarchy – more precisely the time hierarchy – for space-

based complexity classes. But the analogous hierarchy of classes does not exist

because nondeterminism can be simulated deterministically in quadratic space

(Section 13.4) and nondeterminism can simulate “co-nondeterminism” with

the same space requirements (Section 13.5). Another place that one could

use space bounds in place of time bounds would be to replace polynomial re-

ductions – more precisely polynomial time reductions – with space-bounded

reductions. Reductions that only require logarithmic space are a restriction on

polynomial-time reductions and permit a view of the structure within

P.The

study of this structure leads to the discovery of problems in

P that presum-

ably cannot be solved by computers with many processors in polylogarithmic

186 13 Further Topics From Classical Complexity Theory

time. These issues will be discussed in Section 13.6. Finally, in Section 13.7 we

introduce another variant of many problems. In Section 2.1 we distinguished

between optimization problems, evaluation problems, and decision problems.

In decision problems we ask whether or not there exists a solution with a

certain property. A generalization of this is the counting problem, in which

the number of such solutions must be computed.

13.2 Space-Bounded Complexity Classes

As we did for time-based complexity classes, we will use the Turing machine

model to deﬁne space-bounded complexity classes. The space used by a nonde-

terministic computation on input x can be measured by counting the number

of diﬀerent tape cells that are visited during the computation. For nonde-

terministic computations we must consider all computation paths. Since for

most problems it is necessary to read the entire input, sublinear space would

not make much sense. But this is too coarse a measure of space. Instead, we

consider Turing machines with two tapes. The input is located on an input

tape on which the beginning and end are marked. The input tape is read-only,

that is its contents can be read, but no new symbols can be written on the

input tape. The second tape is the work tape and behaves like the tapes we are

accustomed to, except that we will require this tape to be one-way inﬁnite,

that is we only allow addresses i ≥ 1. The space used by a computation is

measured solely in terms of the work tape, and is equal to the largest j such

that work tape cell j is visited during the computation.

Deﬁnition 13.2.1. The complexity class

DTAPE(s(n)) contains all decision

problems that can be decided by a deterministic Turing machine using at most

s(|x|) space for each input x.

NTAPE (s(n)) is deﬁned analogously for non-

deterministic Turing machines.

PSPACE is the union of all DTAPE(n

) for

k ∈ N.

The notation is not entirely consistent since

TAPE and SPACE refer to

the same resource. But here as elsewhere we will go with the notation used

most often. It is notable that the space bound s(n) is taken very exactly.

DTAPE(n) only allows n tape cells to be used on the work tape, whereas linear

time allowed O(n) computation steps. This can be explained by the following

remark, in which we will show that for space bounds constant factors can be

saved without any diﬃculty.

Remark 13.2.2. For every natural number k,

DTAPE (s(n)) = DTAPE (s(n)/k)

and

NTAPE (s(n)) = NTAPE (s(n)/k).

Proof. If we replace the tape alphabet Γ with Γ



:= Γ

×{1,...,k},thenwe

can store k symbols from Γ on one tape cell and also mark which of them is

“really” being read. The simulation using this idea is now obvious. 

13.2 Space-Bounded Complexity Classes 187

At this point we want to make a few comments about the class CSL for

those who are familiar with the classes in the Chomsky hierarchy. Context

sensitive languages are deﬁned by context-sensitive grammars (for more infor-

mation see, for example, Hopcroft, Motwani, and Ullman (2001)). Except for

the generation of the empty string, context-sensitive languages are monotone,

that is, the right side of each rule is not shorter than the left side. This allows

the following nondeterministic algorithm that checks if x ∈ L for a context-

sensitive language L.Ontheworktapearegionoflength|x| is marked. This is

where a derivation starting with the start symbol will be nondeterministically

generated. Derivations that do not stay within the space bounds indicated by

the marked cells are terminated and x is rejected. Otherwise, the sequence

generated is compared with the input x after every step. If they are found to

be equal, x is accepted. This shows that

CSL ⊆ NTAPE(n). We will omit the

proof of the other direction but state the result in the following theorem.

Theorem 13.2.3.

CSL = NTAPE(n). 

This theorem shows that complexity classes based on space bounds can be

used to characterize important classes of problems.

Connections between time and space bounds are interesting. The basic

idea of the following consideration is simple. If a computation with restricted

space uses too much time, then it must repeat a conﬁguration (see Section 5.4).

A conﬁguration is an instantaneous snapshot of a Turing machine. The set

of all possible conﬁgurations for an input of length n can be described by

Q×{1,...,n}×{1,...,s(n)}×Γ

s(n)

, that is, by giving the current state q ∈ Q,

the position i ∈{1,...,n} on the input tape, the position j ∈{1,...,s(n)}

on the work tape, and the contents y ∈ Γ

s(n)

of the work tape. If there is

an accepting computation path, then there is an accepting computation path

that does not repeat any conﬁgurations and therefore has length at most

|Q|·n·s(n)·|Γ |

s(n)

O(log n+s(n))

. Since we can count computation steps, we

can terminate computation paths that have not halted after |Q|·n·s(n)·|Γ |

s(n)

steps and reject the input along these paths. The only requirement is that s(n)

can be computed from n in time 2

O(log n+s(n))

.Thisistrueofall“reasonable”

space bounds. So we make the following remark:

Remark 13.2.4. If s(n) can be computed in space s(n) and in time bounded by

O(log n+s(n))

, then deterministic Turing machines using at most s(n) space can

be simulated by Turing machines that use space s(n)andtime2

O(log n+s(n))

The same is true for nondeterministic Turing machines.

Between space and time there is at most an exponential blow-up if s(n) ≥

log n. Space bounds s(n)=o(log n) are a special case, since the position

on the input tape can serve as auxiliary storage. This explains why some of

the results that follow begin with the assumption that s(n) ≥ log n.From

Remark 13.2.4 it follows immediately that

DTAPE(log n) ⊆ P.