2026-11-04

2026-11-04 TOC Scribe

$\newcommand{\PCP}{\mathbf{PCP}}$ $\newcommand{\comNP}{\mathbf{NP}}$ $\newcommand{\comP}{\mathbf{P}}$ $\newcommand{\GSAT}{\mathsf{GAP-3SAT}}$ $\newcommand{\MTSAT}{\mathsf{MAX-3SAT}}$ $\newcommand{\TSAT}{\mathsf{3SAT}}$

Student Presentation: Probabilistic Checkable Proofs (PCP)

Theorem 1: $\mathbf{PCP}$ Theorem: Hardness of approximation view

$\exists$ some constant $0 \lt \rho \lt 1$ s.t. $\forall L\in \comNP$, $\exists$ a poly reduction $\GSAT: x\rightarrow$ 3CNF formula $\varphi$ such that

• $x\in L \implies \mathsf{OPT}(\varphi) = 1$
• $x \notin L \implies \mathsf{OPT}(\varphi) \lt \rho$

The above image summarize this. We know that $\forall L \in \comNP$ we can convert it to a 3CNF. The above theorem states that $\exists$ some function $f$ such that those formulas have this gap between them. All the non-instances have at most $\rho\%$ of clauses that are satisfiable and instances, obviously, have all clauses satisfiable. This causes this no man’s land between them.

Notice that we’re saying that this function exists – though very hard to write down. Another point to keep in mind is that $\rho$ is constant – it doesn’t depend on $n$.

Implications

Though the above “reduction” may seem neat, its real implication is with approximation. Let’s suppose that you have some polynomial-time $\epsilon$-approximate algorithm to solve $\MTSAT$, meaning it can tell with some negative error the percentage of clauses that are satisfiable, you can solve $3SAT$ which would imply $\comP = \comNP$.

The reason is that once we’ve established this gap, we can stop after we cross it, as we know that there are no instances above $\rho$ and below 1.

This leads us to conclude approximation is as hard as solving the real thing.

Efficient Verification

A more positive outlook on this is efficient verification. Say that we convert some problem in $\comNP$ into this $\GSAT$. We have the following interactive proof

The above proof is complete as all clauses of all positive instances will evaluate to 1. Therefore we will always accept any positive instance.

The above proof is sound with probability at most $\rho$.

Why would one prefer this?

A TM proof for $\TSAT$ would have the same completeness but its soundness would be very low. This is because even for $\varphi\notin\TSAT, \mathsf{OPT}(\varphi) \approx 1$ so randomly chosen clause being satisfiable is very low.

Our reduction to $\GSAT$ greatly amplifies the soundness.

The Proof View

We can think of languages having local proofs. Notice above that we only needed to read 3 bits and we only needed to flip $\log(n)$ random coins to index into proof. We parameterize $\PCP$ as $\PCP(r(n), q(n))$ where $r(n)$ is the number of random coins and $q(n)$ is the number of queries to the proof.

Theorem 2: The $\PCP$ theorem

$\comNP = \PCP(\log n, 1)$

Though the equivalence is obvious, at least using the $\GSAT$ reduction, the proof is quite hard. There have been many proofs of this theorem but the simplest one to read is by Din07. There is also a video of her explaining this.

It has numerous applications including ZKP and Reed Solomon Encoder.

Theorem 3: Exponential Time Hypothesis

$TSAT$ requires at least $2^{\Omega(n)}$ time to solve

Here $n$ is the number of variables. Usually $\TSAT$ is parameterized by two variables - $n, m$ where $m$ is the number of clauses. You can only have so many clauses with $n$ variable, I believe it is cubic, before you have repetition. So they are polynomially linked. Here we just ignore $m$.

The above statement implies that even if you solve $\TSAT$ in $2^{0.01n}$ it still would not refute ETH.

TODO