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

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

168 12 The PCP Theorem and the Complexity of Approximation Problems

the same input a. For consistent linear functions L

,andL

the test

makes no errors. Inconsistent triples of linear or almost linear functions will

be detected with constant error-probability β<1. Once again, only constantly

many bits will be read.

Finally, the proof veriﬁer reads constantly many bits and tests as described

above whether p

(a) = 0 for random bit vectors r. If the proof contains L

and L

, then the value of p

(a) is correctly computed. Otherwise the error-

probability can be bounded by a constant γ<1.

All together the proof (L

) for a satisfying assignment a is always

accepted. For unsatisﬁable clause sets, a proof can be accepted if at least one

of the following occurs:

• One of the three linearity tests fails to detect that one of the functions is

not even almost linear.

• The consistency test fails to detect a triple of functions that are inconsis-

tent. For this almost linear functions are corrected to linear functions.

• All the computed p

(a) have the value 0. Once again, almost linear func-

tions are corrected to linear functions.

• One of the many function evaluations produces an incorrect value.

It is important to note that the function evaluator is used in the other

modules. We will allow each linearity test an error-probability of 1/18, i.e., a

combined error-probability of 1/6. The consistency test – under the assump-

tion that the linearity tests make no errors – is allowed an error-probability

of 1/6. That leaves an error-probability of 1/6 for the proof veriﬁer – under

the assumption that the other tests are all error-free. The proof veriﬁer reads

three bits. If we permit the function evaluator an error-probability of 1/10,

then for unsatisﬁable clause sets a value of 0 is computed for p

(a)onlyif

(a) = 0 (probability 1/2) or a function evaluation produces an incorrect

value. So the overall error-probability of the proof veriﬁer is bounded by 4/5.

Nine independent repetitions reduce this error-probability to less than 1/6.

Similar arguments allow us to compute the corresponding parameters for the

other modules. So it suﬃces to show that every test has an error-probability

bounded by some constant less than 1 and can be computed with the help of

constantly many proof bits and O(n

) random bits in polynomial time. Then

the PCP veriﬁer can be made by assembling these modules.

We begin with the linearity test. Since we are working in the ﬁeld Z

f : Z

→ Z

is linear if and only if f(x + y)=f (x)+f(y) for all x, y ∈ Z

We will say that a function f is δ-close to a function g if under the uniform

distribution on Z

,Prob

(f(x) = g(x)) ≤ δ. We will use the subscript on

Prob to denote which element was chosen at random, always assuming a

uniform distribution. The linearity test works as follows:

• Choose independent and random x, y ∈ Z

and only consider f to be

non-linear if f(x + y) = f(x)+f(y).

This test has the following properties:

12.2 The PCP Theorem 169

• If f is linear, it will pass the linearity test.

• If δ<1/3andf is not δ-close to any linear function, then f passes the

test with probability less than 1 − δ/2.

The ﬁrst property is clear. The second property can be equivalently for-

mulated as

• From Prob

x,y

(f(x + y) = f(x)+f(y)) ≤ δ/2 it follows that f is δ-close to

some linear function g.

We will prove this claim by deﬁning a linear function g and showing that f is

δ-close to g. To deﬁne g(a) we consider f(a + b) − f (b) for all b ∈ Z

. For a

linear function f this will always yield the value f(a). So we let g(a)bethe

value from {0, 1} that occurs most frequently in the list of all f(a + b) − f (b).

In case of an equal number of 0’s and 1’s, we let g(a) = 0. It remains to show

that

• g is δ-close to f,and

• g is linear.

The ﬁrst property is proved by contradiction. Suppose that f and g are

not δ-close. Then

Prob

(f(x) = g(x)) >δ.

By the construction of g, for every a ∈ Z

Prob

(g(a)=f(a + y) − f(y)) ≥ 1/2 .

So it follows that

Prob

x,y

(f(x + y) − f(y) = f(x))

≥ Prob

x,y

(f(x + y) − f(y)=g(x) ∧ g(x) = f(x))



a∈Z

−m

· Prob

(f(a + y) − f(y)=g(a) ∧ g(a) = f(a)) .

For every a,eitherg(a)=f (a)org(a) = f(a). In the ﬁrst case the probability

we are considering is 0, and in the second case the condition g(a) = f(a)can

be left out. So

Prob

x,y

(f(x + y) − f(y) = f(x))

≥ 2

−m



a∈Z

g(a)=f (a)

Prob

(f(a + y) − f(y)=g(a))

≥ 2

−m



a∈Z

g(a)=f (a)

>δ/2 ,

170 12 The PCP Theorem and the Complexity of Approximation Problems

contradicting the assumption that Prob

x,y

(f(x + y) = f(x)+f(y)) ≤ δ/2.

The last inequality follows since from Prob

(f(x) = g(x)) >δit follows that

more than δ · 2

of all a ∈ Z

have the property that g(a) = f(a).

For the proof of the linearity of g we investigate

p(a):=Prob

(g(a)=f(a + x) − f(x)) .

By the construction of g, p(a) ≥ 1/2. We will show that, in fact, p(a) ≥ 1 − δ.

Applying the assumption that

Prob

x,y

(f(x + y) = f(x)+f(y)) ≤ δ/2

to x + a and y and also to x and y + a, and noting that for a random choice

of x ∈ Z

, x + a is also a random bit vector from Z

yields

Prob

x,y

(f(x + a)+f(y) = f (x + a + y)) ≤ δ/2

and

Prob

x,y

(f(x)+f(y + a) = f (x + a + y)) ≤ δ/2 .

The probability of the union of these events is bounded above by δ,andthe

probability of the complement is bounded below by 1 − δ. By DeMorgan’s

laws, this is the intersection of the events f(x + a)+f(y)=f(x + a + y)

and f(x)+f (y + a)=f(x + a + y), in particular a subset of the event

f(x + a)+f(y)=f(x)+f(y + a). Thus

Prob

x,y

(f(x + a)+f(y)=f(x)+f(y + a)) ≥ 1 − δ.

In order to take advantage of the independence of the selection of x and y,we

write this equation as f(x + a) − f(x)=f (y + a) − f(y). Then

1 − δ ≤ Prob

x,y

(f(x + a) − f(x)=f(y + a) − f(y))



z∈{0,1}

Prob

x,y

(f(x + a) − f(x)=z ∧ f(y + a) − f (y)=z)



z∈{0,1}

Prob

(f(x + a) − f(x)=z) · Prob

(f(y + a) − f(y)=z)



z∈{0,1}

(Prob

(f(x + a) − f(x)=z))

If z = g(a), then Prob

(f(x + a) − f(x)=z)=p(a). Thus



z=g(a)

Prob

(f(x + a) − f(x)=z)=1− p(a) ,



z=g(a)

(Prob

(f(x + a) − f(x)=z))

=(1− p(a))

12.2 The PCP Theorem 171

and

1 − δ ≤ p(a)

+(1− p(a))

Since, as we noted above, p(a) ≥ 1/2, it follows that 1 − p(a) ≤ p(a)and

p(a)

+(1− p(a))

≤ p(a)

+ p(a)(1 − p(a)) = p(a) ,

and thus p(a) ≥ 1 − δ, as was claimed.

We apply this result three times, using again the fact that not only x but

also x + a is a random bit vector from Z

.Thisgives

Prob

(g(a)=f(a + x) − f(x)) = p(a) ≥ 1 − δ,

Prob

(g(b)=f(b + a + x) − f(a + x)) = p(b) ≥ 1 − δ,

Prob

(g(a + b)=f(a + b + x) − f(x)) = p(a + b) ≥ 1 − δ.

Thus the intersection of the three events has probability at least 1 − 3δ.This

also holds for any event implied by this intersection. In particular, adding the

ﬁrst two equations and subtracting the third, we get

Prob

(g(a)+g(b)=g(a + b)) ≥ 1 − 3δ.

Since by assumption δ<1/3,

Prob

(g(a)+g(b)=g(a + b)) > 0 .

But the equation g(a)+g(b)=g(a + b) is true or false independent of the

choice of x. A positive probability that can only take on a value of 0 or 1 must

have the value 1. So g(a)+g(b)=g(a + b) for all a and b and thus g is linear.

Now we turn to the function evaluator. The function evaluator receives

as input the function table of a function f : Z

→ Z

and an a ∈ Z

.For

δ<1/3 it must have following properties:

• If f is linear, then the result is f(a).

• If f is not linear, but δ-close to a linear function g, then the randomized

function evaluator should output g(a) with an error-probability bounded

by 2δ.

The function evaluator works as follows:

• Chose an x ∈ Z

at random and compute f(x + a) − f(x).

The ﬁrst property is clearly satisﬁed. The second property can be shown

as follows. Since f and g are δ-close,

Prob

(f(x)=g(x)) ≥ 1 − δ

and

Prob

(f(x + a)=g(x + a)) ≥ 1 − δ.

172 12 The PCP Theorem and the Complexity of Approximation Problems

Thus the probability that both events occur is at least 1 − 2δ.Bothevents

together, however, imply that f (x + a) − f(x)=g(x + a) − g(x), and by

the linearity of g, this implies that f(x + a) − f(x)=g(a). So the function

evaluator has the desired properties.

For the consistency test, the function tables for f

, f

,andf

are available.

The represented functions are either linear or δ-close to a linear function. For

δ<1/24 the consistency test should have the following properties:

• If the function tables represent linear functions of the type L

,andL

for some a ∈{0, 1}

, then the function tables pass the consistency test.

• If there is no a ∈{0, 1}

such that the functions f

,andf

represented

in the tables are δ-close to L

,andL

, then the consistency test detects

this with an error-probability bounded by some constant less than 1.

The consistency test works as follows:

• Choose x, x





∈ Z

and y ∈ Z

independently at random.

• Deﬁne x ◦ x



by (x ◦ x



)

i,j

= x



and x



◦ y by (x



◦ y)

i,j,k

= x



j,k

• Use the function evaluator to compute estimates b for f

(x), b



for f





for f



), c for f

(x ◦ x



),c



for f

(y), and d for f



◦ y).

• The function tables pass the consistency test if bb



= c and b





= d.

Linear functions L

,andL

always pass the consistency test. For them

the function evaluator is error-free and

(x) · L







1≤i≤n





1≤j≤n







1≤i,j≤n



= L

(x ◦ x



) .

Analogously it follows that L



) · L

(y)=L



◦ y). For the second prop-

erty we use the fact that for δ<1/24 the error-probability of the function

evaluator is bounded by 2δ<1/12. This means that the error-probability of

all six function evaluations together is bounded by 1/2. Now assume that the

function evaluations are without error. Let the linear function that is δ-close

to f

have coeﬃcients a

and the linear function that is δ-close to f

have

the coeﬃcients b

i,j

.Leta

i,j

:= a

. Now consider the matrices A =(a

i,j

)

and B =(b

i,j

), and assume that the function evaluations are correct but the

function tables are inconsistent. Then A = B. We represent the corresponding

inputs x and x



as column vectors. The consistency test compares x





and





and is based on the fact that for A = B and random x and x



with

probability at least 1/4 the two values are diﬀerent, and so the inconsistency

is detected. If A and B diﬀer in the jth column, then the probability that



A and x



B diﬀer in the jth position is 1/2. This follows by the already

frequently used argument regarding the value of the scalar products x



y and



z for y = z and random x.Ifx



A and x



B diﬀer, then with probability

1/2, (x



A)x



and (x



B)x



are also diﬀerent.

If all the modules use the correct parameters, it follows that

3-Sat ∈

PCP(n

, 1) and thus that NP ⊆ PCP(n

, 1). 

12.3 The PCP Theorem and Inapproximability Results 173

In order to drastically reduce the number of random bits, we need to get

by with much shorter proofs. One idea used is to replace the linear functions

in our approach with polynomials of low degree. Then a so-called composition

lemma is proved that produces from two veriﬁers with diﬀerent properties an

improved veriﬁer. As we have already indicated, we won’t go any deeper into

the proof of the PCP Theorem. Our discussion should at least have made

clear, however, that reading only constantly many bits of a proof can provide

an amazing amount of information. But this only holds for proof attempts

where false proofs are not always detected. The diﬃculty of reporting this

result is shown in the following quotation from The New York Times on April

7, 1992:

“ In a discovery that overturns centuries of mathematical tradition,

a group of graduate students and young researchers has discovered a

way to check even the longest and most complicated proof by scruti-

nizing it in just a few spots ...”

12.3 The PCP Theorem and Inapproximability Results

The article just cited continues

“...Using this new result, the researchers have already made a land-

mark discovery in computer science. They showed that it is impossible

to compute even approximate solutions for a large group of practical

problems that have long foiled researchers ....”

As examples, we want to show that this claim holds for

Max-3-Sat and

Max-Clique.

The PCP Theorem makes it possible to make better use of the gap tech-

nique discussed in Section 8.3. Using the fact that

3-Sat ∈ PCP(log n, 1), we

will polynomially reduce

3-Sat to Max -3- Sat in such a way the following

properties are satisﬁed for a constant δ>0:

• If the given clause set is satisﬁable, then the clause set produced by the

reduction is also satisﬁable.

• If the given clause set is not satisﬁable, then at most a proportion of 1 − δ

of the clauses produced by the reduction are satisﬁable.

We now choose an ε>0sothat1+ε =1/(1 − δ). If

Max-3-Sat has a

polynomial-time approximation algorithm with approximation ratio less than

1+ε, then it follows that

NP = P. For in that case we can solve 3-Sat in

the following way. First we use a reduction with the properties listed above,

and then we apply the approximation algorithm

Max-3-Sat to the result and

compute the proportion α of satisﬁed clauses. If α>1 − δ, then the given

clause set is satisﬁable by the second property of the polynomial reduction. If

α ≤ 1 − δ, then by the ﬁrst property of the reduction and the approximation

174 12 The PCP Theorem and the Complexity of Approximation Problems

ratio of the approximation algorithm, the clause set cannot be satisﬁable. We

will formalize this proof strategy in the theorem below.

Theorem 12.3.1. There is a constant ε>0 such that polynomial approxi-

mation algorithms for

Max-3-Sat with an approximation ratio less than 1+ε

only exist if

NP = P.

Proof. We will complete the application of the gap technique described above.

By the PCP Theorem there are integer constants c and k such that there

is a probabilistically checkable proof for

3-Sat that uses at most c · log n

random bits and reads at most k bits of the proof for instances of

3-Sat

with n variables. We can assume that exactly c · log n random bits are

available and that always exactly k bits of the proof are read. There are

then N := 2

c·log n

≤ n

assignments for the random bit vector. For each

assignment of the random bits and each

3-Sat input there are exactly k bits

of the proof that are read. So for each

3-Sat instance there can only be kN

diﬀerent bit positions that have a non-zero probability of being read. All

other positions in the proof are irrelevant. So we can assume that the proof

has length exactly kN. The set of possible proofs is then the set {0, 1}

Let C be a set of clauses of length 3 on n variables. For this set C we

consider N Boolean functions f

: {0, 1}

→{0, 1} for 0 ≤ r ≤ N − 1. The

index r refers to the random bit vector, which will be interpreted as a binary

number. For a ﬁxed r and C,thek proof positions j

(1) < ··· <j

(k)that

are read are also ﬁxed. The value of f

(y) should take the value 1 if and only

if the probabilistic proof checker accepts the proof y for clause set C with

random bits r. Syntactically we describe all functions in dependence on all

the bits y =(y

,...,y

) of the proof. But it is important that each function

essentially only depends on k of the y-variables. Now we can express the

properties of the probabilistic proof checker as properties of the functions f

• If the clause set is satisﬁable, then there is a y ∈{0, 1}

such that all

(y) = 1 for all 0 ≤ r ≤ N − 1.

• If the clause set is not satisﬁable, then for every y ∈{0, 1}

, f

(y)=1

foratmosthalfofther with 0 ≤ r ≤ N − 1.

The polynomially many functions f

only essentially depend on a constant

number of variables. This makes it possible to compute the conjunctive normal

forms for all of the functions f

in polynomial time. For each function the

conjunctive normal form has at most 2

clauses of length k. Now we apply

the polynomial reduction

Sat ≤

3-Sat (Theorem 4.3.2) to replace the clauses

of each function with clauses of length 3. This replaces each of the given clauses

with k

∗

=max{1,k − 2} clauses. To see that the properties of the functions

described above carry over to the new clause sets we note that f

has the

value 0 if any one of its at most 2

clauses has the value 0. After the described

transformation we obtain for f

at most k

∗

· 2

clauses, and the value of f

0 if any one of these clauses is unsatisﬁed. Thus

12.3 The PCP Theorem and Inapproximability Results 175

• If the original set of clauses is satisﬁable, then the at most k

∗

·2

·N newly

formed clauses are simultaneously satisﬁable.

• If the original set of clauses is not satisﬁable, then for any assignment of

the variables of the newly formed clauses, there are at least N/2 clauses

(oneeachforhalfoftheNf

-functions) that are not satisﬁed.

For δ := (N/2)/(k

∗

·2

·N)=1/(k

∗

·2

k+1

) at most a proportion of 1− δ of

the clauses in the newly formed clause set are simultaneously satisﬁable unless

all the clauses are simultaneously satisﬁable. By our preceding discussion we

have proven the theorem for ε := 1/(1 − δ) − 1 > 0. 

The proof of Theorem 12.3.1 shows that we get better results if we can

decrease the size of k but that the constant c only eﬀects the degree of the

polynomial that bounds the runtime. If k = 2, then we get a set of clauses

each of length 2. For such a set of clauses we can determine in polynomial

time if all the clauses are simultaneously satisﬁable (see Section 7.1). Such

a probabilistic proof checker for

3-Sat or some other NP-complete problem

would imply that

NP = P. Theorem 12.3.1 and the existence of a polynomial

approximation algorithm with ﬁnite approximation ratio for

Max-3-Sat imply

the following corollary.

Corollary 12.3.2. If

NP = P, then Max -3- Sat ∈ APX − PTAS. 

Now we turn our attention to

Max-Clique. This problem stood at the cen-

ter of the attempts to ﬁnd “better PCP Theorems” (Arora and Safra (1998),

H˚astad (1999)). Here we are unable to prove the best known result but will

be satisﬁed with the following theorem.

Theorem 12.3.3. If

NP = P, then Max-Clique /∈ APX.

Proof. Once again we use the gap technique. As in the proof of Theo-

rem 12.3.1, we use a probabilistic proof checker for

3-Sat that uses c · log n

random bits and reads exactly k bits of the proof for a clause set on n vari-

ables. Once again let N := 2

c·log n

≤ n

. For this probabilistic proof checker

we construct the following graph in polynomial time. For each assignment of

the random vector r we consider all 2

assignments of the k bits of the proof

that are read. Each assignment for which the proof is accepted is represented

by a vertex in the graph, so the number of vertices is bounded above by 2

·N.

The vertices that belong to the same r form a group. Vertices from the same

group are never connected by edges. Vertices from diﬀerent groups are con-

nected by an edge if and only if there are no contradictions in the assignment

for the proof bits that both read.

If the given set of clauses is satisﬁable, then there is a proof that is accepted

for all assignments r. From each group we consider the vertices that represent

this proof. By deﬁnition these vertices form a clique of size N.

If the given set of clauses is not satisﬁable, then every proof is only ac-

cepted for half of the assignments r. If there is a clique of size N



>N/2,

176 12 The PCP Theorem and the Complexity of Approximation Problems

then by construction, the N



vertices must come from N



diﬀerent groups.

Furthermore, pairwise their read bits do not contradict each other. So there is

a proof that is compatible with all of these partial assignments of proof bits.

This proof will be accepted by N



(more than half) of the N assignments

of r, in contradiction to the assumption that the given set of clauses is not

satisﬁable.

So if

NP = P, then there is no polynomial approximation algorithm for

Max-Clique that achieves an approximation ratio of 2.

In contrast to the proof of Theorem 12.3.1, the constant k does not show

up in the size of the resulting gap. The gap is 2 because the probabilistic proof

checker has an error-probability bounded by 1/2. But for each constant d>1,

thereisa

PCP(log n, 1)-veriﬁer for 3-Sat with an error-probability bounded

by 1/d. If we carry out the same proof but use this probabilistic proof checker

instead, we obtain a gap of size d. This proves the theorem. 

Our proof of Theorem 12.3.3 applied the PCP Theorem directly. In The-

orem 8.4.4 we described a

PTAS-reduction from Max -3- Sat to Max-Clique

with α(ε)=ε. Using this we obtain for Max-Clique the same inapproxima-

bility result that we showed for

Max-3-Sat in Theorem 12.3.1. In contrast to

Max-3-Sat, Max-Clique has the property of self-improvability, which means

that from a polynomial approximation algorithm with approximation ratio c

we can construct an approximation algorithm with approximation ratio c

1/2

Since this increases the degree of the polynomial bounding the runtime, we

can only repeat this constantly many times. The approximation ratio can then

be reduced from c to c

1/2

for any constant k, and thus under 1 + ε for any

ε>0. This gives us a proof of Theorem 12.3.3 from Theorem 12.3.1 without

applying the PCP Theorem directly.

For the proof of the property of self-improvability we consider for undi-

rected graphs G =(V,E)theproduct graph G

on V × V . The product graph

contains the edge {(v

), (v

)},if

• (i, j) =(k, l), and

•{v

}∈E or i = k,and

•{v

}∈E or j = l.

From a clique with vertices {v

,...,v

} in G we obtain a clique with vertices

{(v

) | 1 ≤ i, j ≤ r} in G

.Thusifcl(G) denotes the maximal clique size in

G,thencl(G

) ≥ cl(G)

. On the other hand, suppose there is a clique of size

m in G

. Consider the vertex pairs (v

) that form this clique. In the ﬁrst

or second component of these pairs there must be at least  m

1/2

 vertices.

To show that cl(G

) ≤ cl(G)

we will show that these m

1/2

 vertices form a

clique in G.Ifv

and v

both occur as ﬁrst components in the vertex pairs of

the clique in G

, then there are v

and v

such that (v

)and(v

)also

belong to the clique in G

, and so are connected by an edge. But this implies

by the deﬁnition of G

that {v

}∈E. The arguments proceed analogously

if v

and v

are second components of such vertex pairs. Thus cl(G

)=cl(G)

12.4 The PCP Theorem and APX-Completeness 177

To improve a polynomial c-approximation algorithm A for Max-Clique

we compute for G the graph G

and apply A to G

to get a clique of size m,

from which we compute a clique of size m

1/2

 in G which we output. Then

cl(G

)/m ≤ c and

cl(G)/m

1/2

≤(cl(G)

/m)

1/2

=(cl(G

)/m)

1/2

≤ c

1/2

This gives us a c

1/2

approximation algorithm with polynomially bounded

runtime.

We won’t derive any more inapproximability results. Kann and Crescenzi

(2000) survey the best currently known results. For the optimization problems

that we have dealt with most intensively we list the best known bounds in

Table 12.3.1.

12.4 The PCP Theorem and APX-Completeness

In Section 8.5 we already showed that Max-W-Sat and Min-W-Sat are NPO-

complete. Here we want to use the PCP Theorem to show that

Max-3-Sat

is APX-complete. This result is the starting point for many further APX-

completeness results, but we will not discuss these here. We have already

seen that

NP = P follows from Max -3- Sat ∈ PTAS. In the ﬁrst and decid-

ing step of the proof, we show that

Max-3-Sat is Max-APX-complete, where

Max-APX contains the maximization problems from APX. After that we show

that every problem in

Min-APX can be reduced to a maximization variant of

itself with a ≤

PTAS

-reduction. Combining these gives the announced result.

We ﬁrst want to discuss the idea of the proof of

Max-APX-completeness.

Consider a problem A ∈

Max-APX that can be approximated in polynomial

time with an approximation ratio of r

∗

≥ 1. The constant r

∗

could be very

large. On the other hand, for small approximation ratios,

Max-3-Sat is a dif-

ﬁcult problem. The approximate solution for A provides us with an interval

[a, r

∗

· a] for the value of an optimal solution. We divide this interval into

subintervals I

:= [˜r

i−1

· a, ˜r

· a], i ≥ 1, for some ˜r>1. As long as ˜r is

also a constant, we obtain constantly many subintervals. For each subinterval

the quotient formed by the upper and lower ends is so small that the sub-

problem A

consisting of all instances that have an optimal solution value in

is ≤

PTAS

-reducible to Max-3-Sat. Of course, now we have the problem of

building from solutions for the constructed instances of

Max-3-Sat, solutions

of suﬃciently good approximation ratio for the entire instance of A. These

ideas will be carried out in the following Lemma.

Lemma 12.4.1.

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

Proof. At the end of Section 12.3 we said that

Max-3-Sat is 1.249-

approximable. But we can show that

Max -3- Sat ∈ APX directly by a simple

argument. Each clause is satisﬁed by one of the following assignments: the