This post gives a gentle introduction to the Probabilistic Checkable Proof (PCP), the pearl of computational complexity theory.

Introduction

Consider the canonical NP problem, boolean satisfiability (SAT). To determine if a Boolean formula is satisfiable, a deterministic verifier needs to check a polynomial length proof — the assignment of each variable. But what if the verifier is allowed to use randomness and to fail with a small probability? It turns out that the probablistic verifier still needs a polynomial-size proof, but it does not need to look at all of it. With oracle access to the proof, it only needs to make constant queries to the proof, i.e. check constant number of locations of the proof. The proof string is of course much more complex than the assignment of each variable. We call these proofs “probablistic checkable proofs” (PCP). The aforementioned fact about NP is the famouse PCP theorem, and in this post, we will walk through the key components of the proof.

Definition

A Language $L$ is in the complexity class PCP$_{c, s}[r, q]_\Sigma$ if there exists a polynomial-time probablistic oracle Turing machine called the PCP verifier $V_L$ such that

• $\Sigma$ is the alphabet for the proofs
• $V_L$ uses $r$ bits of randomness and $q$ queries
• Completeness: If $x \in L$, there exists a proof $\pi$ such that $\Pr_{\rho \sim \{0,1\}^q}[V_L^\pi(x; \rho) = 1] > c$
• Soundness: If $x \notin L$, for all proofs $\pi$, $\Pr_{\rho \sim \{0,1\}^q}[V_L^\pi(x; \rho) = 1] < s$

Basic Examples and Results

• PCP$_{c, s}[0, 0]_\Sigma$ = P
• PCP$_{c, s}[O(\log(n)), 0]_\Sigma$ = P
• PCP$_{c, s}[poly(n), 0]_\Sigma$ = BPP
• PCP$_{c, s}[0, poly(n)]_\Sigma$ = NP
• PCP$_{c, s}[O(\log(n)), poly(n)]_\Sigma$ = NP

Usually $\Sigma = \{0,1\}$ and we simply drop $\Sigma$. Further, if we drop the completeness and soundness parameters, we implicity assume that $c=1, s=\frac{1}{2}$. Note that given $r$ bits of randomness and $q$ queries, the verifier can check at most $2^r q$ locations of the proof, which is the effective size of any proof. (Here, we assume the verifier is non-adaptive.)

The Statement of the PCP Theorem

The theorem demands a very intricate proof, which is of polynomial size and requires only constant number of queries. The proof we will explore is based on “proof composition”. We will construct two not so strong proofs: a very long proof (exponential-size) that requires only constant number of queries, and a short proof (polynomial size) that requires polylog queries. Then we will compose them to take the merits of both. Thus, the outline of the proof will contain three main components: (1) an exponential-size PCP, (2) a polynomial-size PCP, and (3) the proof composition. Generally speaking, every PCP is a smart coding of the plain proof, so we will use different codes borrowed from coding theory throughout the journey.

Exponential-size PCP

Note that the effective proof size is $2^{poly(n)} \cdot O(1) = \exp(poly(n))$, hence the name exponential-size PCP. To prove this statement, we will consider a NP-complete problem called QUADEQ, which determines if a system of quadratic equations has a satisfying assignment. The prover should use Walsh-Hadamard code to construct a exponential-size PCP of the satisfying assignment. The verifier will first use linearity testing to verify the validity of the codeword, i.e., to check that the proof is indeed the Walsh-Hadamard code of some string. Then it can use constant queries to verify if the string is a satisfying assignment with high probability.

QUADEQ

A quadratic equation of $n$ variables $u_1, \dots, u_n$ over $GF(2)$ has the form $\sum_{i, j \in [n]} a_{i,j} u_iu_j = b$. A system of quadratic equations over $GF(2)$ is in QUADEQ if the system has a satisfying assignment $u \in \{0, 1\}^n$.

The polynomial-size proof of QUADEQ is simply the satisfying assignment of the variables $u$, so QUADEQ is clearly in NP. To see that QUADEQ is NP-complete, it is easist to reduce from circuit-satisfiabily. We can assign a variable to represent the output of each gate in the circuit. Then

• $u_k = u_i \land u_j \quad \to \quad u_k = u_iu_j$
• $u_k = u_i \lor u_j \quad \to \quad u_k = u_i + u_j + u_i u_j$
• $u_k = \lnot u_i \quad \to \quad u_k = 1 - u_i$.

Walsh-Hadamard Code

To construct a exponential-size PCP, we will make use of the Walsh-Hadamard code. Given a message $u \in \{0,1\}^n$, its Walsh-Hadamard codeword is $H(u) \in \{0,1\}^{2^n}$, where $H(u)(x) = u \odot x$. Here $x \in \{0,1\}^n$ is the index of $H(u)$, a string of exponential size, and $u \odot x$ is the dot-product of $u$ and $x$.

Random Subsum Principle

As a fundamental principle of coding, if the messages $u$ and $v$ differs in a few locations, we want their codewords to differ in almost all the locations. This is indeed true to Walsh-Hadamard Code, which can be summarized as the random subsum principle:

Linear Functions

Another principle of coding is that the verifier should be able to check the validity of a codeword, i.e., the given string is the codeword of some string, or the given string is close to the codeword of some string. To demonstrate this property, we will consider the Walsh-Hadamard codeword of $u$ as a linear function $l_u: \{0,1\}^n \to \{0,1\}$ defined by $l_u(x) = H(u)(x) = u \odot x$. In general, a linear function $f: \{0,1\}^n \to \{0,1\}$ satisfies $f(u+v) = f(u)+f(v)$. It’s straightforward to see that $l_u$ is indeed a linear function. Conversely, every linear function $f$ can be written as $f=l_u$ for some $u \in \{0,1\}^n$. Let $e_i \in \{0,1\}^n$ be the string with a single $1$ at the $i$-th location. Then $u_i = f(e_i)$. Thus, the Walsh-Hadamard code is equivalent to linear functions over $GF(2)$. To check the validity of a codeword is to test whether it is close to a linear function.

BLR Linearity Testing

Formally, we say that a function $f$ is $\rho$-close to a linear function $l_u$ if

The BLR linearity testing is actually very simple: we randomly query two locations $x$ and $y$, and test if $f(x)+f(y) = f(x+y)$. Nevertheless, it is very powerful. We state without a proof of the following theorem: If

$f$ is $\rho$-close to some linear function.

This suggests a simple probabilistic algorithm for linearity testing, and hence verifying a Walsh-Hadamard code.

Local Decoding

Walsh-Hadamard code is also a locallly decodable code, i.e., we can recover a single bit of a corrupted codeword while making constant number of queries. Suppose $f$ is $(1-\delta)$-close to a linear function $g$ (a Walsh-Hadamard codeword), and we want to decode $g(x)$, but $f(x)$ is corrupted. Then we can pick a random $r \in {0,1}^n, and since

we can decode $g(x)$ by querying $f(x+r)$ $f(r)$ if these two locations are not corrupted. If the codeword is corrupted at every location with the same probability, then this procedure actually makes things worse. However, in our PCP system in the later sections, we will only look for specific locations of the codeword. The local decoding procedure guards against a malicious prover who will concentrate the corruptions on the certain locations we are looking at.

An Exponential-size PCP for QUADEQ

QUADEQ asks, given $m$ quadratic equations of $n$ variables, if there is satisfying assignment of the variables. Equivalently, QUADEQ asks, given inputs $A$ and $b$, where $A$ is a $m \times n^2$ matrix, and $b$ is an $m$ dimensional vector, if there is a $n^2$ dimensional vector $U$ such that $U = u \otimes u$ and $AU = b$. Here $u$ should be a satisfying assignment.

Our exponential-size PCP should be $f = WH(u)$ and $g = WH(U)$, where $U = u \otimes u$. Now the verifier will carry out the following steps:

• (Linearity Test) Check that $f$, $g$ are linear functions i.e., $f$, $g$ are Walsh-Hadamard code- words.
• (Tensor Test) Check that $f$, $g$ encode the same source word i.e., $g$ encodes $u \times u$ and f encodes $u$.
• (Satisfiability Test) Check that $AU = b$.

We’ve already discussed the linearity test. We will describe the remaining two steps.

Tensor Test

The idea of tensor test is very straightforward. If $f = WH(u)$ and $g = WH(u \otimes u)$ for some $u$, then

Thus, given two linear functions $f: \{0,1\}^n \to \{0,1\}$ and $g: \{0,1\}^{n^2} \to \{0,1\}$, the tensor test is as following:

• Choose $r,r' \in \{0,1\}^n$ uniformly at random.
• Accept if $g(r \otimes r') = f(r)f(r')$

The protocol is clearly complete. It is also sound: based on random subsum principle, it can be shown that each tensor test rejects correctly with at least $\frac{1}{4}$ probability. Thus, it is also efficient: we only need to repeat the test constant number of times to achieve desired parameters.

Satisfiability Test

The satisfiability test is also quite straightforward:

• Choose $r \in \{0,1\}^m$ uniformly at random.
• Accept if $(AU)\odot r = b \odot r$

Again, based on the random subsum principle, each test rejects correctly with at least $\frac{1}{2}$ probability. Again, we only need to repeat the test constant number of times to achieve desired parameters.

Polynomial-size PCP

Reed-Muller code

SumCheck Protocol

Low-degree Testing

PCP Theorem via Proof Composition

Now we’ve introduced two weaker PCP theorems, we will compose them to prove the PCP theorem. In order to do that, we introduce two variants of PCPs, whose purposes will be explicit once we get to proof composition

PCP of Proximity (PCPP)

We now present a relaxation of PCPs that only verify that the input is close to an element of the language. The advantage of this relaxation is that it allows the possibility that the verifier may read only a small number of bits from the input. Actually, for greater generality, we will divide the input into two parts $(x,y)$, giving the verifier $x$ explicitly and $y$ as an oracle, and we only count the verifier’s queries to the latter. Thus we consider languages consisting of pairs of strings. For a pair language $L$, we define $L(x) = \{y: (x,y) \in L\}$.

Definition

A Language $L$ is in the complexity class PCPP$_{c, s, \delta}[r, q]_\Sigma$ if there exists a polynomial-time probablistic oracle Turing machine called the PCPP verifier $V_L$ such that

• Completeness: If $x \in L$, there exists a proof $y \circ \pi$ such that $\Pr_{\rho \sim \{0,1\}^q}[V_L^{y \circ \pi}(x; \rho) = 1] > c$
• Soundness: If $\Delta(y, L(x)) > \delta$, for all proofs $\pi$, $\Pr_{\rho \sim \{0,1\}^q}[V_L^{y \circ \pi}(x; \rho) = 1] < s$

We introduce a new proximity parameter $\delta < 1$, and the distance $\Delta(y, L(x))$ is defined as

if $x \in L$ and $\Delta(y, L(x)) = 1$ if $x \notin L$.

On one hand, the soundness criterion of PCPPs is a relaxation of the soundness of PCPs. Whereas, a PCP is required to reject (with high probability) every input that is not in the language, a PCPP is only required to reject input pairs $(x,y)$ in which the second element (i.e., $y$) is far from being suitable for the first element (i.e., $y$ is far from L(x)). That is, in a PCPP, nothing is required in the case that $y$ is close to $L(x)$ and yet $y \notin L(x)$. On the other hand, the query complexity of a PCPP is measured more stringently, as it accounts also for the queries to the input-part y (on top of the standard queries to the proof $π$). This should be contrasted with a standard PCP that has free access to all its input, and is only charged for access to an auxiliary proof.

Construction

Robust PCP

We now present a strengthening of the standard PCP soundness condition. Instead of asking that any proof is rejected with high probability, we ask that any proof is far from acceptance with high probability.

Definition

Given an input $x$ and a proof $\pi$, if we fix the random bits $\rho$, we have a local view $\pi(x, \rho)$. We define the accepting views as

A Language $L$ is in the complexity class RPCP$_{c, s, \sigma}[r, q]_\Sigma$ if there exists a polynomial-time probablistic oracle Turing machine called the PCP verifier $V_L$ such that

• Completeness: If $x \in L$, there exists a proof $\pi$ such that $\Pr_{\rho \sim \{0,1\}^q}[V_L^\pi(x; \rho) = 1] > c$
• Soundness: If $x \notin L$, for all proofs $\pi$, $\Pr_{\rho \sim \{0,1\}^q}[\Delta(\pi(x, \rho), A(V, x, \rho))<\sigma] < s$

Here, the distance function $\Delta$ is defined similarly as in the case of PCPP. Note that PCP$_{c, s}[r, q] =$ RPCP$_{c, s, 0}[r, q]$, i.e., a vanilla PCP has $0$ robustness.

Construction

Proof Composition

To carry out proof composition, we will have an outer RPCP which has a small size, and an inner PCPP which uses a few queries. When the outer RPCP determines the oracle positions to query given random bits $\rho$, $\pi_{out}(x, \rho)$, the inner PCPP will verify that the selected positions are accepted, $V_{in}^{\pi_{out}(x, \rho), \pi_{in}^\rho}(x)=1$. The new proof will be the concatenation of $\pi_{out}$ and $\pi_{in}^\rho$ for all $\rho$. Note that we need the outer RPCP to be robust, because the inner PCPP only has soundness gurantee if $\pi_{out}(x, \rho)$ is far from accepting.

References

[1] CS 294 at UC Berkeley, Probabilistically Checkable and Interactive Proof Systems, Spring 2019, Website