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

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

5.7. The Low Degree Test 153

Theorem 5.69.

Let

0 < 6 < 1/6066

and d, m E N be constants, and let F be a

finite field with

tFI

>>. 8d and

IFI

>/1/6.

Let g: Fm ~ F be a function, and let

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

given by P~,h(t)

= •d= o

T(x, h),+l" t ~ satisfy

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

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

Prob~[g(x) = ~(x)] >i 1 - 5.

~,d

Proof.

For x, h E F

we will denote the degree d line polynomial

P~,h

P~,h.

The function g is then given explicitly by

g(x) = majoritYh {Px,h(O) },

that is,

g(x)

is a value so that I{h I

Px,h(O)

= g(x)}] /> I{h I P~,h(O) = a}l for

every choice of a E F. In case there should be several candidates equally suited

for choice as

g(x),

we choose one arbitrarily (we will see later that this cannot

happen and g is indeed uniquely defined).

By assumption we have

erob~,h,t[P~,h(t) # ~(x + th)] <~ ~,

(5.34)

hence

1 35

Prob~,h[Probt[Px,h(t) ~ ~(x + th)] > -~] < -~.

By Lemma 5.65 we know that

P~,h ~ P~,h

implies

Probt[Px,h(t) = ~(x + th)]

1/2(1 +

d/IFI) <~

1/2(1 + 1/8) = 9/16 and hence

Probt[Px,h(t) # ~(x + th)] >1

7/16 > 1/3. Thus we conclude

Prob.,h[/5.,h ~

e~,hl ~< 3_~

and together with (5.34) also

35 5 5

Prob~,h,t[P~,h(t) r [7(x + th)] <<. -~ + -~ = -~.

We can even strengthen the result: If we fix a t E F, we can replace in the above

equation t by t + t' and x by

x - t'h

to get

Probx,h,t,[Pz-t,h,h(tq-t')

~ ~(x-t'h+(t+t')h)] = Prob~,h,t,[P~,h(t) ~ ~(x+th)],

since

Px-t'h,h(t "{- t t) ~- Px,h(t)

according to the consistency criterion for line

polynomials. Thus we conclude

154 Chapter 5. Proving the PCP-Theorem

Probx,h[P~,h(t)

~ 9(x + th)] <~ ~

for all t 9 F. (5.35)

Note that this equation is no longer a statement about averages taken over x, h, t,

but one about averages taken over x, h that holds for every t. By an application

of Lemma 5.68 we can strengthen the result even more, yielding a statement

where averages are taken only over h: For every

hi,h2 E F m,

let

A = (ast)

denote the matrix given by

ast = 9(x + shl + th2),

and let

rs(t)

= Px+shl,h2(t)

and ct(s)

Pz+th2,h,(8).

If we replace x by

x+shl

for s ~t 0 and h by h2, (5.35)

yields

Probhl,h2[rs(t) r = Probhl,h2[P~+shl,h2(t) ~ 9(x + Shl +

th2)] <

for all t 9 F, hence [SI/> IF\{0}I = IF[ - 1 >/(1 - 5)IF ] since IF I I> 1/6. As we

similarly conclude ITI /> (1 -5)[FI, all assumptions of Lemma 5.68 are satisfied,

and the lemma yields

Probh,,h2[Pz+8ohl,h2(to) ~ Px+toh2,hl(SO)] ~

546 for

all x 9

F m, so,to E F,

(5.36)

since by definition

Pz+sohl,h2

is the line polynomial for the so-th row and

Px+toh2,hl

the line polynomial for the t0-th column of A. If we fix now

x 9 F m

and t 9 F\{0} and consider the special case so = 0 and to = t of (5.36), we

deduce that

Probh~,h2

[Px+th2,h, (0) ~ P,,h2

(t)] < 546.

On the other hand, replacing x by

x + t(h2 -

hi) (this is possible since t ~t 0)

and h by hi and using

P~+t(h2--hl),h, (t) = Px+th2,h,

(0) (by consistency), (5.35)

yields 5

Probh,,h2

[Pz+th2,hi

(0)

~ g(X + th2)] ~ 2"

Combining those two inequalities we conclude

Probh[P~,h(t) r 9(X + th)] <.

54.55 for all x 9 E ra and t 9 F\{0}. (5.37)

Furthermore we can use the special case so = to = 0 of (5.36) to prove the above

claim that

g(x)

is uniquely defined: Indeed, for every x E Fra we have

1 - 546 ~ PrObhl,h2

[Pz,hl (0) = P~,h2

(0)]

= ~ Probh,

[Px,hl

(0) = a]. Probh2[Px,h2

(0) = a]

aEF

< Probh[Px,h(O) =

g(x)]. ~

Probh[Px,h(O) = a],

aEF

where the last inequality holds since

Probh[P~,h(O) =

g(X)] >/

Probh[P~,h(O) = a]

follows from the definition of g for any a E F. Since we furthermore know that

~,~eF Probh[P~,h(O)

= a] = 1, we conclude

5.7. The Low Degree Test 155

1 Fm.

(5.38)

Probh[Px,h(O) =

g(x)] >t 1 -- 545 > ~ for all x E

We proceed now to prove the 6-closeness of g to g- First note that

g(x) ~ j(x)

implies 9(x) ~

Px,h(O)

g(x) ~ Px,h(O)

for every

h E Fm.

We can write this as

Probh[~(x) # P,,h(0)] + Proba[g(x) # P~,h(0)] /> 1,

which implies

Probh[~(x) # P~,h(0)] >/Probh[g(x)

P~,u(0)] >

by (5.38). On the other hand, the special case t = 0 of (5.35) yields

Frobx[Probh[~(x) # P,,h(0)] > 5] ~< 6,

and thus

Prob,[g(x)r ~ 6.

(5.39)

Note that this allows us to extend (5.37) to the case t = 0: as (5.39) and (5.38)

imply

Probh[Px,h(O) ~

~(X)] ~< 546 + 6 -= 556 for all x E F m,

we combine this with (5.37) to get

Frobh[Px,h(t) 7s ~1(x + th)] <~

555 for all x E F "~ and t E F. (5.40)

What remains to be shown is that g is actually a degree d polynomial. This

requires another application of Lemma 5.68: Let

x, h E F m

be fixed. For every

hi, h2 E F m

let A' = (a'u) denote the matrix given by

, [ g(x+sh) if t=0

au = ~ ~(x + sh + t(hl +

sh2)) otherwise

and let

rts(t)

= Px-l-sh,hl§

(t)

and

c~ (s)

---- Px-l-thl,h+th2 (8).

Note that replacing

x with x + thl and h with

h + th2

for any t E F\{0), (5.35) yields

Probhl ,h2 [c~ (s) r a'st ] ---- Probh,,h2

[Px+th, ,h+th~ (S) ~ ~(X + thl + s(h + th2))]

for all s, t E F, t ~ 0. On the other hand, setting x to

x + sh

for some s E F

and replacing h with

hi + sh2

in (5.37) we get

Probh,,h2

It's (t) r a'st ] -=-

Probh~,h2[Px+sh,h,+sh2(t) ~ ~(x + sh + t(hl +

sh2))] ~< 54.55

for all t e F\{0}. But for t -= 0 we can use (5.38) to get

156 Chapter 5. Proving the PCP-Theorem

Probh~,h2V~(O) #

a~s,o] = PrObhl,h2

[Px+sh,hl+sh= (0) # g(x + sh)] <~

546, (5.41)

concluding

PrObhl,h2[r~s(t) # also] <~

54.56 for all s,t 9 F.

Hence, if we replace 6 by 1096, the assumptions of Lemma 5.68 are again satisfied.

Applying the lemma in the case so = to = 0 we therefore conclude

Probhl,h2[Prow(O) # Pcot(O)] <~

58866.

(5.42)

Furthermore, we note that by Lemma 5.65 we know that

Prow ~ r~

implies l{t E

F [ r~o(t)

= a~,t} ] < 1/2(]F] + d), and hence

I{t E F I Px,hl(t)

g(x q-

thl)}[

1/2(IF] +d)+ 1 ~< 1/2(1 + 1/8)lFI +

6IF [

< 1153/2048]F I since 6 < 1/2048, and

hence Probt[P~,h,

(t) # O(x + thl)]

> 895/2048. Since (5.40) yields

Probh~[Probt[Px,h~(t) # ~(x +

thl)] > 2~458 ] ~< 28-~-58556,

we conclude

Probh~,h2[Prow ~ r~] ~< 1266.

This combined with (5.41) for s = 0 and (5.42) yields

Probh,,h2[Pcot(O) r

g(x)] ~< (54 + 126 + 5886)6 = 60666 < 1

by choice of 6. On the other hand, we see that since the first columns of the

g,d

matrices A t do not depend on hi or h2,

Pcot

is in fact identical to

P~,h,

the

degree d line polynomial for g. Since

g(x)

does not depend on hi or h2 either,

we conclude

g,d

P~,h(O)=g(x)

forallx, hEF m.

g,d

Using the consistency

condition

P~+th,h(O) = PSz, h

(t) we even have

g,d

P~,h(t) = g(x + th)

for all x, h E F m, t E F,

but then we can conclude from Lemma 5.67 that g is a degree d polynomial. 9

For the proof of Theorem 5.54 we need the even stronger property that the

polynomial g, whose existence is guaranteed by Theorem 5.69, is even efficiently

computable. This follows as an immediate corollary of the proof just given and

Lemma 5.66, though.

Corollary

5.70.

In the situation of Theorem 5.69, there exists an algorithm

that takes the course-of-values of [? as input and computes the course-of-values

of g as output, provided the conditions of the theorem are satisfied. The running

time of the algorithm is polynomial in the size of its input (i.e. polynomial in

[Fm]).

5.8. A Proof of Cook's Theorem 157

Proof. Since the function g was explicitly given by

g(x) = majoritYh {P~,h(O) }

in the proof of Theorem 5.69, where P~,h was defined to be the degree d line

polynomial for ~ on the line lx,h, we want to make use of this definition in our

algorithm. Since there are only IFrnl many values of h, we can evaluate the

majority quantifier in the definition by brute force. The only remaining problem

is to compute the line polynomials P~,h.

Recall from Lemma 5.66 that we can compute all line polynomials satisfying

Prob~[Px,h(t) = ~(x + th)] > 1/2(1 + ~-~)

in polynomial time. Since 1/2(1 + i-~) ~< 1/2(1 + 1/8) = 9/16, and since

Probh[Prob~[Px,h(t) ~ ~(x + th)] > 7/16] ~< 16/7. 555 < 1/40

follows from equation (5.40) and the fact that 5 < 1/6066, we conclude that for

every x ~ F m, we can compute P~,h for at least 39/40 of all h E F 'n.

On the other hand, we know from equation (5.38) that

Probh[Px,h(O) = g(x)] >/ 1 - 545 > 99/100.

This means that even if get wrong results for 1/40 of all h E F m by using the

algorithm of Lemma 5.66 for computing the P~,h(O), we will still receive the

correct result g(x) in the (overwhelming) majority of cases. 9

5.8 A Proof of Cook's

Theorem

Theorem 5.71 (Cook-Levin).

Let L be a language which is recognized by a

(nondeterministic) Turing machine in time O(nC). Then for each input size n,

we can construct in time O(n 2c) a 3-CNF formula r of size O(n 2c) such that

for all binary strings x of length n, the string x is in L iff the formula ~ is

satisfiable with partial assignment x.

Proof. To fix the notation, suppose that the machine jk4 consists of the set

of states Q = {qo,q+,q-,qu,q4,...,qk} -- containing the starting state q0,

the accepting state q+, and the rejecting state q_ -- the tape alphabet Z =

{o, 0, 1, a3, a4, 9 9 a~ }, and the transition relation 5 C Q • ~ x Q x Z x { - 1,0, + 1 },

where (q, a, q', a ~, m) E 5 is supposed to mean that if Jk4 is in state q while scan-

ning the tape symbol a at the current head position, it is allowed to change into

state q~, write a ~ into the current tape cell, and move the head according to m

(left, right, or no movement).

158 Chapter 5. Proving the PCP-Theorem

An instantaneous description of the configuration of the machine M must con-

tain the state of jk4, the position of the head, and the contents of the tape. We

assume without loss of generality that the machine .&4 is such that for every

input of size n there is a

t(n) 60(n c)

such that every computation of fi4 is of

length exactly

tin),

and that .&4 never tries to "run off the tape". In this case,

the machine can only visit the tape cells at positions 0,...,

t(n),

and thus the

size of a configuration is limited. Furthermore, a whole computation of ,s can

be represented by a sequence of

t(n)

configurations. The basic idea is now to en-

code this sequence of configurations into those propositional variables that may

occur in r in addition to the variables xt,..., x~ that will always be assigned

according to the input string x. For better readability, we give special names to

those additional variables, according to what they are supposed to encode (note

that the number of variables used is in

O(n2C)):

Qt: at time t, A,t is in state

qs ( 0 <<. t <~

t(n), 0 <~ s ~< k)

- Ht: at time t, the head scans a tape cell at position ~< r (0 ~ t,r ~<

t(n))

- Tt,,: at time t, the tape cell at position r contains

as (0 <~ t, r <<. t(n), 0 ~ s <~ l)

The formula r that we want to construct can be described as the conjunction of

the following statements (note that we will sometimes use the shortcuts P~ := H~

and Pr t := H t A H~t_l (0 < r ~< tin)) expressing that at time t, the head scans

exactly the cell at position r):

- At any time, the machine is in exactly one state:

O<~t<<.t(n) <<.s<<.k O<~sl<s2<<.k

At any time, the head position flags are consistent:

A -:(o,^ A A

O<<. t<<. t(n) O<~ t<~ t(n)

O~<r<t(n)

- At any time, every tape cell contains exactly one symbol:

A A V A

O<~t<<.t(n) O~<r~<t(n) I_O~<,~<t O<sl <s~ ~<l

At time t = 0, the machine is in state q0, scans the cell at position 0, and the

tape is inscribed as follows: for 0 ~< r < n, the cell at position r contains the

symbol 1 if xr+l is true and the symbol 0 otherwise, and all other tape cells

contain the symbol <>:

Q~176

[(xr+'VT~~176 A

T~~

o~<r<~

n<~ r<<.t(n)

5.8. A Proof of Cook's Theorem 159

At time t

t(n), the machine is in state q+:

Q'('~)

- For any t < t(n), the tape contains the same symbol in cell r at time t + 1 as

it contains at time t, unless the machine scans cell r at time t:

A A A

- For any t < t(n), if the head scans cell r, there is a transition (q, a, ql, a I, m) E (f

such that the machine is in state q at time t and in state ql at time t + 1, the

cell r contains a at time t and a ~ at time t + 1, and the head scans cell r + m

at time t + 1:

[~r t A rpt-]-I t+l ]

A A v V ^ ^ a+,,,)

O~t<t(n) O<~ r~t(n)

(qa,ab,qc,o'd,tn)E6

If we call the conjunction of the formulae given above r it should be obvious

that r is satisfiable with partial assignment x if and only if A4 accepts the input

string x. But note that r is no 3-CNF formula. This poses no problem though,

since in each of the formulae above, the part enclosed in [.- .] is an expression of

constant size (independent of n). Therefore, each of those parts can be replaced

by an equivalent 3-CNF formula of constant size, using some additional variables

(where the number of new variables is also a constant). Since the total number

of parts to be translated is

O(n2C),

we conclude that we can construct a 3-CNF

formula r with the following properties:

- For all x, r is satisfiable with partial assignment x iff r is satisfiable with

partial assignment x.

r uses

O(n 2c)

distinct variables (apart from Xl,..., xn).

r consists of

O(n 2c)

clauses of length 3.

To conclude the proof we note that the construction of r can obviously be done

in time linear in its length. 9

Exercises

Exercise 5.1. Let g : ~2 -'+ F2 be a linear function and let ~ : F~2 --~ F2 be a

function which is b-close to g.

160 Chapter 5. Proving the PCP-Theorem

a) Show that

Proby[g(x) # ~(x + y) - ~(y)] ~< 26.

Note that this generalizes the first part in the proof of Corollary 5.19.

b) Is Proby[g(x) = .~(x + y) - ~(y)] independent of x?

Exercise 5.2. In the proof of Theorem 5.39 we used three codewords A, B,

and C of codeword length 2 n, 2 n2, and 2 n3, respectively, from the linear func-

tion coding scheme. Recall that these codewords encode an assignment for the

variables in a given 3-CNF formula. In fact these codewords listed all values of

the sums given in equation (5.15), (5.16), and (5.17).

a) Show that codeword A can always be efficiently extracted from codeword B

or codeword C, and that codeword B can always be efficiently constructed

from codeword C.

b) Is it possible to construct an (n 3, 1)-restricted solution verifier, which queries

only bits from codeword C? If so, could the CONSISTENCY TEST be removed?

6. Parallel Repetition of MIP(2,1) Systems

Clemens GrSpl, Martin Skutella

6.1 Prologue

Two men standing trial for a joint crime try to convince a judge of their inno-

cence. Since the judge does not want to spend too much time on verifying their

joint alibi, he selects a pair of questions at random. Then each of the suspects

gets only one of the questions and gives an answer. Based on the coincidence of

the two answers, the judge decides on the guilt or innocence of the men.

The judge is convinced of the fairness of this procedure, because once the ques-

tioning starts the suspects can neither talk to each other as they are kept in

separate rooms nor anticipate the randomized questions he may ask them. If the

two guys are innocent an optimal strategy is to convince the judge by telling the

truth. However, if they have actually jointly committed the crime, their answers

will agree with probability at most ~, regardless of the strategy they use.

To reduce the error r the judge decides to repeat the random questioning k

times and to declare the two men innocent if all k pairs of answers coincide. This

obviously reduces the error to ck. So he randomly chooses k pairs of questions

and writes them on two lists, one for each of the accused.

The judge does not want to ask the questions one after another but, to make

things easier, hands out the two lists to the accused and asks them to write

down their answers. Of course he does not allow them to communicate with

each other while answering the questions. Waiting for the answers, he once more

thinks about the error probability. Can the two men benefit from knowing all

the questions in advance?

6.2 Introduction

In mathematical terms, the situation described in the prologue fits into the

context of two-prover one-round proof systems. In this chapter, we give an intro-

duction into basic definitions and characteristics of two-prover one-round proof

162 Chapter 6. Parallel Repetition of MIP(2,1) Systems

systems and the complexity class MIP(2, 1). (The letters MIP stand for multi-

prover interactive proof system). Yhrthermore, we illustrate the central ideas of

the proof of the Parallel Repetition Theorem. Our approach is mainly based on

the papers of Raz [Raz95, Raz97] and Feige [Fei95].

Multi-prover interactive proofs were introduced by Ben-Or, Goldwasser, Kilian,

and Wigderson in [BGKW88], motivated by the necessity to find new founda-

tions to the design of secure cryptography. The story told in our prologue is an

adaption of an example given in [BGKW88].

The chapter is organized as follows: We formally introduce MIP(2, 1) proof sys-

tems in Section 6.3. Then, in Section 6.4, we explain the problem of error re-

duction by parallel repetition of MIP(2,1) proof systems and state Raz' Parallel

Repetition Theorem. Its proof is based on the investigation of coordinate games,

which are introduced in Section 6.5. Sections 6.6 and 6.7 give an overview of the

proof of the Parallel Repetition Theorem.

6.3 Two-Prover One-Round Proof Systems

In a MIP(2, 1) proof system G, two computationally unbounded

provers P1, P2

try to convince a probabilistic polynomial time

verifier

that a certain input I

belongs to a pre-specified language L. The proof system has one round: Based

on I and a random string T, the verifier randomly generates a pair of questions

(x, y) from a pool X x Y which depends on the input I and sends x to prover

P1 and y to prover P2- The first prover responds by sending

u = u(x) E U

to the verifier, the second prover responds with

v = v(x) E V.

Here U and V

are pre-specified sets of possible answers to the questions in X resp. Y. Since

the verifier is polynomially bounded, only a polynomial number of bits can be

exchanged. In particular, the size of all possible questions and answers must be

polynomially bounded in the size of the input I.

The two provers know the input I and can agree upon a strategy (i. e., mappings

u : X --~ U and v : Y --4 V) in advance, but they are not allowed to communicate

about the particular random choice of questions the verifier actually asks. Based

on x, y, u, and v, the verifier decides whether to accept or reject the input I.

This is done by evaluating an

acceptance predicate Q : X x Y x U x V --~

{0,1}

where output 1 means acceptance and 0 rejection. We think of Q also as a

subset of Z := X • Y • U x V, i.e., Q =

{(x,y,u,v) E ZlQ(x,y,u,v )

= 1}.

The probability distribution of the question pairs (x, y) chosen from X • Y by

the verifier is denoted by #. The strategy of the verifier (i. e., his choice of # and

Q based on I) is called the

proof system,

while the strategy of the provers (i. e.,

their choice of u and v, based on the knowledge of I, /z and Q) is called the

protocol.

For fixed input I, a proof system G can be interpreted as a

game

for two players

(provers). Thus, ff we talk of G =

G(I)

as a game we implicitly consider a fixed