Transcript Chap7 - Extras Springer

The PCP theorem
Summary
- Proof structure
- Basic ingredients
- Arithmetization
- Properties of polynomials
- 3-SAT belongs to PCP[O(n3),O(1)]
Proof structure
3-SATPCP[log,polylog]
3-SATPCP[log,polylog]
composition lemma
3-SATPCP[log,polyloglog]
3-SATPCP[O(n3),O(1)]
composition lemma
PCP[log,O(1)]  NP
3-SATPCP[log,O(1)]
PCP is closed with
respect to polynomial-time Karp reducibility
Basic ingredients
- If two univariate polynomials of degree d coincides on
at least d+1 points, then they are the same
- aritmetization of Boolean formulas
- low-degree probabilistic test
- If a small fraction of the value table of a (low degree)
polynomial is wrong, it is still possible to compute the
right values (with high probability)
- self-correcting probabilistic procedure
Polynomial associated with a formula
- Let f be a CNF Boolean formula with three literals per
clause
- Polynomial p[ƒ] associated with f:
- p[u]=1-x[u] and p[not u]=x[u]
- p[l1 or l2 or l3]=p[l1]p[l2]p[l3]
- p[c1 and ... and cm] =  p[ci]
Truth-assignments and values
- If f(a1,...,an) is true, then p[f](a1,...,an)=0 where we
identify the value TRUE with 1 and the value FALSE
with 0
- Problem: If f(a1,...,an) is false, then p[f](a1,...,an) not
necessarily is 1
- Depends on the parity of the number of satisfied clauses
Example
- c1=u1 or not u3 or not u4,
c2=not u1 or u2 or not u4,
c3=u2 or u3 or not u4
- p[f](x1,x2,x3,x4)=
(1- x1)x3x4+x1(1-x2)x4+(1-x2)(1-x3)x4=
x3x4+x1x3x4+x1 x4-x1x2x4+x4-x3x4-x2x4+ x2x3x4=
x4 +x1 x4+x2x4+x1x2x4+x1x3x4+x2x3x4
- ƒ(0,0,0,1) is false and p[f](0,0,0,1)=1 but …
ƒ(1,0,0,1) is false and p[f](1,0,0,1)=0
Homogenization
- Lemma: Let v1,...,vm be a non-zero vector. Then
Prr  {0,1}m[ rivi=1]= 1/2
- Easy proof by induction on m
- For any r {0,1}m, define
p[f,r]=  rip[ci]
- Hence:
- if f(a1,...,an) is true, then, for any r {0,1}m, clearly
p[f,r](a1,...,an)=0
- if f(a1,...,an) is false, then from the lemma it follows that
Prr  {0,1}m [p[f,r](a1,...,an)=1]=1/2
Example
c1= u1 or not u3 or not u4, c2= not u1 or u2 or not u4, c3= u2 or u3 or not u4
r
p[f,r]
p[f,r](1,0,0,1)
000
0
0
001
x4+x2x4+x3x4+x2x3x4
1
010
x1x4+x1x2x4
1
011
x4+x1x4+x2x4+ x3x4+ x!x2x4+x2x3x4
0
100
x3x4+ x1x3x4
0
101
x4+x2x4+ x1x3x4+ x2x3x4
1
110
x1x4+x3x4+ x1x2x4+x1x3x4
1
111
x4+x1x4+ x2x4+x1x2x4+ x1x3x4+x2x3x4
0
Arithmetization and linearity
- Polynomials of degree 3
- Must be converted in set of linear functions
- Each polynomial of degree 3 is the sum of
-
constant term a
set of monomials (I1=set of variable indices)
set of binomials (I2=set of pair of variable indices)
set of trinomials (I3= set of triple of variable indices)
- Hence,
p(x1,...,xn)=a+  i  I1xi+ (i,j)  I2 xixj+  (i,j,k)  I3 xixjxk
Example
- p(x1,x2,x3,x4)=x4+x1x4+x2x4+x1x2x4+x1x3x4+x2x3x4
- In this case,
-
a=0
I1={4}
I2={(1,4),(2,4)}
I3={(1,2,4),(1,3,4),(2,3,4)}
Computing the polynomial value
- Let a1,...,an be an assignment to the polynomial
variables
- Then,
p(a1,...,an)= a+  i  I1ai+ (i,j)  I2 aiaj+  (i,j,k)  I3aiajak
- Define:
- A(x1,...,xn)=  aixi
- B(x1,...,xn2)=  aiajxi,j
- C(x1,...,xn3)=  aiajakxi,j,k
- The value of p can be computed as
p(a1,...,an)=a+A(Ch(I1))+B(Ch(I2))+C(Ch(I3))
Example
- p(x1, x2, x3, x4) = x4+x1x4+x2x4+x1x2x4+x1x3x4+x2x3x4
- Assignment: 1,0,0,1
- In this case:
-
Ch(I1) = 0,0,0,1 and A(Ch(I1)) = a4 = 1
B(Ch(I2)) = a1 a4 + a2 a4 = 1
C(Ch(I3)) = a1a2a4 + a1a3a4 + a2a3a4 = 0
p(1,0,0,1) = 0+1+1+0 = 0
3-SAT  PCP(n3,1)
formula of size n
verifier
n3 random bits
A(x) = ax
2n
B(y) = (a o a)y
2n2
C(z) = (a o a o a)z
2n3
Problems to be solved
- Verifying that A, B and C are (almost) linear and
consistent
- Must be done with n3 random bit and querying a constant
number of values of A, B and C
- Verifying that A, B and C encode a satisfying truth
assignment
- Must be done with n3 random bits and querying a constant
number of values of A, B and C in order to compute the
values of A, B and C corresponding to Ch(I1), Ch(I2), and
Ch(I3), respectively
Disadvantages
- Proof has exponential size because we have a
polynomial number of variables
- Requires a polynomial number of random bits
- Alternative: low degree polynomials with less
variables
- The degree depends on the length of the assignment
- That’s another story ...
Linear functions
- A function f from {0,1}m to {0,1} is linear if, for any x
and y {0,1}m, f(x+y)=f(x)+f(y)
- Given two functions f and g, their distance d(f,g) is the
fraction of input on which they differ
- f and g are -close if d(f,g)  
- Lemma: let  <1/3 and let g be a function from
{0,1}m to {0,1} such that
Prx,y  {0,1}m[g(x+y)  g(x)+g(y)]  /2.
Then there exists a linear function f that is -close to g
Proof
- f(x)=majority{g(x+y)-g(y)}
- f and g are -close
Otherwise, since Pry  {0,1}m[f(x)=g(x+y)-g(y)]  1/2, if
Prx  {0,1}m[f(x)g(x)] >  then Prx,y {0,1}m[g(x+y)-g(y)  g(x)] > /2
- f is linear
- For any a, Prx  {0,1}m[f(a)  g(a+x)-g(x)]   (see later)
– for any a and b, Prx  {0,1}m[f(a)+f(b)+g(x)  g(a+x)+f(b)]  
– for any a and b, Prx  {0,1}m[f(b)+g(a+x)  g(b+a+x)]  
– for any a and b, Prx {0,1}m[g(a+b+x)  f(a+b)+g(x)]  
- For any a and b, Prx  {0,1}m[f(a)+f(b)+g(x)=f(a+b)+g(x)]  1-3 >0
- Independent from x: ƒ is linear
Proof (continued)
- For any a, pa=Prx  {0,1}m[f(a)=g(a+x)-g(x)]  1-
- By hypothesis, Prx,y  {0,1}m[g(x+a+y)  g(x+a)+g(y)]  /2
- By hypothesis, Prx,y  {0,1}m[g(x+y+a)  g(x)+g(y+a)]  /2
- Hence, Prx,y  {0,1}m[g(x+a)+g(y)=g(x)+g(y+a)]  1-
- Prx,y  {0,1}m[g(x+a)+g(y)=g(x)+g(y+a)] =
Prx  {0,1}m[g(x+a)-g(x)=0] Pry  {0,1}m[g(y+a)+g(y)=0] +
Prx  {0,1}m[g(x+a)-g(x)=1] Pry  {0,1}m[g(y+a)+g(y)=1] =
(Prx  {0,1}m[g(x+a)-g(x)=0])2+(Prx  {0,1}m[g(x+a)-g(x)=1])2
- From definition of f, pa  1/2
- Since either f(a)=0 or f(a)=1, we finally have that
1-  pa2+(1- pa)2  pa(pa+(1- pa)) = pa
Linearity test
begin
randomly choose x,y {0,1}m ;
if g(x+y)=g(x)+g(y) then return YES
else return NO
end.
- If g is linear, then it answers YES with probability 1
- If g is not -close to a linear function, then it answers
NO with probability at least /2
- By iterating, we can make the error probability arbitrarily
small
Self-correcting procedure
begin
randomly y  {0,1}m ;
return SC-g(x)=g(x+y)-g(y)
end.
- Lemma: If g is -close to a linear function f, then
Pry  {0,1}m[SC-g(x)=f(x)]  1-2
Proof
- For any x {0,1}m, y and x+y are uniformly
distributed (even if they are not independent)
- Hence, for any x {0,1}m,
- Pry  {0,1}m[g(y)=f(y)]  1-
- Pry  {0,1}m[g(x+y)=f(x+y)]1-
- Since, for any x,y {0,1}m, f(x)=f(x+y)-f(y), we have
that, for any x {0,1}m,
Pry  {0,1}m[g(x+y)-g(x)=f(x)]  1-2
- Hence, Pry  {0,1}m[SC-g(x)=f(x)]  1-2
Consistency
- If ai, bi,j, and ci,j,k are the coefficients of linear
functions A, B, and C, then bi,j= ai aj and ci,j,k= ai aj ak
- Equivalently, for any x, x’ {0,1}n and for any
y{0,1}n2, A(x)A(x’)=B(x o x’) and A(x)B(y)=C(x o y)
where x o x’ is in {0,1}n2 and its (i-1)n+j-th element is
xix’j (similarly for x o y)
- Problem: x o x’ is not random and we cannot directly
use the -closeness
- Solution: use the self-correcting procedure
Consistency test
begin
randomly x,x’ {0,1}n ;
if SC-A(x)SC-A(x’)=SC-B(x o x’) then return YES
else return NO
end.
- Lemma: For any  < 1/24, there exists k such that if A
and B are not consistent, then with probability at least
1- at least one of k applications of the consistency
test answers NO
- Similar test and lemma for C
Proof
- Assume that coefficients of B and A are not consistent
- otherwise there is nothing to be proved
- Since, for any xx’ {0,1}n, Prr  {0,1}n[xr  x’r]=1/2,
then, for any xx’  {0,1}n2, Prr {0,1}n[xr  x’r]  1/2
- Coefficients of B form a matrix b
- Coefficients of A form a vector a, and a o a is a matrix
- Hence Prr,s {0,1}n[rT(a o a)s  rTbs]  1/4
- rT(a o a)s=A(r)A(s) and rTbs=B(r o s)
- By property of self-correcting test, it follows that
- Prr,s {0,1}n[SC-A(r)SC-A(s)  SC-B(r o s)]  1/4-6 > 0
Satisfiability test
begin
randomly r {0,1}m ;
compute a, I1, I2, and I3 of polynomial p[f,r];
if a+A(Ch(I1))+B(Ch(I2))+C(Ch(I3))=0 then return YES
else return NO
end.
- Lemma: If A,B, and C are -close to linear consistent
functions, then there exists k such that with
probability at least 1- at least one k applications of
the satisfiability test answers NO if the assignment
does not satisfy ƒ
- Teorem: 3-SAT is in PCP(n3,1)