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

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

5.5. Composing Verifiers and the PCP-Theorem 123

Proof.

We construct an extended verifier V as required in the definition of

(n, 1)-splittable. For every natural number k and for

n = kl

we let L n~ be equal

--?%

to C~ ~. Condition 1 then is immediate because given a string x of length l, we

can choose for w some code for

xO (k-1)~

in Cn.

Given an input (0n,zozl...Zk) we can assume that the zi axe indeed in C~ ~

because only in this situation V is required to work correctly. Thus each z~ is a

code for some binary string

xi = xi,1 ... xi,n

and if we let y = Yl ..-Yn be the

the j-th element of F~2 in lexicographical order, then the j-th bit of z~ is equal

t=l

Then for

X := Xl.1 ...Xl,lX2,1 ...X2,1 ... Xk~l...Xk,l

the linear function lx maps y - Yl ... yn to

n k I k

t=l i~1 t----1 i=1

By our construction the functions

and l~ 0 axe equal if[ the codewords Zl, 9 9

are a split representation of zo. In order to check the latter property V chooses

an argument y in ~ uniformly at random and checks whether both functions

agree at place y. Observe that according to equation (5.22 / in order to compute

l~ (y) it suffices to read one value each of l~ through l~. If the two functions are

not equal then by Lemma 5.16 they differ on half of their domain, and hence this

check fails with probability 1/2 in case the zl,..., zk are not a split representation

of z0, but succeeds always, otherwise. Then by repeating this check twice, while

rejecting if one of the iterations fails, we can amplify the probability for rejection

from 1/2 to 3/4.

By the preceding discussion V satisfies Conditions 3 and 4. Concerning Condi-

tion 2, it suffices to observe that for all strings zl,..., zk in Cn the function l~

corresponds to a codeword z0 in Cn where V accepts the input (O n,

ZoZl ... zk). I

Recall in connection with Proposition 5.47 that the polynomial coding scheme

was defined w.r.t, an admissible sequence <o, <a,.-. of orderings where admissi-

ble means that <n is a strict ordering on H~" such that the relevant operations

can be done in polynomial time.

Proposition

5.47.

For every natural number k, we can choose an admissible

sequence

<0,<1,...

such that thereby the polynomial coding scheme becomes

(log n, poly(log n))-splittable

into k parts.

Proof.

Recall that each of the decoding functions dec p~ depends on an order-

ing <n on Hn m" which we have not yet specified in detail. Now we will specify

124 Chapter 5. Proving the PCP-Theorem

an admissible sequence of orderings such that the polynomial coding scheme be-

comes (log n, poly(logn))-splittable. Here it suffices to specify the ordering <n

in detail for the cases where n is a multiple of k, while for all other n, as before

we might use arbitrary orderings such that the relevant operations can be done

in polynomial time.

We fix a natural number I and for

n = lk

we let p =

Pn, ra = ran, h = ha,

(~.poly and decn = dec p~ For all j in Fp we denote by Sj the

H = Hn , C,~ v,~ ,

slice of ~ defined by the equation xm = j. In order to define the strict ordering

<n on H m we specify a partition To,... ,T2n-1 of

Hm:

for each j ~ p - 1, the

set

contains the first l elements of

Sj N H m

w.r.t, the lexicographicai ordering

<lex on F~p, and the set Tp+j is the relative complement

(Sj n H m) \ Tj

of Tj in

Sjn H m. Then we specify <~ by requiring that two elements in some set

are

ordered according to the ordering <lex, and that for i < j all elements of Ti are

below all elements of Tj.

By our construction the first

elements of H m w.r.t. <~ are the first I elements

So N H m,

followed by the first I elements of

$1 n H m,

and so on. Recalling

that the decoding function decn maps a codeword w in Cn to the binary string

x = a(w, <n, n)

we obtain that by our choice of <n we have

x = xl ... Xk

where,

intuitively speaking, xj is decoded from the first l places of

Sjn H m.

For a function f on ~ we denote by

f[~.,,=j

the function on F~p -1 which is

obtained by firstly restricting f to the slice Sj and then identifying in the natural

way the elements of Sj and of ~-1. By definition the code C p~ contains all

m-variate polynomials over F n of degree at most

mh.

Now we let L p~ be the

set of all polynomials q in C p~ such that in addition the polynomial

q[~,,,=o

has degree at most

- k + 1. Recall that for every function g from H m to Fp

there is a polynomial

II II yg(hl,... (5.23)

hi - y

{hx ..... hm)EH "n

i=l yeH-{h~}

which by construction agrees with g on

H m

and which has degree at most

m(h -

1) and hence is in C p~ By inspection we obtain that the restriction of

the polynomial in (5.23) to the slice defined by

= 0 has degree at most

(m- 1)(h- 1)

= mh- (m + h-

1).

As a consequence for all values of n which are so large that m + h is greater

or equal to k, the polynomial is in L p~ and Condition 1 in Definition 5.44 is

satisfied. Here again we handle the finitely many remaining values of n by a

brute force approach.

It remains to construct an extended verifier V as required in the definition of

(r, q)-splittable coding scheme. On input (O n,

ZOZl... zk),

the verifier V inter-

prets z0 through zk as functions from ~ to F n, which we denote by

go,..., gk,

respectively. We can assume that the

are indeed in C p~ because only in this

5.5. Composing Verifiers and the PCP-Theorem 125

situation V is required to work correctly. Thus the

are polynomials of degree

at most

mh,

and then so are for 1 ~ j ~ k, the functions

golx,~=j-x and gj[x,,,=o.

The extended verifier V now tries to verify that for j = 1,..., k, the functions

9olx~=j-1

and

gj[x~=o are

the same. In order to do so for each such pair of

functions, V chooses an argument x in their common domain ~-1 uniformly

at random and checks whether both functions agree at x. By the theorem of

Schwartz stated as Theorem 5.22 two distinct (m - 1)-variate polynomials of

degree at most

over F v agree on at most a

mh/p

fraction of their domain.

According to equation (5.11)

mh/p

is less than 1/36 and hence in case the func-

tions in one of the pairs are not the same, V will accept with probability at most

1/36.

The extended verifier V obviously satisfies Condition 4 in Definition 5.44. Con-

cerning Condition 3, observe that in case the codewords Zl,...,

Zk axe

not a split

representation of some codeword z0, then by definition deck(z0) differs from the

string decn(Zl)[a..l],..., decn(zk)[l:t]. But by choice of the ordering <n this just

means that for some j the functions

gol~,,=j-a and gj}~=o

disagree, and con-

sequently V rejects the input (0 n,

ZOZl... Zk).

Concerning Condition 2, we assume that codewords Zl,..., zk in L p~ are given

which correspond to polynomials ql,-..,

qk,

respectively. Then by definition of

L p~ the functions

qjlx,,,=o are

polynomials of degree at most

- k + 1 and

consequently the function q0 defined by

k--1

q0( l, Z II

' j -- i " [qj+llx,~=0 (Xl,...,

Xm--i)]

j=o ie(o ..... k-1}-{j}

is a m-variate polynomial over F v of degree at most

mh,

that is, qo corresponds

to a codeword Zo in C p~ This finishes our proof, because by construction, the

codewords

zl ..., zk

are a split representation of z0 and hence V accepts the

input

( On, zo... Zk).

More precisely, in order to show that the Zl,...,

are a

split representation of Zo observe that for the lexicographical ordering <lex we

have for all al,...

,am-l,bl,... ,bm-l,i,j

in Fp

(al,...,am-l,i)<lex(bl,...,bm-l,i)

if[

(al,...,am-l,j)<lex(bl,...,bm-l,j).

As a consequence and according to the definition of the ordering <, in terms of

the lexicographical ordering the restrictions of <n to the slices $1,..., Sk order

these slices in essentially the same way. Thus for 1 ~< i ~ k, we will use essentially

identical orderings while decoding the length l strings dec(z0)[(i_l)l+l:i~] and

dec(zi)[1.t] from the restriction of q to slice Si-a and from the restriction of qi to

slice So, "respectively. 9

5.5.2 Decision Formulae and Composition of Extended Verifiers

In connection with Definition 5.48 recall our convention according to which an

assignment for a 3-CNF formula of length n has length n, too.

126 Chapter 5. Proving the PCP-Theorem

Definition 5.48. Let ~ be a 3-CNF formula of length n.

A partial assignment for ~ is a binary string of length less or equal to n. Given

a partial assignment a for ~o of length k, a complementary assignment for ~ and

a is a binary string of length n - k.

The formula ~ is satisfiable with partial assignment a iff there is some com-

plementary assignment b for qo and a such that ab is a satisfying assignment

for ~.

In the sequel we wilt use the following variant of Cook's theorem, for a proof see

Section 5.8.

Theorem 5.71 (Cook-Levin). Let L be a language which is recognized by a

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

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

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

satisfiable with partial assignment x.

We will show in Lemma 5.51 that a pair of a verifier and a solution verifier which

satisfy certain technical conditions can be composed to yield a more efficient

verifier. Here the key idea is to transform, for a given verifier I/1, the evaluation

of the bits read from the proof into a 3-CNF formula ~, then using the solution

verifier V2 for checking the satisfiability of the formula qo. If we assume that for

some input x and some random string 7- the answers to 1/1 queries are given

as a binary string a, then the evaluation of a amounts to a computation with

input (x, T, a). Here we can assume due to V1 being polynomially time bounded

that the running time of this computation, as well as the length of T and a

are polynomially bounded in n. Thus by Cook's theorem there is a formula qa

of size polynomial in n, such that ~o is satisfiable with partial assignment XTa

iff the evaluation of a results in acceptance. However even if the verifier V1 is

(r, q)-restricted for some sublinear function q, in general the formula obtained

according to Cook's theorem will have size polynomial in n. In this situation in

general we obtain formulae which are larger than the input formulae of V1 and

consequently the composed verifier might be less efficient than the verifier V~

we have started with. So we are led to the consideration of verifiers where the

behavior for given x and T Can be described by formulae of small size.

Definition 5.49. Let V be an (r, q)-restricted verifier, and let x and r be binary

strings of length n and r(n), respectively. Let il < ... < it be the positions of

the proof which are queried by V while working on x and T, and for a proof 7r of

length at least it, let a(x, T, 7r) = 7ril ... 7ri~ contain the corresponding bits of r.

A decision formula for V, x, and T is a 3-CNF formula qa such that for every

proof rr of suitable length, V accepts (x, 7r) on random string Tiff the formula

is satisfiable with partial assignment a(x, v, 7r).

5.5. Composing Verifiers and the PCP-Theorem 127

(r,

q)-restricted verifier V has

feasible decision

if] given strings x and ~" of

length n and r(n), respectively, we can compute in time polynomial in n a deci-

sion formula for V, x and T Of size at most polynomial in q(n).

Observe in connection with Definition 5.49 that the decision formula depends on

the verifier V, the argument x, and the random string r, but not on the proof

7r. Observe further that during the evaluation of a decision formula q0 we will

use the bits read from the proof plus some complementary assignment which

specifies values for some auxiliary variables. However we need not refer to x or

T, that is, intuitively speaking, the values of x and T are hardcoded into the

decision formula.

Proposition

5.50.

The constant

(n a, 1)-restricted

solution verifier from Theo-

rem 5.39 has feasible decision.

The constant

(log n, poly(log n))-restricted

solution verifier from Theorem 5.43

has feasible decision.

Proof.

Concerning the first assertion about the (n 3, 1)-restricted extended ver-

ifier observe that an (r(n), 1)-restricted verifier always has feasible decision. In

order to obtain a decision formula as desired we simply simulate the verifier for

all possible assignments of answers to the constantly many queries to the proof

in order to compute the Boolean function which maps such an assignment a to

0 in case V rejects, and to 1, otherwise. Given the truth table of this Boolean

function we construct a formula qo0 in conjunctive normal form such that the

Boolean function under consideration maps a to 1 iff a is a satisfying assignment

for qo0. Finally we employ standard techniques in order to transform qo0 into a

3-CNF formula ~ such that an assignment a satisfies qo0 iff qo is satisfiable with

partial assignment a.

Concerning the second assertion let V be the (log n, poly(log n))-restricted ver-

ifier from Theorem 5.43. For concreteness we assume that the number of bits

V reads from its proof is bounded by a function q where

q(n)

is in poly(log n).

Inspection of the construction of V reveals that for an input x of length n, a cor-

responding random string ~-, and a proof 7r, the evaluation of the answer string

a(x, T, 7r)

of length at most

q(n)

can be viewed as a computation with running

time in poly(q(n)). Here this computation requires as input, besides

a(x, T, 7r),

parameters such as logn or Pn of size in poly(logn), but not the whole string

x. If we denote the concatenation of these additional parameters as y, the input

to the computation can be written as

a(x,T, Tr)y

and has length in poly(logn).

By Cook's theorem we obtain a 3-CNF formula qo0 of size in poly(logn) such

that ~o is satisfiable with partial assignment

a(x, T, 7r)y

iff V accepts (x, ~r) on

random string ~. In order to obtain a decision formula as required it suffices to

hardcode y into ~0 without destroying 3-CNF. In order to do so we let xj be the

variable which corresponds to the first bit of y and we replace each variable for

which we want to hardcode an assignment 0, respectively 1, by ~-~j, respectively

128 Chapter 5. Proving the PCP-Theorem

by xj. Finally we add a clause

(xj Vxj

Vxj) in order to ensure that in a satisfying

assignment the variable xj is assigned the value 1. 9

Lemma 5.51 (Composition Lemma).

Let Vz be an (rl,ql)-restricted con-

stant verifier with feasible decision for some language L where for all f in

poly(qz)

and for all but finitely many n holds f(n) <<. n.

For every natural number k >/1 let there be an

(r2,

q2)-restricted solution verifier

V2 with a coding scheme which is (r2,q2)-robust and is (r2,q2)-splittable into k

parts.

Then there is an

(rl (n) -I- r2 (q~ (n)), q2 (q~ (n)))-restricted

verifier V3

(5.24)

for L where q~ is a function in

poly(ql).

In case V2 is constant, has feasible decision, or satisfies both of these properties,

respectively, then we can arrange that the same holds for V3.

Observe that the bounds in equation (5.24) reflect that the composite verifier

V3 first uses rl random bits in order to simulate V1 on an input of size n and

to compute a decision formula ~ of size at(n), and then consumes

O(r2(qll(n)))

random bits and reads

O(q2(q~(n)))

bits of the proof while simulating V2 on ~.

Proof.

In the sequel we construct a verifier V3 as required in the lemma and we

leave it to the reader to check that V3 satisfies the resource bounds required.

On input x of length n, the verifier V3 basically proceeds as follows.

Step 1. II3

simulates V1 on input x and a random string ~- of suitable length in

order to compute the positions which V1 reads from its proof.

Step 2. V3

computes a decision formula ~r for 111, x, and T and assumes that the

proof of V3 contains an appropriate encoding 7r~ which essentially contains an

assignment for ~r. (Recall that an assignment for the decision formula qo r con-

sist of a partial and a complementary assignment where the partial assignment

corresponds to the positions computed during Step 1.)

Step 3.

In order to ensure that the partial assignments given by the encodings

~r~ are consistent for the various values of r, the verifier V3 assumes that some

part of its proof contains a proof 7r y' for V1. Here for technical reasons the proof

7r v' is not given directly, but is first partitioned into blocks of appropriate size.

Then we choose a solution verifier V2 with coding scheme C as in the assumption

of the composition lemma and encode each block according to C. By means of

this encoding and by robustness and the splitting property of C, the verifier V3

can check within its resource bounds whether the partial assignment given by

7r~ agrees with the bits read from 7r vl .

5.5. Composing Verifiers and the PCP-Theorem 129

Step ~.

Related to the tests in Step 3, in case 7r~ encodes a string y then y is not

an assignment for ~o 7, however the values for the variables of ~o 7 are given by

a proper subset of the bits of y. Accordingly V3 transforms ~7 into a basically

equivalent formula r such that (r is an appropriate input for the solution

verifier V2.

Step 5. V3

simulates 1/2 on input (r162

Here V3 rejects immediately in case one of the tests in Step 3 fails, and in case

Step 5 is reached, then V3 accepts iff the simulation of V2 results in acceptance.

With the construction of V3, Steps 1, 2, and 5 are straightforward, so it suffices

to consider Steps 3 and 4. First we consider the encoding of a given proof ~r yl

for V1 related to Step 3. We partition lr V~ into blocks of equal length

b(n).

Here,

for the moment, b is an arbitrary function in poly(ql(n)) which is computable in

polynomial time and which is larger than both the size of the decision formula

~7 and the number of queries asked by V1. While simulating V1 we will query

positions in at most O(1) such blocks because, firstly, V1 is constant and hence

queries only (9(1) many segments of its proof and, secondly, by construction each

such segment is contained in two successive blocks. Thus there is a constant k

which is independent of x such that V1 queries positions in exactly k - 1 blocks.

Next we choose some (r2, q2)-restricted verifier V~ with a coding scheme g which

is (r2, q2)-robust and (r2, q2)-splittable into k parts. We let

l = b(n)

and let

Lkl

be a subset of the

kl-th

code C~I of g as in the definition of splittable coding

scheme. Then we replace each block of r wl by a code z in

Lkt

for some string

y of length

such that the block under consideration is equal to the length l

prefix of y.

Further we assume that for every % the proof of V3 contains at a designated

position some code z& = z~ in Lkl for some block of length

b(n).

Here we view

z& as code for a string y which contains as a prefix a complementary assignment

for ~7. Consequently there is an assignment for the formula ~r which is given in

the form of codewords Zl,... , Zk_l, z k in Lk~. But if we want to use the solution

verifier V~ in order to check whether this assignment satisfies ~7, it is necessary

that the assignment is given as a single code. So we assume that for every 7 the

proof of V3 contains a code ~r~ in Ckl. By choice of L and by assumption on the

coding scheme g, the extended verifier V3 can now use an

(r2

(kl),

(k/))-restricted extended verifier V (5.25)

in order to test probabilistically for some suitable 5 < 1/4 whether the alleged

codes

7r~, zy,..., Zk are

5-close to Ckl, and if so, whether the nearest codewords

of the zj are a split representation of the nearest codeword of ~r~. Observe that

by definition of splittable coding scheme for all choices of the k codes in L there

is always at least one codeword z0 in C such that the corresponding test accepts

with probability t in case we let ~r~ be equal to z0. Observe further that by

assumption on ql for almost all n we have

~< n and that by convention the

130 Chapter 5. Proving the PCP-Theorem

resource bounds r2 and q2 are non-decreasing. Thus for almost all n, the values

r2(kl)

and

q2(kl) axe

less or equal to r2(n) and q2(n), respectively. As usual we

handle the finitely many remaining values of n by a brute force approach.

Now Step 5 basically amounts to simulating the solution verifier V2 on the for-

mula ~o r and the assignment as given by lr~. However 7rg is not a code for an

assignment of 7r~, but a code for a string of length

which among its bits

con-

tains

such an assignment. Thus we have to alter the formula ~o r into a formula

r such that the new formula together with 7r~ provides a reasonable input for

112. In connection with this modification, recall the representation for 3-CNF

formulae we have agreed on in Section 5.4.1. Now, the modification of ~o ~ has

to take care of the two following problems. First, in case V1 queries positions

jl < ... < jr,

of its proof, then specifying a single variable of ~ requires [log t]

bits. Here t > t ~ is the number of variables in the formula ~o ~ and thus also

the length of its binary representation. With the new formula tr we will have

to specify the corresponding t positions within an assignment of length

and

hence it requires [log

kl]

bits to specify a single variable of r Second, according

to the convention in Remark 5.32, in case we want to present to V2 an assign-

ment of length

kl,

then also the corresponding input formula must have length

kl.

In order to handle these two problems we proceed as follows. Firstly, we re-

place in ~o r the variable identifiers by length [log

kl]

variable identifiers w.r.t.

the assignment encoded by ~r~. Secondly, we patch the formula thus obtained by

dummy clauses in order to obtain a formula of length

kl.

In order to make this

construction go through we ensure that

3([log

kl] +

1) divides

kl,

(5.26)

t kl

3([logt] + 1) < 3([logk/] + 1)" (5.27)

Then by equation (5.27) the replacement of the formula identifiers in the length

n formula ~o ~ results in an intermediate formula of length less than

kl.

Further we

can patch this intermediate formula with dummy clauses in order to obtain the

length

formula r according to equation (5.26) because by our representation

of 3-CNF formulae the intermediate, as well as the patched formula consists of a

prefix and several clauses which each have length 3([log

kl]

+1). Observe that it is

always possible to satisfy equations (5.26) and (5.27) by choosing an appropriate

value for

l = b(n)

O(poly(ql(n))),

and that this choice is compatible with the

previous conditions on b.

Concerning the simulation of V2 on the pair (r r~) observe that tr has length

in poly(ql(n)) and thus the simulation queries

O(q2(poly(ql(n))))

places of

the proof and uses a random string T2 of length in

O(r2(poly(ql

(n)))). During

the simulation of V2 we use for each random string T a different part 7r~ of the

proof of Vz as proof ~rl of V2. Thus in particular in case ~o ~ is satisfiable we can

choose 7r{ such that the simulation results in acceptance with probability 1, and

in case to ~ is not satisfiable then for all choices of or{ the simulation results in

acceptance with probability at most 1/4. Here the probabilities are w.r.t, r2.

5.5. Composing Verifiers and the PCP-Theorem 131

In order to verify that Va recognizes L it suffices to show that for every fixed

f~ > 1 and for all inputs x we can achieve that Claims 1 and 2 are satisfied.

Claim 1.

If 1/1 accepts (x, #) for some proof ~, then there is a proof v such that

I/3 accepts (x, lr).

Claim 2.

Given a proof r for 1/3 we can construct a proof ~ for V1 such that

for every rational E > 0, if V3 rejects (x, ~r) with probability at most c then V1

rejects (x, ~) with probability at most f~.

We show that Claims 1 and 2 together imply that V3 recognizes L. For every x

in L, the verifier V1 accepts x for some proof, and then so does V3 according to

Claim 1. Conversely, let x be not in L and assume for a contradiction that Va

does not reject x, that is, assume that there is a proof ~r where V3 rejects (x, ~r)

with probability at most 3/4. By Remark 5.3 and because V1 recognizes L we

can assume that for every proof ~, the verifier 111 rejects (x, ~) with probability

at least 4/5. We obtain a contradiction by choosing j3 > 1 so small that (3/4)j3

is less than 4/5 because according to Claim 2 then there is a proof ~ where V1

rejects (x, ~) with probability at most (3/4)f~ < 4/5.

Claim 1 is more or less immediate from the construction of V3. Concerning

Claim 2, we fix some ~ > 1 and we let ~r be a proof for V3. We assume that

~r contains an encoding of a proof Ir yl for V1 which is given as the concatena-

tion zl ... z~ of alleged codes z i in Lk~ as above. In order to obtain a proof

as required essentially we want to let ~ --

d(yl).., d(yt)

where

d(yj)

is some

arbitrary string of length l in case yj is not 1/4-close to

Ckl,

and otherwise,

d(yj)

is the length l prefix of the binary string encoded by the nearest codeword

for z i. However, related to the proof of Theorem 5.54, we use a slightly more

liberal definition of the function d. Recall that in (5.25) we have already fixed a

verifier V which for some suitable 5 < 1/4 rejects an input

(Okl,y)

in case y is

not 5-close to Ck~. We now assume that we are given a function d where

d(y)

the length l prefix of the binary string encoded by the nearest codeword for y

in case (0 kl, y) is not rejected by V, and

d(y)

is some arbitrary string of length

l, otherwise. Then, similarly as above, we let

~r = d(yl).., d(yt).

Observe that

there is always some function d as required, because in case V does not reject

(Okt,y),

then y is 5-close to Ckl. (In the proof of Theorem 5.54, we will show

that for the polynomial coding scheme the function d can in fact be chosen to

be computable in time polynomial in the length of the input y.)

In order to show Claim 2, by contraposition it is sufficient to show for every

> 0, that in case V1 rejects ~ with probability greater than f~, then V3 rejects

~r with probability greater than c. Now consider a random string T such that

V1 rejects (x, #) on T. We can assume that in case, firstly, ~ or one of the

strings z i which correspond to the yj which are accessed by V1 on x and T is

rejected by ~z or, secondly, the nearest codewords of these z i are not a split

representation of r~, then one of the tests performed by V3 during Step 3 fails

with probability greater than 1//3. But otherwise, firstly, the subverifier V will

132 Chapter 5. Proving the PCP-Theorem

not reject the zj, that is, by definition of d, the first I bits of

d(zj)

in fact relate to

zj and, secondly, the assignment given by ~r~, intuitively speaking, agrees with

the strings

d(zj).

Consequently and by assumption on % in this case we can

assume that the simulation of V2 in Step 3 results in rejection with probability

greater than 1//3. Thus for every random string 7 of V1 such that V1 rejects

(x, #) on T, the corresponding simulation by V3 on (x, r) will result in rejection

with conditional probability of at least 1//3. By summing up these conditional

probabilities over all such % we obtain that V3 rejects (x, It) with probability

greater than (/3e)1//3 = e. 9

5.5.3 The PeP-Theorem

We will obtain the PCP-Theorem as an easy consequence of Theorem 5.52.

Theorem 5.52.

There is a

(logn,

1)-restricted verifier for

3SAT.

Proof.

Consider the (n 3, 1)-restricted solution verifier Vnn from Theorem 5.39

and the (log n, poly(logn))-restricted solution verifier Vpoly from Theorem 5.43.

Both solution verifiers are constant and by Remark 5.4 they can be viewed

as verifiers which accept the language 3SAT. As a consequence both of them

can play the role of the Verifier V1 in the composition lemma with L equal to

3SAT. On the other hand they can also play the role of V2 due to the properties

of their coding schemes and because both have feasible decision according to

Proposition 5.50. In this connection, recall that the linear function coding scheme

is (n, 1)-splittable and that for every natural number k we can arrange that the

polynomial coding scheme becomes (log n, poly(log n))-splittable into k parts.

Applying Lemma 5.51 with VI and V2 both equal to Vpoly yields a constant

(log n + log log n, poly(log log n))-restricted verifier V'

which accepts the language 3SAT. Applying Lemma 5.51 again with V1 equal to

V ~ and V2 equal to Vnn then yields a

(log n + poly(log log n), 1)-restricted verifier V

which accepts the language 3SAT. The verifier V is in fact (log n, 1)-restricted

because poly(log log n) is contained in O(log n). Observe that in the above rea-

soning we have used several times that constant factors and exponents become

absorbed due to equations such as

O(log(poly(log n))) = O(loglog n).

Theorem 5.53 (PCP-Theorem).

The class .AfT ~ is equal to

PCP(log n, 1).