Data checking and verification
Randomization and coding
A guide to PCP, an approach towards
classification of NP problems

P versus NP
Have you heard about P vs NP problem?
• Millenium prize problems by Cray institutehttp://www.claymath.org/millennium/• P versus NP is not only million dollar problem,
Its value is trillion dollars.

Class P and class NP• Consider a computational problem M of input size n• P: class of polynomial time solvable problems in usualmodel of computation– M is in P if there is an algorithm to solve it in polynomialtime• Example: Sorting, Searching, Graph connectivity• Shortest path, text pattern matching• NP: class of polynomial time solvable problems in
nondeterministic model of computation– M is in NP if there is a nondeterministic algorithm to solve
it in polynomial time (difficult to understand, isn’t it?)• P is a subclass of NP

More intuitive description• Verification is often easier than solution– Solving an equation is more difficult than verification• NP: If we know the solution, we can show it suchthat verification is done in polynomial time
– 1: Hamilton path
– 2: Graph coloring,– 3: Does this SUDOK puzzle have a solution?

• A problem (probably) not in NP– 1: Will black win this Chess game ?
– 2: SOKOBAN game
– 3: #3SAT (number 3SAT)• Intuitively, a problem that we are convinced withcorrectness of solution easily if it is shown.

NP and co-NP• It is notable that negation of an NP problem
might not be in NP– Is a given graph G is colored by using k colors?
• We give the actual coloring to veryfy. Thus NP problem– Is a given graph G has no coloring with k colors?
• If so, how to convince it?

• Co-NP problem: negation of an NP problem• It is believed NP and co-NP are different• It might be true that NP ∩ coNP = P

P vs NP
• Is it true that verification is easier than solution ?
– Consider an equation f(x) = x5 - 3x4 +3x2 + 4 = 0– Ask “ is this equation has an integer solution less than n (say,n=100)”.
– Verification: f(2) = 32-48+12+4 = 0– Solution???

• P vs NP: Is there any problem where verification is easy (Ptime) but solution is difficult (not in P-time)?
• Philosophical question– Is it easy to learn than solve by yourself?
• Is it true that a difficult problem remains to be difficult even if you aresuggested a solution (you must make sure it is true).

– In real life, we must solve many NP problems(or even moredifficult problems). Human can solve them by training (likeSUDOK) for most of instances. Why??

Implication of P=NP
• If P=NP, we can solve many problems– Many-body problem in physics– Protein folding problem in biology– Optimal scheduling in manufacturing– Optimal traffic control– Many problems in computational chemistry• If P=NP, we have serious inconvenience– Current cryptology assumes P is not NP– Information security system is destroyed• Most of researchers believes P is not NP, and the above
situation only occurs in Scientific Fiction– But no one knows the truth• The biggest mathematical challenge in 21st century

Several approaches towards P vs NP
http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf
Lance Fortnow’s article• NP- complete theory (S.Cook and R.Karp)– Almost all NP problems are either in P or NP-complete( one of
the most difficult problems in NP)• Circuit complexity– Show NP needs exponential size of circuits• Algebraic/group theoretic method– Relation to generalized Riemann hypothesis (Mulmuley)• From mathematical logic• Relation to randomness• Interactive Proof and Checkable Proof

Textbooks/papers• Randomized Algorithms (Motwani-Raghavan)• Efficient Checking of Polynomials and Proofs
and the Hardness of Approximation Problems(M. Sudan, ACM Distinguished Thesis, 1995)• Proof Verification and the Hardness ofApproximation Problems (S. Arora, C. Lund, R.
Motwani, M. Sudan, M. Szegedy), J. ACM, Vol
45(3), 1998, pp. 501-555

Rajeev Motwani (from wikipedia)
•

•

•
•

•

Motwani joined Stanford soon after U.C. Berkeley. Motwani was one of the co-authors (with Larry
Page and Sergey Brin, and Terry Winograd) of an influential early paper on the PageRank algorithm,
the basis for Google's search techniques. He also co-authored another seminal search paper What
Can You Do With A Web In Your Pocket with those same authors.[3]He was also an author of two widely-used theoretical computer science textbooks, Randomized
Algorithms (Cambridge University Press 1995, ISBN 978-0521474658, with Prabhakar Raghavan)
and Introduction to Automata Theory, Languages, and Computation (2nd ed., Addison-Wesley, 2000,
with John Hopcroft and Jeffrey Ullman).
Prior to his involvement with Google, Motwani founded the Mining Data at Stanford project (MIDAS),an umbrella organization for several groups looking into new and innovative data management
concepts. His research included data privacy, web search, robotics, and computational drug design.
He was an avid angel investor and had funded a number of successful startups to emerge from
Stanford. He sat on the boards of Google, Kaboodle, Mimosa Systems, Adchemy, Baynote, Vuclip,
NeoPath Networks (acquired by Cisco Systems in 2007), Tapulous and Stanford Student
Enterprises among others. He was also active in the Business Association of Stanford Entrepeneurial
Students (BASES).[4][5][6]He was a winner of the Gödel Prize in 2001 for his work on the PCP theorem and its applications
to hardness of approximation.[7][8]Verification
Algebraic methods to verify
information

Verification in real life
• Given two data A and B, we want to verify A=B– We want to do it without reading A and B explicitly• If A and B are “persons”– How we can “read” data of persons completely?
• Impossible!

– Name, blood type, color of hair/eye,……
– ID numbers, secret keywords,– Finger print, DNA identification• If A and B are twins………

Fingerprinting• We recall the data checking problem we
discussed some weeks ago– Given a set of n data {a(1),a(2),…,a(n)}, and wesuspect one (or more) data is modified.
– How should we check efficiently?
• The sum of all data
• Use hash function, and sum of h(a(i))– This is an example of “fingerprint”

Fingerprinting for matrix multiplication• Consider a prime p• Given n by n matrices A, B, and C, we want toverify AB = C mod p– Computation in the field GF(p) (or Zp )• Can you do it in O(n2) time?

Pattern matching via verification• Given a text T of length n (bit string)• For each query pattern P of length m, we want tofind location of occurrence of P in T
• Both m and n are long (say, m = 100000, n =10000000)• KMP algorithm, BM algorithm: optimal O(n+m),
but not much practical• Can we apply verification idea?
• SOLUTION on blackboard (you can find it inMotwani-Raghavan book)Verifying an identity• X = (x1,x2,..,xd)• We want to verify a polynomial identity
F1(X)=F2(X) of degree nVerifying an identity• X = (x1,x2,..,xd)• We want to verify a polynomial identity F1(X)=F2(X) ofdegree n– Or more cruel identities for which you cannot probably
understand its mathematical proof (like the one below)

Prover and Proof
Prover is stronger than proof, since
we can ask questions instead ofreading the proof

Interactive Proof• Suppose that you can ask a god (or a powerfulsupercomputer ) to solve a problem• If the answer is “YES” (or “NO”), do you believe it blindly?
– In real life, we blindly believe the weather forecast which acomputer software reports– In ancient Greek, people believed “oracle of Apollo”.
– If you are given a program/software , how you believe it?
• Or how you write a program convincing others its correctness?

– Even in a university, most of students (and professors) believe
Wikipedia blindly ????

• We want to request a proof or an evidence.
– For a NP problem, we can ask for a proof if the answer is Yes– But if answer is NO, can we do something?

Graph non-isomorphism• You have two graphs G=(V,E) and G’=(V’,E’)• You suspect that they are isomorphic– There is a one-to-one map f of vertices of G such that(x,y) is an edge of E if and only if (f(x), f(y)) is in E’• You ask your professor who says he is always honest
and can solve the problem for any pair of graphs.
– If he answers “yes”, you can ask him to show the map f.
– Can you believe him if he says “NO”?

An interactive proof• You (verifier) have G and G’, and ask yourprofessor (prover) whether G=G’
• Professor answers “NO”, but you suspect that hetells a lie.
• You ask some more questions to the professor toreveal whether he is honest– You can flip a coin, and the random choice is notknown to the professor• SOLUTION on the blackboard (you can easily find
it in several textbooks)

How IP is strong• I will show that #3SAT is solved by using
interactive proof system– #3SAT: Find the number of solutions of a logicalequation (given in a certain form)• This implies #P is in IP, and co-NP is in IP– do not worry about such terminology• A. Shamir showed that IP = PSPACE– PSPACE is considered to be larger than NP– 2 player’s game like GO and Chess are in PSPACE

3SAT and #3SAT• 3SAT: Is a logic equation F(X(1),X(2),..,X(n)) = 1 in 3CNF formula has a solution?
• #3SAT: How many solutions F(X)=1 has?
• 3SAT is an NP-complete problem– Any NP problem can be transformed into a 3SAT
problem in polynomial time.
– If 3SAT is in P, then NP = P– To show 3SAT is NP-complete• SAT is NP-complete (Cook’s theorem)• SAT is transformed into 3SAT• #3SAT is more difficult (called #P complete
problem)–Toda’s theory (1989, Goedel award)

From SAT to 3SAT• Show that SAT is P-time soluble if 3SAT is.
• Given an instance (U,C) of SAT, we show atransformation of it into (U’, C’) of 3SAT
– U: set of variables, C:set of clauses• U={X(1),X(2),..,X(n)}, C={C(1),C(2),..,C(m)}• c( j )  l1, j  l2, j  ...  lk , j  {l1, j , l2, j ,.., lk , j }• For each clause C of C of length k, we consider
k-3 new variables, and transform it into a setof clauses each of which has length 3• Thus, we transform into 3SAT input with at
most nm variables and mn clauses

Transforming a clause• C = {z(1) , z(2) ,.., z(k)}– z(i) is either X(i) or its negation• We define new variables y(1),y(2), y(k-3)– These variables are only used to transform C• The clause c is transformed into
– S(c) = {{z(1),z(2),y(1)}, {y(1) , z(3), y(2)}, {y(2),z(4),y(3)},..,{y(k-3),z(k-1),z(k)}}– c is satisfied if and only if all clauses in S(c) aresatisfiedIntaractive proof for #3SAT
Step 1: Arithmetization• F(X(1),X(2),…X(n)) = a logical function in 3CNF
• C(i) = L(i,1) ∨L(i,2)∨L(i,3)• F = C(1) ∧C(2)∧..∧C(m)• Transfrom F into a real function f• For each literal L = L(i , j), we define l(i,j) = 1-x(k)if L=X(k) and l(i,j) = x(k) if L=X(k)• c(i) = 1 - l(i,1)l(i,2)l(i,3)• Observation: C(i) is satisfied if and only if c(i)=1• F = c(1)c(2)…c(m): a polynomial in x(1),..x(n)Number of solutions• If F= (X(1) ∨X(2)∨ X(3))∧（X(1)∨X(3)∨X(4)),• f= (1-(1-x(1))(1-x(2))x(3)) (1-x(1)x(3)(1-x(4)))• Number of solutions of F=1 is 7 + 5 = 12.
1
1
1• Define # f    ...  f ( x(1), x(2),.., x(n))
x (1) 0 x ( 2 ) 0x ( n ) 0

• Then, # of solutions of F=1 equals #f• Computation is difficult, but your professor who says
he can compute #f for any f.
• Ask the professor “What is #f”, and he answers that“its value is s ”. (say, “its value is 2487000”)• Verify whether he tells a truth.

Our model
1

1

1• Define # f    ...  f ( x(1), x(2),.., x(n))
x (1) 0 x ( 2 ) 0 x ( n ) 0
• Computation is difficult, but your professor whosays he can compute #f for any f.
• Ask the professor “What is #f”, and he answers
that “its value is s ”. (say, “its value is 2487000”)• Moreover, the professor will answer to any
computation request.
– Thus, you can give any modified question.

Key idea
1

#f 

1

1

 ...  f ( x(1), x(2),.., x(n))

x (1) 0 x ( 2 ) 0x ( n ) 01f i ( x(1), x(2),.., x(i))  

1

 ...  f ( x(1), x(2),.., x(n))

x ( i 1) 0 x ( i  2 ) 0

Lemma
•f0 = #f
• f ( x(1))  1
111x ( n ) 01

  ...  f ( x(1), x(2),.., x(n))

x ( 2 )  0 x ( 3)  0x ( n ) 0•fn(x(1),..x(n)) = f(x(1),x(2),..,x(n))•fj-1(x(1),…,x(j-1)) = fj(x(1),..,x(j-1), 0 ) + fj(x(1),..,x(j-1), 1)

Basic (failing) strategy 1• Question 1: What is the value of f0?
– Professor answers : 247800• Question 2: What are f1(0) and f1(1)– Professor answers: 4000 and 243800– You check f0 = f1(0) + f1(1)– If check fails, professor tells a lie: The end.
– Else, guess which of two values is wrong…..

• Question 3: What are f2(0,1) and f2(0,0)?

Basic (failing) strategy 2• Question 1: What is the value of f0?
– Professor answers : 247800• Question 2: What is the function f1(z)?
– Professor answers: 222800z6 + 12000 z5 + 4000.
– You check f0 = f1(0) + f1(1)– If fail, professor tells a lie: The end. Else, continue• Question 3: What is the function f2 (x(1),x(2))?
• Proceed this processSuccessful strategy• Question 1: What is the value of f0?
– Professor answers : 247800• Question 2: What is the function f1(z)?

– Professor answers: g1(z) = 222800z6 + 12000 z5 + 4000.
– You check f0 = g1(0) + g1(1)– If fail, professor tells a lie: The end. Else, continue• Select a random value r, and compute g1(r)– say, r = 367• Question 3: What is the function f2(367, z)– Professor answers: g2 (z) = 34800 z5 + 34900 z2 + 403000– You check g1(r) = g2(0) + g2(1)• Next, select another random value r’, and compute g2(r’)• CONTINUEAnalysis• Al l functions are considered in GF(p) for a primep > 2n• What is the probability that gi(z) is not fi(z) but
gi(r) = fi(r) ?
– In other words, algorithm does not detect the lie in
the i-th step

• Error probability is at most 3nm/p, VERY SMALL• So if the professor tells a lie, the system detects itwith high probability.

PCP

PCP (probabilistic checkable proof)• Instead of god, we give a written proof.
• For a NP problem, we have a proof of lengthpoly(n)– But, verifier wants to save time to verify– You prepare a proof such that verifier can easily
verify the correctness• This is just like database query!
• Like a database, we prepare the proof in a nicestructure.
– We need help of randomness and error correctingcodePuzzle 1
Captain Cook hided a great treasure, but he needto escape for a long time to prevent fromarrested.
He will send letters to his 20 pirates to inform thelocation of the treasure, but they are only
reliable if they watch each other.
So, he want to encode the secret key so that it isrevealed if and only if 11 or more meet.
How he should do?

Popular error correcting codes• Reed solomon code
– Your CD is encoded by using it– Use a polynomial on a field F• F= GF(2q) in practical implementation• Here, we use GF(p) for a prime p• Hadamard code
– Use randomness– We can correct very large error.

Reed Solomon code
• a(1)a(2),..,a(k) :the key we want to send
– Each a(0) is a member of GF(p), thus a large
number.

• Let F(x) = a(k)xk+ a(k-1)xk-1+..+ a(1)x + a(0)• We randomly select m>k values x(i) and lety(i)=F(x(i)).
• As for captain Cook, k=10, m=20
• Send (x(i), y(i)) to the i-th pirates for i=1,2,..,20

Puzzle 2• A team of N people ware blue or red hats.
– Hats are distributed randomly• Each person can see all hats excepts his/herown .
• Each person guess color of his/her hat, andshout simultaneously, but he can say “pass”• Your team wins if all answer correctly, but you
lose if all say “pass”.
• Consider a good strategy

Try to solve the puzzle• If n=3– Solution 1: Everyone randomly calls “B” or “R”• Wining probability = 1/8– Solution 2: Everyone randomly calls “B”,”R”, or “P”• Wining probability = 8/27 – 1/27 = 7/27

– Solution 3 : Choose a leader, who calls B or R. Others
say “P”.
• Winning probability = ½– Solution 4: If one sees two “R” (two “B), then calls “B”(resp. “R”) . If one sees different colors, “P”.
• Winning probability = ¾Try to solve the puzzle• If n=4• Solution 1: If one sees more red than blue,
then call B, otherwise R– Winning probability: 6/16 = 3/8• Solution 2: Force a person “ignored”, andapply 3 person strategy– Winning probability = ¾Try to solve the puzzle• General solution for n= 2k-1
– Assign each member his ID from 1 to n
– Each person compute the bitwise sum of ID of red hat
persons• How we call the color– If the bitwise sum of ID is his ID, then shout “blue”– If the bitwise sum of ID is 0, then shout “red”• Analysis– At least one person gives call
– The method only fails all red or all blue cases.
– Winning probability = 1 – 1/2k

Hamming code
• Given a bit sequence of length 2k -1 , weappend k check bits to detect an error of thecode including the position of the error.
• Check bit is the bitwise sum of the positions of
1 bits• In practice, we do slightly different
implementation.

Hadamard code
• Given a bit vector a= (a(1), a(2),…,a(n)), we
generate ∑ a(i) r(i) for all bit vectors r• Very large code (size 2n)• We can decode a even if we have many errors.
• We can decode a by using n code bits.

PCP (Probabilistic Checkable Proof)• PCP consists of all languages (i.e. problems) L that has arandomized polynomial time verifier V such that for any input x ,– If x ∈L (i.e., the answer of L for x is yes), thenThere exists a proof Π, such that Pr(V(x,Π), accept)= 1– Otherwise,
For any (fake) proofs Π, Pr(V(x,Π), accept) < 1/2• By definition, NP is in PCP• PCP should contain IP• Known: PCP = NEXP (non-deterministic exponential time)– Thus, a very wide class• Thus, we refine PCP by how many bits of proofs we see, and also
how many random bits we use.

PCP(r(n),q(n))• The number of random bits to use: O(r(n))• The number of bits of the proof we read:O(q(n))– The size of the proof is at most 2 O(r(n)q(n))• The famous result: (Arora, Lund, Motwani,
Sudan, Szegedy 1992)– NP = PCP ( log n, 1 )• We show an easier but key result:– NP ⊆ PCP (poly(n), 1)

We show that 3SAT is in PCP(poly(n),1)• Input: 3SAT formula• Professor (prover) wants to persuade you(verifier) that 3SAT has a satisfying assignment• Idea: You ask the professor to write the proof byusing Hadamard code.
– Also use idea of Reed-Solomon code

• You randomly check small number of bits of theproof to verify both
– Proof is written by using Hadamard code correctly– The proof code a satisfying assignment of 3SAT.

3SAT into degree 3 polynomial• 3SAT: {C1,C2,…,Cm } set of clauses• We showed IP (interactive proof) for #3SAT can begiven using high-degree polynomial.
• Here , we use degree 3 polynomial instead.
• For a clause Ci = X(1)∨ X(2) ∨X(3) we define
ci(x) = (1-x(1))x(2)(1-x(3))• If A satisfies 3SAT then ci(A)= 0 for all i• h (x(1),x(2),…,x(n)) = ∑ ci (x)• If A satisfies 3SAT then h(A)= 0– But, converse is false– How to resolve it? Use Hadamard code

3SAT into degree 3 polynomial
If A satisfies 3SAT then ci(A)= 0 for all i• Random bit sequence r(1),r(2),..,r(m)• f(X)=f(r,X)= f (x(1),x(2),…,x(n)) = ∑ ci (x) r(i)• If A satisfies 3SAT then f(A)= 0
If A does not satisfy 3SAT thenPr (f(A) = 0) = ½• You may ask professor the table of f(r,A) for all r– Professor can easily lie by showing the 0 table– You need a clever method to compute f(r,A) using theproof.

The proof
The proof consists of three tables• Sum A(S) of a(i) for i ∈S for all index set S.
– GA( z(1),..,z(n)) = ∑a(i)z(i)• Sum B(S’) of a(i)a(j) for (i,j) ∈S’ for all possible set S’of pairs of indices.
– GB( z(1,1),..,z(n,n))= ∑b(i,j) z(I,j)– b(i,j) = a(i)a(j)• Sum C(S’’) of a(i)a(j)a(k) for (i,j,k) ∈S’’ for all possible
set S’’ of triples of indices.
– GC(z(1,1,1),..,z(n,n,n)) = ∑c(i,j,k) z(I,j,k)– c(i,j,k) = b(i,j)a(k) = a(i)a(j)a(k)How to compute f(A) from the proof
The proof consists of three tables• Sum A(S) of a(i) for i ∈S for all index set S.
– GA( z(1),..,z(n)) = ∑a(i)z(i)• Sum B(S’) of b(i,j)=a(i)a(j) for (i,j) ∈S’– GB( z(1,1),..,z(n,n))= ∑b(i,j) z(i,j)• Sum C(S’’) of c(i,j,k)= a(i)a(j)a(k) for (i,j,k) ∈S’’ for– GC(z(1,1,1),..,z(n,n,n)) = ∑c(i,j,k) z(i,j,k)

f(X)=f(r,X)= f (x(1),x(2),…,x(n)) = ∑ ci (x) r(i)ci(x) : degree 3, e.g. (1-x(1))x(2)(1-x(3))

f ( X )    xi   xi x j iS1( i , j )S 2

x x xi( i , j , k )S3

j k

How to compute f(A) from the proof
The proof consists of three tables• Sum A(S) of a(i) for i ∈S for all index set S.
– GA( z(1),..,z(n)) = ∑a(i)z(i)• Sum B(S’) of b(i,j)=a(i)a(j) for (i,j) ∈S’– GB( z(1,1),..,z(n,n))= ∑b(i,j) z(i,j)• Sum C(S’’) of c(i,j,k)= a(i)a(j)a(k) for (i,j,k) ∈S’’ for– GC(z(1,1,1),..,z(n,n,n)) = ∑c(i,j,k) z(i,j,k)f ( A)    ai   ai a j iS1( i , j )S 2

a a ai( i , j , k )S3

jkf ( A)   A(S1 )  B(S2 )  C (S3 )f ( A)   GA (  (S1 ))  GB (  (S2 ))  GC (S ( 3 ))How to compute f(A) from the proof
The proof consists of three tables• Sum A(S) of a(i) for i ∈S for all index set S.
– GA( z(1),..,z(n)) = ∑a(i)z(i)• Sum B(S’) of b(i,j)=a(i)a(j) for (i,j) ∈S’– GB( z(1),..,z(n))= ∑b(i,j) z(i)z(j)• Sum C(S’’) of c(i,j,k)= a(i)a(j)a(k) for (i,j,k) ∈S’’ for– GC(z(1),..,z(n)) = ∑c(i,j,k) z(i)z(j)z(k)f ( A)    ai   ai a j iS1( i , j )S 2

a a ai( i , j , k )S3

j

f ( A)   A(S1 )  B(S2 )  C (S3 )Thus, f(A) =0 can be certified by reading three
entries of the tablekHow to compute f(A) from the proof
The proof consists of three tables• Sum A(S) of a(i) for i ∈S for all index set S.
– GA( z(1),..,z(n)) = ∑a(i)z(i)• Sum B(S’) of b(i,j)=a(i)a(j) for (i,j) ∈S’– GB( z(1,1),..,z(n,n))= ∑b(i,j) z(I,j)• Sum C(S’’) of c(i,j,k)= a(i)a(j)a(k) for (i,j,k) ∈S’’ for– GC(z(111),..,z(nnn)) = ∑c(i,j,k) z(I,j,k)f ( A)    ai   ai a j iS1( i , j )S 2

a a ai( i , j , k )S3

jkf ( A)   A(S1 )  B(S2 )  C (S3 )Can professor cheat? Note that α=0 or 1 with evenprobability if original SAT is false

How to reveal false proof
The proof consists of three tables• Sum A(S) of a(i) for i ∈S for all index set S.
– GA( z(1),..,z(n)) = ∑a(i)z(i)• Sum B(S’) of b(i,j)=a(i)a(j) for (i,j) ∈S’– GB( z(1,1),..,z(n,n))= ∑b(i,j) z(I,j)• Sum C(S’’) of c(i,j,k)= a(i)a(j)a(k) for (i,j,k) ∈S’’ for– GC(z(111),..,z(nnn)) = ∑c(i,j,k) z(I,j,k)

We should examine the following:
1. GA(Z) is a linear function
2. B= A x A : x is the outer product
3. C= A x B

How to reveal false proof (Step1)
The proof consists of three tables• Sum A(S) of a(i) for i ∈S for all index set S.
– GA(z(1),..,z(n)) = ∑a(i)z(i)First step: (δ<1/3 is small)
1. G(z)=GA(z) is a NEAR linear function, that is there
is a linear function H such that G(x)= H(x) withprobability at least 1-δ• Theorem: If G(x) + G(y) = G(x+y) with probability
1 – δ/2 , then G(x) is near linear

If G(z) is near linear, we can do error correction byG(z)  G(x)+G(z-x) for taking random vector xHow to reveal false proof (STEP2)
The proof consists of three tables• GA( z(1),..,z(n)) = ∑a(i)z(i)• Sum B(S’) of b(i,j)=a(i)a(j) for (i,j) ∈S’– GB( z(1,1),..,z(n,n))= ∑b(i,j) z(i,j)
If B= A x A is cheating, for random r and s,

Prob(r ( A  A)s  r Bs )  1 / 4tt

Prob(GA (r )GA (s)  GB (r  s))  1 / 4

How to reveal false proof (STEP2)
The proof consists of three tables• GA( z(1),..,z(n)) = ∑a(i)z(i)• Sum B(S’) of b(i,j)=a(i)a(j) for (i,j) ∈S’– GB( z(1,1),..,z(n,n))= ∑b(i,j) z(i,j)• Sum C(S’’) of c(i,j,k)= a(i)a(j)a(k) for (i,j,k) ∈S’’ for– GC(z(1,1,1),..,z(n,n,n)) = ∑c(i,j,k) z(i,j,k)

If C= A x B is cheating,Prob(r ( A  B)s  r Cs)  1 / 4tt

Prob(GA (r )GB (s)  GC (r  s))  1 / 4

Overall• We can check that GA(z) is near linear bychecking constant number of bits of the proof.
• We can check the other two conditions bychecking constant number of bits
• Thus, we can reveal cheating of the proof withhigh probability by checking constant numberof bits.
• Thus, 3SAT is in PCP(poly(n), 1).

Further (and important) improvement• NP is PCP( log n, 1)– Reducing the number of bits to O(log n)• Thus, we need to 2 O(log n) < p(n) possible
choices of query, and each query asks c bits.
• Thus, the (effective) proof of length is c p(n)• Thus, the possibility of query set is (c p(n))c– This is polynomial size in n

A surprising implication• NP is PCP( log n, 1)• Polynomial number of possible choice of queries(without knowing A)• The probability of “yes” queries is formulated as apolynomial size optimization problem (CSP)
considering A as unknown vector X• This probability is 1 if and only if 3SAT formula has an
assignment.
• This probability is less than ½ if and only if 3SAT
formula has no assignment• This means that if CSP can be solved withapproximation ratio ¾, then, we can solve 3SAT

Classification of NPO problems• If P is not NP, then NP optimization problems (NPO) areclassified into as follows:
1. P (polynomial time soluble)
2. PTAS (a problem with polynomial time approximation
scheme)–3.

APX complete (a problem with a polynomial time
constant approximation solution, but not in PTAS)–

4.

Knapsack problem, Subset-sum problem, Euclidean travelingsalesman problem, Max Independent set in planar graphMAX 3-SAT, MAX 2-SAT, Vertex Cover

Problems with no constant approximation polynomial
time algorithm (if P is not NP)–

CLIQUE, Graph coloring, set covering,