Probabilistically checkable proofs (PCP's) are proofs that can
be verified with high probability by looking at the proof in only a
few randomly chosen places. Here we describe a relatively
simple self-contained proof that any satisfiable Boolean formula has a PCP of
its satisfiability that can be checked by querying a constant number
of bits. Formally, we show
### Building block #1 --- Encoding F as a collection of quadratic functions over Z_{2}^{n}.

### Building block #2 --- Freivald's trick

### Building block #3 --- SelfTestingCorrecting

^{n× n} bits,
one for each possible matrix X.
Let P(X) denote the bit in the proof P giving the value of F_{b}(X).
^{2} < 1/2.

References:

THEOREM: SAT ∈ PCP(n^{O(1)}, 1)

That is, SAT has a randomized polynomial-time verifier V with the following properties:

- V takes input (A,P) where A is a Boolean formula of size n, and P is a PCP.
- If A is satisfiable, then there exists a PCP P such that V(A,P) accepts with probability 1.
- If A is not satisfiable, then for any string P, V(A,P) rejects with probability at least 1/2.
- V(A,P) looks at O(1) bits of P and uses n
^{O(1)}random bits.

The PCP system we describe uses exponentially large proofs.

In fact, the stronger result holds, but we don't describe a proof:

THEOREM: SAT ∈ PCP(log(n), 1)

In his book "Approximation Algorithms", Vazirani mentions the following intuition for PCP's. Given a Boolean formula in 3-SAT form with $m$ clauses, suppose the verifier was given a satisfying assignment (as the proof of satisfiability) and then checked a single clause at random of the formula to see if the assignment satisfied that one clause. If the clause was satisfied, then the verifier would accept.

With this simple PCP system, if the formula is satisfiable, there is a proof to give the verifier so that the verifier will accept with probability 1. Conversely, if the formula is not satisfiable, no matter what ``proof'' one gives the verifier, the verifier will reject with probability at least 1/m.

The challenge is to amplify this rejection probability to at least 1/2, while still having the verifier check only a constant number of bits in the proof.

The verifier wants to verify that the Boolean formula F is satisfiable.
To begin, the verifier converts F
into a set S of equivalent quadratic equations and variables over Z_{2}^{n}
(the integers {0,1} with arithmetic mod 2).
The equations will have a solution if and only if F is satisfiable.

Example: Suppose F = (v_{1} or v_{2}) and (v_{1} or v_{2}) .

Then the equations are:

Equation | Meaning |

B_{3} = B_{1} + B_{2} - B_{1} B_{2} | B_{3} = (v_{1} or v_{2}) |

B_{4} = 1 - B_{1} B_{2} | B_{4} =(v_{1} or v_{2}) |

B_{5} = B_{3} B_{4} | B_{5} = B_{3} and B_{4} |

B_{5} = 1 | B_{5} = true |

Next, the verifier selects a random subset of the set of equations above
and adds them together to get a single equation, say, ∑_{ij} x_{ij} B_{i} B_{j} = 1
for some particular (known) x. We will write this equation also as F_{B}(x) = 1.
Note that the verifier knows x but not B, even though we use notation
suggesting that F_{B}(x) is a function of x.

LEMMA: *The random function F _{B}(x) has the following property: for any particular assignment B=b, if b satisfies all the equations,
then F_{b}(x)=1. Otherwise, Pr[F_{b}(x) = 1] ≤ 1/2. *

This is because, if there are any incorrect equations (for a particular b), the final equation will be incorrect exactly when the number of incorrect equations chosen in the set is odd. This is FreivaldsTrick.?

Finally, the verifier examines the proof P, using the SELF-CHECK-DIAG and SELF-CORRECT algorithms from SelfTestingCorrecting.?

The verifier expects the proof P to encode a satisfying assignment B=b for the equations as follows.
For each of the 2^{n× n} n× n matrices X ∈ Z_{2}^{n× n}, the proof should
tell the value (0 or 1) of

- F
_{b}(X) = ∑_{ij}X_{ij}b_{i}b_{j}.

The key observation at this point is that if P has the correct format,
then P(X) is a diagonal linear function of X.
In particular, P(X) = F_{b}(X) = ∑_{ij} X_{ij} b_{i} b_{j}
for some particular b.

Now we can state the verifier completely. On input (A, P), where A is a SAT formula and P is an alleged proof that B is satisfiable, the verifier V does the following:

- Use SELF-CHECK-DIAG(P) to check that P(X) is an approximate diagonal linear function of X. If the test fails, reject.
- Assume that P is an approximate diagonal linear function encoding a diagonal linear function Q(X) = ∑
_{ij}X_{ij}b_{i}b_{j}for some b. - As described above, construct a set of quadratic equations over Z
_{2}^{n}that has a solution iff A is satisfiable. - Repeat the remaining steps twice:
- As described above, let quadratic equation "F(B)=1" be obtained by summing a random subset of the equations. Compute x such that F(B) = ∑
_{ij}x_{ij}B_{i}B_{j}. - Use SELF-CORRECT(P,x) to evaluate Q(x). If SELF-CORRECT discovers a non-linearity, reject. If the equation "Q(x)=1" fails, reject.
- Accept.

LEMMA: If A is satisfiable, there exists a proof P such that V(A, P) accepts.

PROOF: As described, let B=b be a satisfying assignment of the quadratic equations.
For each X, let P(X) = ∑_{ij} X_{ij} b_{i} b_{j} .
Then P(X) is a diagonal linear function of X, so the SELF-CHECK-DIAG(P) test passes,
and SELF-CORRECT(P,x) returns P(x), which equals Q(x), which equals F(b).
Since all equations in the set of quadratic equations are satisfied,
so is the equation F(b)=1, so Q(x)=1 holds too.
Thus, the verifier accepts.

QED

LEMMA: If A is not satisfiable, then for any alleged proof P, Pr[V(A,P) rejects] ≥ 1/2.

PROOF:
Suppose A is not satisfiable.
If P does not encode an approximate diagonal linear function, then SELF-CHECK-DIAG(P) fails with probability at least 1/2.

So assume that P does. Let Q(X) = ∑_{ij} X_{ij} b_{i} b_{j} be the approximate diagonal linear function that P encodes.
One of the following things has to happen for the remaing steps to not reject:

- Freivalds' trick fails (the random subset of equations sums to an equation that is satisfied). Since not all equations are satisfied by b, this happens with probability at most 1/2.
- Freivalds trick succeeds but the SELF-CORRECT(P,x) call fails to return the correct value Q(x),

QED

References:

- S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. 33rd IEEE Symp. on Foundations of Computer Science, pages 14-23, 1992.