Mayr E.W., Pr?mel H.J., Steger A. (eds.) Lectures on Proof Verification and Approximation Algorithms

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

204 Chapter 7. Bounds for Approximating MAXLINEQ3-2 and MAXEkSAT

~ B~

= y~ B~ ~<

i=1

~:6s1/2<1~1<.C41.

~ : a~-l/Z<lBl~<$~-4/=

Overall the expected value of (7.27), being the probability of success for Verifier

Vsat[J], is shown to be less than (7 + 5J)/8 for any unsatisfiable formula qo. 9

As mentioned in the introduction of this chapter we get immediately

Corollary 7.16.

For any

e > O,

there exists some constant

b E N such

that

(1/8 - e)-RoBE3SAT-b

is A/P-complete.

It remains to give the generalization from E3SAT to EkSAT for k ~> 3.

Proof of Theorem 7.2.

We proceed by induction, starting from case k = 3.

In the induction step, we map a (1 -

1/2 k,

1)-gap of satisfiable clauses in case of

EkSAT to a (1 - 1/2 k+l, 1)-gap for E(k+I)SAT.

This is done by introducing for each EkSAw-instance qo a new variable x and

substituting each clause C by the two clauses C V x and C V ~. This produces

an E(k+l)SAw-instance q0'.

If we look at an arbitrary assignment to the variables of qd, half of the clauses are

satisfied just by the value of x, and in the rest x can be omitted, yielding a copy

of qo. Thus any assignment to the variables of qo satisfying a fraction of p clauses

yields for both possible assignments to x an assignment satisfying ~ clauses

of ~o ~ and vice versa. This gives immediately the desired mapping of gaps. 9

7.6.2 Estimating Expected Values of Success

It remains to give proof sketches of the two technical lemmas estimating the

important parts of the acceptance probability.

For that purpose we need another lemma stating roughly speaking that in the

choice of V there is only a small probability that large sets B of assignments for

W are projected onto small sets a of assignments for V.

Lemma 7.17.

I/V is chosen out o/W according to Test 7.13, there exists a

constant c, 0 < c < 1 such that/or

any

fixed/~ C_ 2 w

E 1 <~ 11~I c"

7.6. Optimal Lower Bounds for Approximating MAXEkSAT 205

The proof of this lemma is omitted here. It is based mainly on the following

observation. One can think of the choice of V as a sequential process of choosing

subsequently for the clauses of r one variable per clause. Assume that, before

choosing a variable from C -- x V y V z, two assignments in ;3 can differ on their

restriction to V only on x or y (depending on the choices made before). Then

the choice of z will force the two assignments to have identical restrictions to

V. Starting from a large set /~ of different assignments, one can estimate the

expectation on the number of different restrictions according to the part of V

chosen so far, changing during this process from [/~[ to [/~j'V[.

In the course of this calculation, one gets some inequalities c has to fulfill for

making the claim of the lemma true. As stated above, c = ~ turns out to be

one possible value. For the details see [Hks97b].

Proof o] Lemma 7.14.

We have to estimate the expected value of

B(gl)B(g2)

under the chosen distribution

D6,.

As stated in Lemma 7.3, the only non-zero contributions in the expected value

of the Fourier transform are those where/~1 --/~2, and here factors with different

projections onto V are independent of each other.

Consequently we have

E(B(gl)B(g2)) = E \(Z~ B~ ~E~H gl(Y)g2(Y))

= E B$ H

gl(Y)g2(Y)) ,

\ ~ zEfl'tV yE~:yTV:z

which under distribution

D6,

can be calculated to be

where s~ is the number of y G ~ with x =

y~fV.

To check this we consider the two

possible values for

f(x)

which occur each with probability 1/2. If f(x) = 1, we

have gl (y)g2 (Y) = -1 for each of the s~ many assignments y being restricted to x.

Otherwise we have for each y independently E (gl (Y)g2 (Y)) = 5' (- 1) + (1 - 5' ) 1 =

1 -

25 I.

Now we make a case distinction in accordance to the summation boundaries

stated in the claim of the lemma, i.e. we distinguish the cases

1. I, 1 5

2. ~,-,/2 < I/~I ~ ~,-41~

and

206 Chapter 7. Bounds for Approximating MAxLINEQ3-2 and MAXEkSAT

8 '-~/~ < 1131.

We want to estimate the corresponding three partial sums of (7.28) such that

they all together meet the right hand side of inequality (7.26). In the second case

there is nothing to do since the absolute value of the large product is obviously

at most one, and the term

occurs on the right hand side of (7.26).

In case 1, independently of V, we will show the corresponding sum to be at most

8 '1/2 in absolute size. By Lemma 7.6, for all t3 of even size, we have/3Z = 0 and

hence nothing to prove. For 13 of odd size, there must be some x E 131"V having

an odd sz. The corresponding factor in (7.28) evaluates to

1((-1) s: + (1 - 28') s=) = 1(-1 + (1 - 28')s'). (7.29)

By 8~ ~<

IZl

we have

sz <~ 1/8'

(we are considering case 1), and thus obtain as

an estimate for odd s~:

(1 - 28') ~:/> 1 - 28's=.

Consequently, the factor (7.29) can be bounded by

89 + + (1- 2r = -8'8=

where the last inequality comes again from s= ~<

I~I ~< 8 'I/~.

All other factors in (7.28) can be bounded by I in absolute value, which bounds

the absolute value of the large product by 8 '1/5. In total, we obtain the following

bound for the absolute value of the contribution of case 1 to the sum (7.28).

~< ~ D~8 '1/~ ~< 8 '1/~.

Lemma 7.5

,O:lJOl~6,-~/2

To finish the proof we have to bound the contribution of case 3 by 26 tl/2. Here,

we need to consider the distribution over the choices of V out of W = Var(r

using Lemma 7.17. We observe that 0 < (1 - 28') 8= ~< 1 - 26', bounding the

absolute value of each factor in (7.28) by 1 - 8'.

We now estimate

7.6. Optimal Lower Bounds for Approximating MAxEkSAT 207

fl: 6'-4/o<[fl]

zEBI"V

~ /}~ E ((1 - 5')["1"Vl) .

fl : 6,-4/~ <[fl I

By Lemma 7.17, case 1/31"V I <

Ifll c/2

occurs with probability at most

Ifll -c/2

512. Hence this case contributes in absolute value at most ~t2 to the expectation.

In case

[flTY[ >t [fl[cl2

~> 5,-2 we obtain (1 - 51)lf11"vl ~< (1 - 51) ~'-2 < 5 I.

Overall the expected value of the product is bounded by 5 '2 + 5' ~< 25 It/2 which

also bounds the whole sum, when applying again ~fl/}~ ~ 1 (Lemma 7.5). 9

Lemma 7.15 is in a certain correspondence to Lemma 7.9. In fact the difference

in the proof lies mainly in the use of a different distribution over the functions

f, gt, g2, and after calculating the impact of this we will reach a point where

again Lemma 7.8 will be applied, using implicitly the Weak Parallel Repetition

Theorem.

Proo] o] Lemma 7.15.

Here we have to show that for any sufficiently large

formula ~ the satisfiability follows from

(A(f)B(gl)S(g2) )l >1 5.

(7.30)

Remember that the functions f, gl, g2 are assumed to be chosen according to

D6,, and that the number of clauses the verifier chooses for the test is assumed

to be v >/v2((i, 51). The appropriate value for v2(5, 5 I) will be determined at the

end of the proof.

As in the proof of Lemma 7.9 it is again our aim to reach from the assumption

(7.30) a point where we can set up the MIP(2, 1)-protocol.

For this we use again the Fourier transform, representing

E(A(f)B(gl)B(g2)) as

E (~--~ ~1,~2 ~ A~/)fll/~2 ~e~H f(x)yet~lH gl(y)~2H g2(Y)) 9 (7.31)

Again by Lemmas 7.3 and 7.4, only the terms where fll = ~2 =: fl and a C_ fll"V

contribute to the expected value.

This transforms the sum (7.31) to

208 Chapter 7. Bounds for Approximating MAxLINEQ3-2 and MAxEkSAT

Note that we have decomposed the calculation of the expectation under distribu-

tion D~, into two aspects. The outer expectation is taken w.r.t, the distribution

of clauses r and variable sets V. Here we will obtain the same result for all r

but the distribution of sets V for fixed r will play an important role. Conse-

quently, the inner expectation is (for fixed r V) taken w.r.t, the distribution of

the functions f, gl, g2.

Now we use the shorthands

E'~'~ := E (I-I "f(x) H gl(Y)g2(Y)) ye~

and

which convert (7.32) to

E~,v := ~ .4~ E.,~,

acf~'tv

For applying Lemma 7.8 we need to show that large f~ give only a small contri-

bution to (7.31). Therefore, the following calculations are meant to be applied

for large ~ only, regardless of the fact that most of them hold for all ~.

As in the previous proof we can split the inner product into different components,

according to which y Efl restrict to the same x E fJl"V. Since a may be a proper

subset of ~I"V, there may be also some x E (~V) \ a. For those, we have to

calculate

E"'~'~ := E ( 1-[.e~:y,v=~

gl(y)g2(y)),

and in case x E a the respective part of the product is

Then we get

= I-[ l-[ (7.33)

sea ze(~'rv)\a

As in the proof of Lemma 7.14, see (7.28), we obtain from the definition of

distribution

D~,

1 ((-1)"

(1 - 2~')") (7.34)

by a simple case distinction depending on

](x).

7.6. Optimal Lower Bounds for Approximating MAXEkSAT 209

Similarly we get

1 ((-1)'" -(1- P.A')") (7.35)

where the only difference lies in the fact that we have to multiply by the value

f(x)

= -1 in the second case.

Now we estimate

oc_~'~v

\oc_~tv / \oC~tv

(

Eo,~

(7.36)

The first inequality of (7.36) is obtained by interpreting the first sum as scalar

product and applying the Cauchy-Schwartz inequality. The second one is just

another application of Lemma 7.5.

Next, we want to convince ourselves that

y~ 2

Eo,~ =

oC_~tv

((1((-1)'" - (1 - 28')")) 2+ (1((-1)'" + (1 - 28')")) 2) (7"37)

zcB1-v

In view of (7.33), (7.34), and (7.35) this means that we have to show

E o,.,. II II

~ *ca *e(/3tv)\~ *el3tV

This claim is obtained by showing by induction on the size of some helping set

N C_/~I"V that

xe(~'rV)\N

\oCN ~eo xe(~tV)\o

E2,,,x).

zEfltV

Each factor in the product in (7.37) is of the form a 2 + b 2 with lal + [b I = 1 and

z := max(la[, Ib[) ~< 1 - 6'. This implies z/> 89 and 1 - z >/6'. Hence each factor

is bounded bya 2+b 2 =l-2[a I[b 1=l-2z(1-z) < 1-289 ~< 1-6'.

Consequently

Ea,~ ~< (1 ~,)l~tVl,

a_c~tv

210 Chapter 7. Bounds for Approximating MAXLINEQ3-2 and MAxEkSAT

and by (7.36)

E~,v ~ (1 - 5')I~v,.

Here, we may apply Lemma 7.17 analogously as in the previous proof, yielding

that for If~l 1> k :=

(55') -~/c

we have the case Ifl$VI < (55') -1 with probability

at most 55 ~. This gives us, again analogously as in the previous proof,

(

E ~ E,,v < (7.3S)

Now we remind that we started from the assumption

5 ~ 'E(A(f)B(gl)B(g2))'-= ]E (E:~2~E~'V)

which by (7.38) can be transformed to

where the last inequality comes from the observation [Ea,~ I ~ 1.

Finally, we want to eliminate all • with 1.4al ~ 2-kl. For each ~ with If~l ~ k

there may be at most 2 k possible a C ~$V. Hence

and by ~/~ ~< 1, also

Thus we have

E E

B~ ~,, ~<~.

E E

7.6. Optimal Lower Bounds for Approximating MAXEkSAT 211

Now we apply Lemma 7.8. We let

7 = 2-k~/4 =

2-(6'~)-2/c$/4, and obtain

the claimed v2(5, 5~) as v(~, $~, V, k) of that lemma. Please note, that condition

a C ~3~V as well implies JaJ ~ k (by Jj3J ~< k) as it serves as condition c~ N/~,

guaranteeing the existence of some y E/~ with

y'~V E o~

(remember that ~ has

to be non-empty by .4r = 0).

Thus Lemma 7.8 gives the desired satisfiability of ~. 9

8. Deriving Non-Approximability Results by

Reductions

Claus Rick, Hein RShrig

8.1

Introduction

In the last chapter we saw how optimal non-approximability results have been

obtained for two canonical optimization problems. Taking these problems as a

starting point, we will show how the best known non-approximability results

for some other ,4PX-problems can be derived by means of computer-generated

reductions. Most of the results surveyed in this chapter are from the work of

Bellare, Goldreich, and Sudan [BGS95], Trevisan, Sorkin, Sudan, and Williamson

[TSSW96], Crescenzi, Silvestri, and Trevisan [CST96] and Hs [Hs

8.1.1 The Concept of a Gadget

Since the early days of Al/)-completeness theory, the technique of local replace-

ments [GJ79] has been a common way to devise reductions. For example, in the

reduction from

SAT to 3SAT,

each clause of

a SAT

formula is represented by

a collection of clauses, each containing exactly three literals and built over the

original variables and some new auxiliary variables. In the following we will call

such finite combinatorial structures which translate constraints of one problem

into a set of constraints of a second problem a "gadget". In order to prove the

AlP-hardness of 3SAT we only need to make sure that

all

clauses in a gadget are

satisfiable if and only if the corresponding SAT clause is satisfied (of course we

also have to ensure that the gadgets can be constructed in polynomial time).

The concept is easily extended to show the AlP-hardness of optimization prob-

lems rather than decision problems. For example, consider the following reduc-

tion from 3SAT to MAX2SAT. Each clause

Ck = X~ V X2 V X3

is replaced by

ten clauses

X1, X2, X3, --,XI v ~X2, --,X2 v -,X3, -~X3 v --,X,,

yk,x1 V ",Yk,X2 V "-,Yk,X3 V ~yk.

is an auxiliary variable local to each gadget whereas X1, X2 and X3 are

primary variables which can also occur in gadgets corresponding to other clauses

214 Chapter 8. Deriving Non-Approximability Results by Reductions

of the 3SAT instance. If clause

is satisfied, then 7 of the 10 clauses in the

corresponding gadget axe satisfiable by setting yk appropriately, and this is the

maximum number of clauses satisfiable in each gadget; otherwise only 6 of the

10 clauses are satisfiable. So if we could solve MAX2SAT exactly we would also

be able to decide 3SAT. This proves MAX2SAT to be Alp-hard.

8.1.2 Gap-Preserving Reductions

Gadgets conserve their importance in the field of non-approximability results of

optimization problems. In order to prove non-approximability results we need

an initial optimization problem which is Af:P-hard to approximate to within a

certain factor, i.e., which exhibits a certain gap. Gadgets then are to implement

so-called "gap-preserving" reductions (for a formal definition see below).

The previous chapter showed a gap for MAXE3SAT: it is AfT)-hard to distinguish

satisfiable instances from instances where at most a fraction of ~ +c of the clauses

can be satisfied at the same time. Using the same gadgets as above to replace

each clause by ten 2SAT clauses we can immediately derive a non-approximability

result for MAX2SAT. If the instance of MAxE3SAT is satisfiable, then exactly

of the clauses of the corresponding instance of MAX2SAT are satisfiable. On the

other hand, if a fraction of at most ~ clauses of the MAxE3SAT instance can be

7 7 clauses in the

satisfied at the same time, then a fraction of at most ~ ~ + Y6

corresponding instance of MAX2SAT are satisfiable. Thus we have established

an Alp-hard gap for instances of MAX2SAT and we conclude that it is hard to

approximate MAX2SAT to within a factor of 56

~-~ - ~.

In general, gap problems can be specified by two thresholds 0 ~ s ~ c ~< 1.

Let III denote the size of a problem instance I, e.g., the number of clauses in

an unweighted MAX3SAT instance or the sum of the weights associated to the

clauses in a weighted MAX3SAT instance. Then

Opt(I)/lI I

~ 1 is the normalized

optimum, i.e., the maximum fraction of satisfiable clauses in I. We can separate

instances I where

Opt(I)/lI I ~/ c

from instances where

Opt(I)/lI I < s,

i.e.,

where the normalized optimum is either above or below the thresholds. For an

optimization problem H the corresponding gap problem is

GAP-IIc,8

Instance:

Given an instance I of II in which the normalized optimum is guar-

anteed to be either above c or below s

Question:

Which of the two is the case for I?

We axe of course interested in gap problems which are AfT~-haxd to decide since

this implies that the underlying problem is hard to approximate to within a

factor of ~. The larger the gap, the stronger the non-approximability result.

The PCP based approach to find such gap problems is as follows [Be196]: First

show that AfT ~ is contained in some appropriate PCP class, then show that this