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

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

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

7.5.3 Soundness

The following soundness properties of the verifier are much more difficult to

prove than the previous lemma.

Lemma 7.10 (soundness of the verifier).

Let 5 > O. Then there exists a

constant vl (5) such that the following holds for every input ~o: if for some v >/

vl (5) verifier

Vlin[5, v]

accepts some ~r as a proof for ~o with probability at least

(1 + 5)/2

and if ~o has at least m(v) clauses, then ~o is satisfiable.

For an explanation of m(v), see Lemma 7.8.

Proof.

We need some more notation. When ~ is a set of assignments W --+ B

and when V C W, then we write/3J'2V for the set of all assignments x: V -4 B

there exists an odd number of elements y E/7 with

ySV = x

for.

Let ~o be a E0-ROBE3SAT-b instance and ~r a proof that is accepted with prob-

ability at least (1 + 5)/2 by Vlin[5,v]. Define k by k -- [-(log5)/5], and let T

denote the set of all pairs (r V) where r E (~) and V is a set of variables with

one variable from each clause in r

If we show

A~,=v(B~)

>/5/2, (7.16)

then, by Lemma 7.8, ~o is satisfiable, provided ~o has at least

re(v)

clauses and

,iv

v >>. v(5, 5, 5/4, k).

(Recall that ~t=v /> 5/4 implies that f~t2V ~ 0. Clearly,

Ifll ~ k implies 1fl~2V I ~ k.) In other words, setting vl (5) = v(5, 5, 5/4, k) makes

Lemma 7.10 true, provided (7.16) holds under the given assumptions. So in the

rest of this proof, we will show that (7.16) holds.

The test in Step 3 is passed iff

AV(f) 9 Br 9

Be(g2) = 1. If the test is not

passed, then

AV(f) 9 Be(g1) 9 Be(g2)

= -1. Thus the probability that the test

is passed is given by

1 (1 +

E(AV(I) 9 Be(g1) 9

Be(g2))) (7.17)

Hence, by assumption,

E (AV(f) 9 Be(g1) 9 Be(g2)) >>. &

(7.18)

The left-hand side of (7.18) can be written as

7.5. An Optimal Lower Bound for Approximating MAxLINEQ3-2 195

ITI

(AY(f) 9

Br 9 B~(g2)), (7.19)

(~,,Y)eT

where each expectation is taken on the condition that r and V are chosen.

Fix (r V) from T, and consider one of the summands in the above expression.

For notational convenience, we will drop the superscripts with A and B and not

spell out multiplication any more.

By Fourier expansion, we obtain

E (A(f)B(g~)B(g2))

Z "4'~B&Bfl2 E(Hf(x) Hgl(Y) Hg2(Y)) "

c~,fll ,f~2

xEo~

yEfll yEfl2

From Lemma 7.8 we can conclude that the right-hand side of the previous equa-

tion is identical with:

Consider one of the inner expectations, namely

E (,~e~'f(x) l-I /

(7.20)

(7.21)

for fixed a and ft. By independence, this expectation can be split into a product

of several expectations:

x E fltv z E fll"V

sea

y =z z~a yTV=x

We first calculate the expectations in the left product, where we split according

to whether

f(x)

= 1 or

f(x)

= -1 and use s~ to denote the number of elements

y e fl such that

yTV = x:

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

---- ~ E(gl (~])g2 (Y))

E(gl (Y)g2 (Y))

ye~ ~e~

yTV = z yTV = z

I(=) = 1 I(=) = -1

1 { (1-2(f) s:, ifs=isodd,

= ~ ((1 - 25) s= - (26 - 1) s=) = 0, otherwise.

Similarly, we get

( ) { (1 - 25)s~' if s~ is even' 0, otherwise.

E 1-[ g~(y)g2(y) =

yE~,y~V----x

So (7.21) is non-zero only if

- for all x E j31"V where x E a, there is an odd number of elements y E/7 such

that

y'tV = x, and

- for all x E/~I"V where x ~ a, there is an even number of elements y E/7 such

that

yTV = x.

This is true if and only if a = f~T2V. In this case, (7.21) evaluates to

1-I (1- 25)'-.

zEI3TV

Now, observe that by definition, ~=e~ s= = I/~l. So (7.21) evaluates to (1- 28)I,I,

and we can write (7.20) as

9 ,4n'i'=v D~(1 - 25)1nl.

We try to identify small summands in the above sum.

First, observe that because of Lemma 7.5

A#t=v/}~(1 - 25) I#1 < 5/4.

n: IA~,2v 1~<6/4

(7.22)

Using the fact that (1 -x)

1/z

< 1/e for small x, we obtain (1- 25) -0~ ~< 62.

Assuming 5 < 1/4, this implies (1 - 25) -0~ ~< 6/4, which gives

-4/~+2v/}~(1 - 25) I/~l < 5/4. (7.23)

From (7.22) and (7.23) finally follows (7.16). 9

7.5. An Optimal Lower Bound for Approximating MAXLINEQ3-2 197

7.5.4 Reduction from e0-ROBE3SAT-b

The proof of Theorem 7.1 can now be completed by a description of a reduction

from g0-ROBE3SAT-b.

Let 5 > 0 be a rational number such that 1 - 5/> 1 - E and (1 + 5)/2 ~ 1/2 + e,

i.e. 5 ~ e. Let v be greater than vt(5) from Lemma 7.10.

The reduction distinguishes two cases.

First case, ~ has at most re(v) or at most ml (v) clauses. The reduction produces

a single equation if ~ is satisfiable and two inconsistent equations otherwise. In

the first case, all equations can be satisfied at the same time; in the second case,

at most 1/2 of the equations can be satisfied at the same time.

Second case, ~ has more than re(v) and more than ml (v) clauses. The reduction

produces a set of equations in variables denoted X v (f) and Yr (g) corresponding

to the positions of a proof for the verifier Vlin[5, v].

A proof 7r itself corresponds to an F2-variable assignment v. for these variables

(via the correspondence given by -1 ~ 1 and 1 ~-~ 0). Given a proof ~r, the test

in Step 3 is passed iff

Xv(f) + YC(gt) + Yr = 0 (7.24)

holds under the assignment v,.

There is a minor point we have to take care of here. We have to rewrite (7.24) in

certain situations according to the convention for accessing a proof described in

Subsection 7.3.2. For instance, if f(1) = -!, gl (1) = 1, g2 (1) = 1, max(g1, he) =

gl, and max(g2,hr = g2, then (7.24) takes the form xv(-]) + Yr +

Yr : 1.

Let S~ be the set of all tuples (r V, f, gl, g2) for which (7.24) is satisfied under

v=. The probability that the verifier accepts ~r as a proof for ~ can then be

written as

Z Pr~176162

As 5 was chosen rational, there exists a positive integer N such that for every

(r V, f, gl, g2) E ~ the number N- Prob~(r V, f, gl, g2) is an integer.

The reduction produces for each tuple (r V, f, gl, g2) occurring in S. exactly [TI-

N. Prob~(r V, f, gl, g2) copies of (7.24) respectively an appropriately modified

version of (7.24).

Let E denote the resulting system of equations. Then the probability a proof 7r

is accepted is the ratio of the maximum number of equations in E satisfiable at

the same time to the overall number of equations in E.

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

On the one hand, if ~o is satisfiable, then, by Lemma 7.9, at least 1 - 5 >/1 - ~ of

the equations can be satisfied at the same time. If, on the other hand, ~ is not

satisfiable, then, by Lemma 7.10, at most (1 + 5)/2 ~ 1/2 + e of the equations

can be satisfied at the same time.

7.6 Optimal Lower Bounds for Approximating MAxEkSAT

In this section we will present the proof that MAxEkSAT cannot be approxi-

mated in polynomial time within a factor of 2k/(2 k - 1) - v, for any constant

> 0, unless P = AlP.

Grounding on the results of the previous section, it needs only a small additional

effort to reach this claim in the broader sense suggested by the above formulation.

But as we will see this only shows, in case k = 3, AfT~-hardness of separating

formulae where fractions of 1 - e and 7/8 + z, respectively, of the clauses can be

satisfied.

The main part of the section will be devoted to the sharpened result stating

that it is AlP-hard to separate satisfiable E3ShT-instances from those where

only a fraction of 7/8 + 6 of the clauses can be satisfied. From this we can easily

generalize to case k >/3.

Remember that, when dealing with maximization problems, we consider a ver-

sion of E3SAT where formulae are sequences of clauses rather than sets. This

allows multiple occurrences of clauses and can equivalently be seen as having

weighted clauses, where for a fixed ~ there exists a fixed (and finite) set of possi-

ble weights for the clauses. MAXE3SAT is then the problem of satisfying a subset

of clauses having a maximal weight. The weights will result from probabilities

in the following.

Theorem 7.11.

For

MAXE3SAT,

there exists no polynomial time

(8/7 - E)-

approximation algorithm for any small constant E > O, unless 7~=Af7 ).

Proof.

We give a reduction from MAXLINEQ3-2 to MAXE3SAT, mapping the

(1/2 + e~, 1 - s~)-gap of Theorem 7.1 to a (7/8 + ~, 1 - ~)-gap here.

An equation x + y + z = 0 is replaced by the clauses (5 v y V z), (x V ~ v z),

(x V y V ~), (5 V ~ V ~), whereas x + y + z = 1 is replaced by the remaining four

possible clauses over the three variables.

By any assignment to the three variables exactly one of the eight possible

clauses is not satisfied. This one belongs always to the equation not fulfilled

by the "same" assignment (identifying the elements of F2 with Boolean values

by "true=l" and "false=0"). This means that for each equation fulfilled by an

7.6. Optimal Lower Bounds for Approximating MAxEkSAT 199

assignment all four clauses are satisfied, and for any equation not fulfilled we

have three out of four clauses satisfied.

This translates fractions of 1/2 + e ~ and 1 - c ~ fulfilled equations to fractions of

7/8 + ~ and 1 - e satisfied clauses, respectively, when letting ~ -- 4e. 9

7.6.1 Separating Satisfiable from at most (7/8 "Jr- e)-Satisfiable

Formulae

We now turn to the sharpened result.

Theorem 7.12. For any small e > 0 it is Alp-hard to distinguish satisfiable

E3SAW-instances from those where at most a fraction of 7/8 + r of their clauses

can be satisfied.

The strategy of the proof will be the following (roughly explained in Section

7.1, and similar to the proof of Theorem 7.1). Overall we will give for any fixed

(0 < r < 1/8) a polynomial time reduction from e0-ROBE3SAT-b (shown to

be AlP-hard for some Co < 10 -4 and some fixed b in Lemma 4.9) to (1/8 - ~)-

RoBE3SAT-b'.

Since polynomially bounded weights can be converted into multiple occurrences

of clauses as described in case of equations in Section 7.5.4, it will be sufficient to

give a reduction to a polynomially weighted variant of (1/8 - e)-ROBE3SAT-bL

As in the proof of Theorem 7.1 the reduction will be obtained via a verifier for

eo-ROBE3SAT-b. The crucial properties of this verifier will be the following.

1. Any satisfiable formula ~o will be accepted with probability 1.

2. Any unsatisfiable formula ~ will be accepted with probability less than

7/8 + e.

3. Acceptance of the verifier on a given formula ~ can be expressed by a (poly-

nomially) weighted formula ~o ~ where the maximal weighted fraction of sat-

isfiable clauses of ~d will be the probability of the verifier to accept ~.

The verifier will be very similar to the one defined for MAXLINEQ3-2. Again

we let the verifier choose a set r of clauses with variables W and a subset V of

one variable per clause. The "proof of satisfiability" for a formula qo will again

contain for an assignment to the variables of q0 the long codes A y and B r for

each such r and V. The difference to the previous construction lies in the test

the verifier performs on ~ and the collection of long codes, which will be a bit

more complicated this time.

Before giving the proof of Theorem 7.12 we describe the verifier and state the

main lemmas for showing the claimed probability in the outcome of it.

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

The basic test performed by the verifier will use again functions from V and W

into B = {-1, 1} with the correspondence to Boolean functions as explained in

Section 7.3.

Test 7.13. (Parameters: 0 < 5 ~ < 1, v E N.)

Input: an instance ~o of ~o-ROBE3SAT-b with kol />

re(v).

Proof: ~ =

((AY)ve(V,,:(~,)),(Br162

1. Randomly choose a set of v clauses r e (~v) with variables W = Vat(C) and

a set V e (va:(,)) consisting of one variable per chosen clause.

2. Pick ] and gl randomly as functions on V and W, respectively.

3. The function g2 on W is taken randomly within the following constraints

(where x = yTV):

a) if f(x) = 1 then

gl(y)g2(y)

= -1 must hold;

b) if f(x) = -1 then with probability 5' we choose g2 such that

gl (y)g2(Y) = -1, and gl (Y)g2(Y)

: 1 otherwise.

4. Check if

min(AW(f),

Be(g1), Be(g2)) = -1.

The above distribution of chosen tuples (r V, f, gl,g2) is just the distribution

D6, as described in a slightly different manner in Subsection 7.3.3.

Now we remind of the access conventions of the proofs as introduced in Section

7.3.2. The conventions about negation, i.e. conditions (7.5) and (7.6) will only

be used later in the main proof. Here we concentrate on condition (7.7) under

which the above test can be restated as checking whether

min(AY(]), B r (max(g1, he)), Be(max(g2, hr = -1

holds. In the corresponding logical notation this means the satisfaction of

AV(f) Y B!b(gl

A r V Be(g2 A r

Note that the possibility of rejecting unsatisfiable formulae for Test 7.13 results

only from this "masking" by he: Without it any fixed assignment (satisfying

or not) would guarantee success. If ~r contains only long codes which are all

obtained from the same assignment for the entire formula we would always have

Av(])

= f(x), Be(g1) =

gl(Y),

and Be(g2) = 92(Y) for the restrictions y and x

of this assignment to Vat(C) and V, respectively. But this would imply

min(AV(f),B~(gl),Br = min(.f(x),gl(y),g2(y))

= -1 (7.25)

7.6. Optimal Lower Bounds for Approximating MAXEkSAT 201

according to distribution D6.

Now by conditions Br = Br he)) and B ~ (g2) =

BC~(max(g2,

he)),

we can have Br = gt(Y) and Be(g2) = g2(Y) for every r only if the fixed

assignment is

satisfying

for the

entire

formula (in which case always he(y) =

-1 and hence max(g, hr

= g(y)).

Clearly this cannot be the case for an

unsatisfiable formula.

By the above argumentation, we have already convinced ourselves that (7.25)

holds if ~r consists of long codes generated from an assignments which satisfies the

whole formula. Hence by using such a proof, Test 7.13 will accept any satisfiable

formula with probability 1.

Based on the elementary Test 7.13, the actual test done by the verifier will consist

of choosing an instance of Test 7.13 on a random distribution over several possible

parameters 51,..., (it. The existence of an appropriate rational constant c and

positive integer v2(~, Ji) will be part of the proofs of the respective lemmas.

Constant c is needed, and determined, in the proof of Lemma 7.17, and the

existence of v2(5, 5i) will be shown in the proof of Lemma 7.15. For giving the

reader an impression how the constants 5i are chosen below, we remark that c

may be fixed to be ~ (see also the comments after Lemma 7.17).

Verifier Vsat[5].

: , = jS/c

for i = 1,2, .. t- 1, and

(It uses the constants t r5-11 51 52, 5i+1 = -i 9 ,

v := max{v2(5, Si) : i = 1,... ,t}).

Input: an instance ~0 of eo-RoBE3SAT-b s.t. ko[ >/re(v).

Proofi 7r =

((AV)ve(v~(~,)),(Br162

1. Randomly choose j e {1,..., t} with uniform distribution.

2. Perform Test 7.13 using parameters 6j and v and accept iff the answer is

positive.

The resulting general distribution over tuples (r

V, f,91,92),

obtained as a sum

over the distributions D6j,j = 1,..., t, divided by t, will be denoted

Dgen.

Besides these definitions, we will need in the proof of Theorem 7.12 the following

two lemmas which themselves will be proved in Section 7.6.2. They give estimates

on the important parts in the calculation of the acceptance probability of Verifier

Vsat[5], where especially the second one bounds this probability for unsatisfiable

formulae.

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

Lemma 7.14.

Let qo be an instance of

eo-ROBE3SAT-b.

Then for any proof

(( v )) for ~v, and for any small constant 5' > 0 holds

7r = A )ve(V,:(~)),(Br162

[E (BCJ(gl)B~(g2))I <.

35 '1/2 + E (/~)2 (7.26)

f~ :6'-1/2 <lf~l~<~,-4/~

where the expectation is taken w.r.t, distribution Da,.

Lemma 7.15.

For any small constants 5,5' > O, there exists a constant

v~(6,5') E N such that for all v >1 v2(5,5'), and for any formula ~ with

I~1 >~

re(v),

the following holds.

there exists some proof 7r = _ ( ( A V )v e (V.~)) , ( Br ) r ~) ) _ for the formula

such that w.r.t, distribution D~,

(AV(f)Br162 >1 5,

then ~a is satisfiable.

In the following, we will usually omit superscripts V and r for simplicity.

Proof of Theorem 7.12.

We will give a reduction from c0-ROBE3SAT-b to a

weighted version where in case of unsatisfiability at most a fraction of 7/8 +

can be satisfied. We choose 5 as a rational number such that (7+55)/8 ~< 7/8+~,

i.e. 5 ~< 8~/5. We use the constants t, 51,...,St, and v from the definition of

verifier Vsat[5], and we let

re(v)

be as defined in Section 7.4.

For formulae of length less than re(v), we have to do the reduction by hand. That

means mapping each satisfiable formula to a single clause and each unsatisfiable

formula to a formula consisting of all eight possible clauses over the same three

variables. By any assignment exactly seven out of these eight clauses are satisfied.

In case lto] />

re(v)

we will first convince ourselves that it suffices to show:

if Verifier Vsat[5] accepts a formula qo with probability (7 + 55)/8 then qo is

satisfiable, and for each satisfiable formula, there is a proof such that the verifier

accepts with probability 1.

Since the success criterion of each single elementary test is a disjunction of the

form

A(f) V B(gl)

V B(g2), it can be translated immediately into a clause with

three literals, when using a separate variable for each position in the long codes

A and B. (The use of long code values

-A(f)

instead of

A(-f),

and analogously

for B, as described in Subsection 7.3.2, causes here the use of negated variables

where appropriate.)

Together with the weights resulting from the probability that Verifier Vsat[5]

performs each single test, this gives already the claimed formula with the max-

imal acceptance probability of the verifier as maximal fraction of satisfiability.

7.6. Optimal Lower Bounds for Approximating MAxEkSAT 203

Since for each fixed 6 the other constants will be fixed too, we have as desired

only finitely many weights.

Also, this assures that the occurrence of each variable in the resulting formula

can be bounded by some constant U.

Now we want to calculate the acceptance probability of Vsat[6]. As we have

noted above, Test 7.13 will always succeed if ~ is generated from a satisfying

assignment. This transfers immediately to the whole verifier, which means that

for any satisfiable formula there is a proof such that Vsat[6] will accept with

probability 1. It remains to show the upper bound of (7-t-56)/8 for the acceptance

probability of unsatisfiable formulae.

We observe that the result of Test 7.13 can be calculated as

(1 + A(f))(1 § B(gl))(1 -t- S(g2)) (7.27)

1-w

if we identify "accept'with 1 and "reject" with 0.

Therefore the acceptance probability of Verifier Vsat[6] is just the expected

value of (7.27) under the distribution Dgen.

Expanding the expectation of the above product results in the term

_ 1 E(a(f)B(g:)) - 1 E(B(gl)B(g2)) - 1 E(A(f)S(gi)B(g2))

This is equal to

E( B(gl )B(g2) )

-g A(I) E( B(gl ) B(g2 ) )

8 8

since all others terms have expected value 0 as being products of indepen-

dent functions only, which are chosen equally distributed from B v --~ B and

B w -+ B, respectively.

For any unsatisfiable formula ~, Lemma 7.15 bounds the absolute value of the

last term by 6/8.

For

E(B(gl)B(g2))

Lemma 7.14 gives us

(B(gl)B(g2))l ~ -~ ~

36~/2 +

= ~:

~7~/~<1~1<~C 4/~

For obtaining the second inequality above we use the fact that the choice of the

6i was made such that the intervals of the inner sum are consecutive, i.e.