Quad-SAT

(Ingredient 3 of 5 in the PCP overview.)

To give a description of our PCP protocol, will let Peggy prove that she knows a solution to a certain NP-complete problem. The one we will use for our protocol is Quad-SAT.

In Quad-SAT, one has a bunch of variables over a finite field $\mathbb{F}_q$, a bunch of equations in these variables of degree at most two, and one wishes to find a satisfying assignment.

Example showing Quad-SAT is pretty clearly NP-complete

If you can’t see right away that Quad-SAT is NP-complete, the following example instance can help, showing how to convert any instance of 3-SAT into a Quad-SAT problem:

$$\begin{aligned} x_i^2 &= x_i \qquad \text{ for each } i=1,2,\dots,10000 \\ y_1 &= (1-x_{42}) \cdot x_{17}, \hspace{3.5em} 0 = y_1 \cdot x_{53} \\ y_2 &= (1-x_{19}) \cdot (1-x_{52}), \hspace{1em} 0 = y_2 \cdot (1-x_{75}) \\ y_3 &= x_{25} \cdot x_{64}, \hspace{6em} 0 = y_3 \cdot x_{81} \\ &\vdots \qquad\text{(imagine many more such pairs of equations)} \end{aligned}$$

The $x_i$’s are variables which are seen to either be $0$ or $1$. And then each pair of equations with $y_i$ corresponds to a clause of 3-SAT.

Setup for the toy PCP protocol

Let’s say there are $N$ variables and $E$ equations, and $N$ and $E$ are both large. Peggy has worked really hard and figured out a satisfying assignment

$$A \colon \{x_1, \dots, x_N\} \to \mathbb{F}_q$$

and wants to convince Victor she has this $A$. Victor really hates reading, so Victor neither wants to read all $N$ values of the $x_i$ nor plug them into each of the $E$ equations. He’s fine receiving lots of stuff in the mail; he just doesn’t want to read it. This is what PCP will let them do, and we describe it in the next post.