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

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

5.3. Encodings 103

We let dn be equal to mnhn, we let

C p~ ::

C(pn,mn,dn),

and we define corresponding decoding functions by

decP~ := a(q,<n,n).

Definition 5.25. The polynomial coding scheme

C p~

(pp

oly ,4~poly~ ,,/-~poly

decPOly),

"1 ' ~I /, ~,~'2 , ....

In connection with the definition of the polynomial coding scheme the cardinality

of H~- must be at least n because we want to decode strings of length n from

the restriction of some polynomial to H~"; in fact, related to the checking of

split representations as considered in Section 5.5.1 we want to ensure that even

the cardinality of Hn m"- 1 is at least n. Indeed we have

9 -n ) logn) = 21ogn = n.

Thus in particular, by choice of the dn and by Remark 5.24, each function dec p~

is onto {0, 1} n and hence is indeed a decoding function for C p~ For further

use observe that for all n >/16, we have log n >1 4 and log log n >~ 2 which then

yields easily

logn logn r logn ]

hn = [logn] >/logn/> --~-+2 >t loglog----~+2 >t |log-~gn_ +1 = mn. (5.10)

Thus the codes of the polynomial coding schemes are all defined w.r.t, parameters

where hn is greater or equal to ran. As a consequence we have always

Pn >I 36[logn] 2 = 36h 2/> 36hnrnn ~ 36d~. (5.11)

In Section 5.4.5 we will use a more general form of the polynomial coding scheme

where we add a natural number e/> 2 as an additional parameter. In order to

define this coding scheme for a given value of e we let for every natural number

Pr be the smallest prime greater than 36 [log n]e. (5.12)

Then we define the parameters mn, hn, and dn as above, and we define H~ and

<~ as above with Pn replaced by Pe,n. Observe that while Hn is now a subset of

Fp~., and not of Fp, the old and the new version of the set Hn and the ordering

<n on H m" are essentially the same and thus we will identify them with each

other, respectively. Finally we let

Cpoly "- C(p~,.,m.,d.),

e~n .-

and

we define corresponding decoding functions by

deceP,~ := a(q,<n,n).

104 Chapter 5. Proving the PCP-Theorem

Definition

5.26.

Let e be a natural number greater or equal to 2. The

poly-

nomial coding scheme with parameter e,

denoted by/~poly is

v e

(fTpoly r ,,~poly

decp~y),

"-'e,1 ' "*~'t'e,1 }, kt" e,2 , , ....

Observe that by definition

C p~

is equal to gpoly and note again that in the

sequel we will always work with this coding scheme, except for Section 5.4.5

where we consider coding schemes gpoly with e/> 2.

In the sequel we will construct resource bounded extended verifiers which expect

parts of their proof to be encoded according to the polynomial coding scheme.

Among other requirements, the parameters

Pn, ran,

etc. in the definition of the

polynomial coding scheme have to be chosen such that these extended verifiers

can apply certain procedures and probabilistic tests to the alleged codewords

while staying within their respective resource bounds. Remark 5.27 contains

some of these procedures and tests together with some corresponding restrictions

on the parameters of the polynomial coding scheme.

Remark 5.27. We list some of the requirements which motivate the choice of

the parameters in the definition of the polynomial coding scheme. For ease of

notation we fix a natural number n and we let p =

Pn, m = ran,

and so on.

First, we want

logp to be in O(poly(log n)) because during the procedure

EXTENDED LFKN-TEST we want

read poly(mh) values in Fp while scanning

only O(poly(log n)) bits in total.

Second, for the sake of the Low DEGREE TEST and the EXTENDED LFKN-TEST

we want p greater or equal to 36d (see equation (5.11)).

Third, we want m logp to be in O(log n) because in the procedures Low DEGREE

TEST and EXTENDED LFKN-TEST we want to choose m elements of F at random

while using only O(log n) random bits.

Proposition

5.28.

For every parameter e >1 2, the polynomial coding scheme

ge p~

(logn,

poly(logn))-checkable.

Proo].

We have to construct a constant (log n, poly(log n))-restricted extended

verifier that checks, given a pair (0a,Tro), whether 7r0 is ~-close to a codeword

of CeP,~ y. From the argument O n the verifier is able to compute in polynomial

time the parameters defining the code CeP,~Y:

p := Pe,n, h := hn, m := mn,

and d := dn. If we now interpret the string ro as a(~, <lex) for some function

~: ~ ~ Fp, then by definition of CeP,~Y the string 7to is a codeword if and only

if .~ can be expressed as a polynomial of degree at most d, and furthermore ro is

b-close to a codeword if and only if ~ is ~-close to some polynomial g: ~p ~ Fp

of total degree at most d.

5.3. Encodings 105

Thus we see that the main part of the problem consists of checking whether a

given m-ary function over a finite field Fp is &close to some polynomial of degree

d. Since d is typically small compared to p, this problem is usually called the "Low

Degree Test". (Note that using Lagrange interpolation, every m-ary function over

Fp can be written as polynomial of total degree

mp;

thus the problem is only

interesting for d <

rap.)

Note that the problem is made especially difficult by the

constraints we have to obey: We are only allowed to use O(log n) random bits,

and to check only a constant number of segments of 7r0 of length O(poly(log n)).

Observe that such a segment might contain up to O(poly(logn)) symbols of

a codeword in C~,~ y, because coding a single symbol from the corresponding

alphabet Fp requires [logpem] bits, that is O(loglogn) bits.

On the other hand, the verifier is allowed to use an additional string 7rl containing

information that could help with the decision. How could this information be

used? The basic idea of the low degree test is to note that if ~ is indeed a

m-variate polynomial of degree d over Fp, then for each x, h E ~ the function

t ~ ~(x+th)

is a univariate polynomial of degree d. Since the set

{x+th] t

9 ]~p}

can be geometrically interpreted as the line

l~,h

with slope h through the point

x, we will call this function the restriction of ~ to the line

l~,h.

In fact, it can

be shown that the converse statement holds as well: If the restrictions of ~ to

all lines can be written as polynomials with degree at most d, then ~ has total

degree at most d as well (see Lemma 5.67).

We will now use this fact to fix our interpretation of ul. If we suppose that

as encoded by lr0 is indeed a degree d polynomial, then all restrictions of ~ to

some line

i~,h are

polynomials of degree d which can be represented by their

coefficients: d + 1 elements of Fp. The verifier shall now expect 7h to contain

a table T that has one element

T(x, h)

for each x, h 9 l~p such that

T(x, h)

consists of the coefficients

T(x,

h)i 9 Fp for 1 ~ i ~< d + 1 of the polynomials

P~,h(t) := ~-~ T(x, h),+l " t'.

i----0

The verifier will now try to ensure that those polynomials are indeed the restric-

tions of .~ to the lines

lx,h.

Note that the table T will he coded into the string

~1 in such a way that the coefficients

T(x,h)i, 1 <. i <. d +

1, will immediately

follow each other. Thus the lookup of one polynomial

T(x, h)

can be done by

reading one segment of length

O(dlogp)

= O(poly(logn)) of 7rl, which means

our verifier is allowed to use a constant number of such table entries.

The basic operation of the verifier will now be to check whether the table T does

indeed contain "correct" polynomials/5,,h that agree with the function ~. This

is done by choosing random x, h 9 ~ and t 9 Fp, and verifying that

= + th).

One such check obviously uses

O(m

log p) = O(log n) random bits, and queries

one value of ~ and one entry of T. As noted above, this does not violate our

106 Chapter 5. Proving the PCP-Theorem

resource constraints. Thus the verifier is allowed to repeat this basic step a

constant number of times, reject if any test fails, and accept otherwise.

Prom the arguments above it is obvious that if 9 is indeed a polynomial of degree

d, we can construct a table T9 such that the verifier will never reject given 9 and

Tg. On the other hand, if 9 cannot be written as low degree polynomial, then for

each table T we can of course find some x, h, and t such that Px,h(t) 7 t ~(x+th).

This does not help us very much though, since our verifier can check only a

constant number of possible combinations x, h, and t, and we cannot guarantee

that it will find a rejecting combination among those that are tried.

But it can be shown that -- under certain conditions -- if 9 is not &-close to any

degree d polynomial, then each test of our verifier will reject with probability at

least 5/8. An exact statement of this property will be given as

Theorem 5.69. Let 0 < & < 1/6066 and d, m E N be constants, and let F be a

finite field with IF{ /> 8d and IF I >~ 1/5. Let ~: F m --+ F be a function, and let

T: F 2m ~ F d+l be a function such that the degree d polynomials Px,h over F

given by P~,h(t) = )-~d= o T(x, h),+l" t i satisfy

Probx,h,t[P~,h(t) = [?(x + th)] >1 1 - 5_.

Then there exists a (unique) polynomial g: F m --+ F of total degree d so that

Probx[g(x) = 9(x)] ~> 1 - 5.

The proof of this theorem is postponed to Section 5.7, since it is technically

rather difficult (in fact, as [Aro94] notes, for some time this was the last missing

part of the proof of the PCP-Theorem). What remains to be checked is that the

additional conditions of the theorem are satisfied in our situation. If we choose

a small enough 50, we see that this is the case, since by construction of the

polynomial codes, we have p >/8d. But, observe that the requirement p ~> 1/5

will be false for small values of n. In order to handle this problem recall that

resource bounds for extended verifiers are formulated in terms of the O-notation

and so we can simply choose the corresponding constants so large that for these

small values of n the verifier can read the course-of-values of the whole function

and can check by brute force whether it is close to a polynomial.

We finally note that if each test of the verifier rejects with probability 5/8, by

performing [2/log(1 + ~/8)~ such tests, we get a total rejection rate of

1 - (1

- ~)2/log(1T&/8) =

1 - 4~ /> 1 - 4 -1 3

=4"

We conclude the proof by explicitly stating the test procedure:

5.3. Encodings 107

Low DEGREE TEST

Read input n and compute p :-- Pe,,~, m := ran, and d :-- d,~.

Assume 7r0 and 7rl encode ~ and T as described above.

if p < 1/5 then

Perform brute-force check.

else

repeat

r2/log(1 -t- 5/8)1 times

Choose x, h E F~p and t E Fp uniformly at random.

if ~d=o T(x, h)i+l 9 t ~ ~t [l(x + th) then reject

As the above arguments have shown, the algorithm Low DEGREE TEST Can

indeed be used as a constant (log n, poly(log n))-restricted extended verifier with

the required properties. 9

Proposition

5.29. For every parameter e >1 2, the polynomial coding scheme

Ce p~ is (logn, poly(logn))-correctable.

Proof. Assuming that a given function ~: F~p --~ Fp is 5-close to some low degree

polynomial g, we know that for all but a fraction 5 of points x E F~p, the values

g(x) and ~(x) agree, but we do not know at which values x the function

misrepresents the polynomial g. To show the correctability of the polynomial

coding scheme, we need to give a verifier which checks probabilistically whether

g(x) and ~(x) agree at some given point x.

For this purpose, we use the same table T as used with the Low DEGREE TEST,

containing for each x, h E ~ the coefficients of a univariate degree d polynomial

that is supposed to represent the restriction of ~ to the line Ix,a. The idea of the

test is now to verify whether at the given point x, for some randomly chosen h,

the corresponding table entry is identical to the restriction of the polynomial g

to that line. Since both are univariate degree d polynomials, this can be checked

by considering only a few points on the line (as we will see, one point is in fact

enough). Now we do not know the polynomial g of course, but we can use the

hypothesis that g is 5-close to ~. This means that for that (uniformly chosen)

point y = x + th where we need to check g(y), we can simply use ~(y) instead

and will thus make an error with only a small probability.

Once we know that for the chosen h the corresponding table entry agrees with

g, we know all values ofg on the line i~,a, especially at the point x. Thus we can

simply check whether this value agrees with .~(x). The procedure just outlined

can be stated as follows:

SELF-CORRECT

Read input n and compute p :-- Pe,n, m := ran, and d := dn.

Read input i and determine the corresponding x E F~np.

Assume ~r0 and 7ri encode ~ and T as described above.

108 Chapter 5. Proving the PCP-Theorem

Choose h E F~v and t e Fp \ {0} uniformly at random.

T(x, h)l # it(x)

then reject

d t~

~i=o T(x, h),+l 9 ~ ~(x + th)

then reject

This algorithm satisfies the requirements: If ~ is a low degree polynomial, then

we can simply choose the same table T~ as above, and the procedure will never

reject. It remains to show that if ~ is (i-close to the low degree polynomial g, but

~t(x) # g(x),

then the algorithm rejects with probability/> 3/4.

We consider now those values of h where /5,,h(0) = ~(x) holds. Since we have

g(x)

# ~(x), and thus/5,,h(0) #

g(x)

follows, the two degree d polynomials

fiz,h

and the restriction of g to

Iz,h

can agree at most at d points t E Fp \ {0}. Since

p /> 8d and hence

d/(p -

1) ~< 1/7 by construction of the polynomial coding

scheme, we conclude that in this case

Probt#o[[~,,h(t) = g(x + th)] <<,

1/7 holds,

hence 6

Probh,t#O[fiz,h(O) ~ ~I(X) V Pz,h(t) ~ g(x + th)] >/ ~.

Now if we could replace g by ~, the above probability would just be equal to the

reject probability of our algorithm. But since for t ~ 0 the expression

x + th

uniformly distributed over F~p iff h is, and by assumption ~ is (f-close to g, we also

have Probh,tr

+ th) ~ g(x + th)] <~ 5.

Since obviously

Pz,h(t)

~ g(x q- th)

implies

[3x,h(t )

~ ~(X -t- th)

~(x + th) r g(x + th),

we conclude that

Probh,tr • ~(X) V

P,,h(t) # g(x + th)]

~< Probh,t#o[Px,h(0) # ~(x) V

Px,h(t) # ~(x + th)] + (i.

But this means that the algorithm rejects with probability of at least 6/7 - 5,

which is >t 3/4 for some small enough (i.

We conclude the proof by noting that the algorithm

SELF-CORRECT

obviously

satisfies the given resource constraints: the algorithm uses

O(m

log p) = O(log n)

random bits to choose h and t, and queries one entry of T and two values of ~. 9

As in the case of the linear code, we immediately obtain the following corollary.

Corollary 5.30.

For every parameter e >1 2, the polynomial coding scheme

Ce p~

(log n, poly (log

n)) -robust.

Remark 5.31. For the proof of Theorem 5.54 we need yet another property of

the polynomial coding scheme: For all proof strings (u0, ~1) that are not rejected

by the low degree test given in the proof of Proposition 5.28, we want to efficiently

find (and decode) the codeword nearest to ~o (which is uniquely defined since

~r0 is (i-close to some codeword, for some 5 < 1/4, otherwise it would have been

rejected by the low degree test).

5.4. Efficient Solution Verifiers 109

But we know from the proof of Proposition 5.28 that if the total rejection rate of

the Low DEGREE TEST procedure is less that 3/4 (i.e. the proof string (uo, ~rl)

is not rejected), then the rejection probability of a single test cannot be higher

than 5/8. (We suppose that we have the case p/> 1/5 here; the case p < 1/5 can

again be solved using brute force.) Now this means that the functions ~ and T

encoded by to and ~rl satisfy the conditions of Theorem 5.69, but in this case --

as we will show in Corollary 5.70 -- we can compute the low degree polynomial

g that is 5-close to ~ in time polynomial in p~ = O(poly(n)) (this holds for

every parameter e >/2 of the polynomial coding scheme).

5.4

Efficient Solution

Verifiers

5.4.1 Solution Verifiers

Solution verifiers are a special type of extended verifier which interpret their in-

put x as Boolean formula and expect their input 7r0 to be an encoded assignment

for this formula. Before we give a more precise definition of solution verifiers we

introduce some notation related to Boolean formulae.

Boolean formulae are built in the usual way from propositional variables and the

logical connectives A, V and -, which are interpreted as conjunction, disjunction,

and negation, respectively. A

literal

is a propositional variable or the negation

of a propositional variable and a

clause

is a disjunction of literals. A Boolean

formula is

in conjunctive normal form

iff it is a conjunction of clauses.

A 3-CNF formula

is a Boolean formula in conjunctive normal form with exactly

three literals per clause. In order to fix an appropriate representation of 3-CNF

formulae by binary strings observe that usually we are only interested in the

satisfiability of a 3-CNF formula and thus the formula essentially remains the

same under renaming of variables. Consequently we can assume that the vari-

ables of a 3-CNF formula ~o in n variables are just xl,...,

xn.

In this situation

it is straightforward to represent a single literal of ~p by k -- [log n] + 1 bits and

to represent a single clause by 3k bits. In order to represent the whole formula

we will specify the value of 3k by a length 3k prefix 03k-ll and we will use

another

3kin

bits for representing the m clauses of ~, thus leaving us with a

binary representation of length

3k(m +

1). We will usually identify a 3-CNF

formula with its binary representation and thus for example the language 3SAT

of all satisfiable 3-CNF formulae becomes a set of binary strings.

Remark 5.32. For technical reasons we will assume from now on that a 3-CNF

formula with a binary representation of length n has exactly n variables in the

sense that in an assignment for the formula we have to specify values for n

variables (which do not necessarily all occur in ~o). This convention is safe due

to the fact that for a 3-CNF formula with a binary representation of length n

110 Chapter 5. Proving the PCP-Theorem

the number of variables occurring in the formula must be less than n because

representing a single literal requires at least two bits.

Definition 5.33. An extended verifier V is a solution verifier with coding

scheme C ifffor every input (x, Tro),

V accepts in case x is a 3-CNF formula such that 7to is a code w.r.t. C for a

satisfying assignment of x and

V rejects in case ro is not 1~4-close to a code for a satisfying assignment of x.

Remark 5.34. Every solution verifier can be viewed as a verifier for 3SAT. Let

V be a solution verifier. Then each formula x either is satisfiable and in this

case there is some ~r0 on which V accepts, or x is not satisfiable and then V

rejects for every proof 7to because in this case no string is 1/4-close to a code

for a satisfying assignment. According to Remark 5.4 the solution verifier V can

thus be considered as a verifier for 3SAT.

5.4.2 Arithmetization of 3-CNF Formulae

In Remark 5.35 we describe a method for arithmetizing 3-CNF formulae which

will subsequently be used during the construction of solution verifiers.

Remark 5.35. We can assume that every clause of a 3-CNF formula belongs

to one of the following types

xk, r

"~,

~3 := ~,

v~Tv~, r

:= ~v ~v~.

These possible types of clauses can be arithmetized by the polynomials

(1 - xi)(X - xj)(1 - xk), p2 := (1 - xi)(l - xj)xk,

PS := (1- x~)XjXk, P4 := xixjxk,

respectively. More precisely we let V be the set of variables {x0,..., xn-1} and

for ease of notation we identify V with the set {0,... ,n - 1}. By means of this

identification the usual strict ordering on the natural numbers induces a strict

ordering < on V. Recall from Section 5.3.4 that a function g from V to a field

Fp corresponds to a binary string s := a(g, <) of length n. Here s = b0... bn-1

can be viewed as an assignment for the variables in V where the value for the

variable xj is equal to bj. We leave it to the reader to show that now indeed

for every function g from Y to Fp, the expression pr(g(i),g(j),g(k)) evaluates

to zero iff the assignment a(g, <) satisfies the clause Cr(Xi, xj, Xk).

Next we consider a 3-CNF formula q0 in variables x0,..., xn-1 and again we

let V = {0,...,n - 1}. In order to obtain an arithmetization of qo we define

5.4. Efficient Solution Verifiers 111

indicator functions X1,...,X4 from V 3 to {0, 1} which correspond to the four

types of clauses and where for example

Xl(i,j,k)

is 1 iff ~ contains a clause

xi V xj V xk.

Then a function g from V to a field Fp corresponds to satisfying

assignment

s = a(g,

<) for qo iff we have for all r = 1,... ,4 and for all

(i,j,k)

in V 3

x~( i, j, k) . p~ (g( i), g(j), g( k ) ) = 0

(5.13)

Thus we can for example test whether a(g, <) is a satisfying assignment for

by testing whether for r = 1,... ,4, the function shown in equation (5.13) is

identically zero on V 3.

Note that the arithmetization by the polynomials Pl,-.. ,P4 as given in Re-

mark 5.35 differs from the more intuitive standard way of arithmetizing Boolean

formulae where for example the formulae ~ and x A y are arithmetized as 1 - x

and xy,

respectively.

5.4.3 An

(•3,

1)-Restricted Solution Verifier

In this section, an (n 3, 1)-restricted solution verifier with linear function coding

scheme will be constructed. As described in the previous section, we use the

vector

~(x) = ~5(xo,..., x,~-l)

= (xr( i, j, k ) . pr(xi, x3,

Xk ) )( i,j,k,r)EV3•

of length 4n 3 as an

arithmetization

of the 3-CNF formula ~o on n variables in

V = (x0,...,x,~-l}. Here and in the sequel we denote by [ml : m2] the set

(n E N : ml ~< n A n <~ m2} and we abbreviate the vector (x0,... ,xn-1) by x.

As usual, we identify a function g : V --~ F2 with a binary string of length n, and

hence with an assignment for a 3-CNF formula ~. Note that a satisfying assign-

ment of the 3-CNF formula ~ corresponds in a natural way to an assignment of

(Xo,..., xn-1)

for which the vector qS(Xo,..., xn-1) is zero.

Observation 5.36.

A 3-CNF formula ~ is satisfiable if and only if its arith-

metization ~(x) is zero for some x e ~2 .

Testing whether such a vector q~(x) is zero can be done by testing whether the

scalar product of qb(x) and a random vector v E F~2 n3 is zero. While

~(x) T. v = 0

whenever qS(x) = 0, it is nonzero with probability 89 whenever qS(x) # 0 as shown

in the following lemma:

Lemma 5.37.

Let 0 # z E F~2 , then Probv[zTv #

0] = 89

112 Chapter 5. Proving the PCP-Theorem

Proof.

First note that due to Definition 5.15

lz(v)

= zTv

and lo - O.

Hence the

claim follows from Lemma 5.16, which states that

lz and lo are

exactly 89 9

We now take a closer look at the scalar product

~(X) T 9 V ---- /~b(:c)(V)-

A funda-

mental observation is that l~(x)(v) can be rewritten as follows:

l~(x) (v) -- Z Xr (i,

J, k) . pr (xi, x j, xk) "

V(i,j,k,r)

(i,j,k)Ev s

.E[l:4]

= c(v)+

Z xi+ Z xixj+ Z xixjxk,

(5.14)

i~sl(v) (i,3)~s2(v) (i,j,k)~Ss(v)

where the constant c(v) and the sets Sx(v), S2(v), S3(v) depend only on v and

the given 3-CNF formula ~o, but they are independent from an assignment for x.

Thus, if we have random access to the following sums

Zg(i )

for all S C {O,...,n- 1}, (5.15)

iES

g(i).g(j)

for all S C {0,...,n- 1} a, (5.16)

(i,j)ES

Z g(i).g(j).g(k)

for all S C_ {O,...,n- 1} 3, (5.17)

(i,j,k)eS

of a given assignment g for

x = (xo,... ,xn-1),

the values of these three sums

will suffice to check the satisfiability of the given formula ~o. Observe that each

listing of all sums given in equation (5.15), (5.16), and (5.17) can be expressed

as a codeword of the linear function code, where the sets S are interpreted as

its arguments.

To be more precise, we need the following definitions. Let

x, x'

E F~2 be two

vectors, then we denote by x o x ~ the following vector y E F~2 2 given by

Yz,j =

x~ -xj. Here we identify the matrix element

yi,j

with the vector element

Y(i-1)n+j.

Similarly, let x E F~2 and y E F~2 2 be two vectors, then we denote by x o y

the following vector z e ~3 given by

zi,j,k

----

X i "Yg,k"

Again, we identify the

tensor element

zi,j,k

with the vector element

Z(i_l)n2+(j_l)n+k.

For

a fixed vector

a E F~2, let b =

bi,j = a o a E F~2 2 and c = Ci,j,k

= a o b E F~2 ~ . Using these vectors

a, b, and c, we can define the following three codewords A :-- l~, B :-- Ib, and

. . . 2

C :=

of the hnear function code with codeword length of 2 n, 2 n , and 2 ~3,

respectively. If

ai = g(i)

for all i E {0,..., n - 1) then the codewords A, B, and

C correspond exactly to the listing of all sums given in equation (5.15), (5.16),

and (5.17), respectively.

In what follows we construct a solution verifier based on these three linear codes.

Recall that for a solution verifier the input x is an encoding of a 3-CNF formula ~o

and that 7r0 of the proof zr = (Tr0, zrl) is an encoding using the linear function

coding scheme of a satisfying assignment of qo. Note that if g is a satisfying