ness R, that V 1, 2 (A; R) outputs accept is
at most 1 − e (n).
The definition is (intentionally) very
close to that of a PCP verifier, so let us
notice the differences. Rather than one
proof oracle, we now have two provers.
But each is asked only one question, so
effectively they are oracles! In PCPs, the
response to a query is one bit long, but
now the responses are a(n) bits long.
On the other hand, in PCPs, the verifier
is allowed to make q(n) queries to the
proof oracle, while here the verifier is
only allowed one query each. Nevertheless, PCP verifiers and MIP verifiers are
closely related. In particular, the following proposition is really simple from the
Proposition 4. 2. If 3SAT has a 2IP verifier of answer size a(n) and gap e (n), then
3SAT has a PCP verifier with query complexity 2 · a(n) and gap e (n).
The PCP verifier simply simulates
the 2IP verifier, with each query to the
provers being simulated by a(n) queries
to the proof oracle.
Thus to prove the PCP theorem, it suffices to give a 2IP verifier with constant
gap and constant answer size. We start
with the approach of Arora and Safra. 4
Reducing answer size. The initial
proofs of the PCP theorem approached
their goal by holding the gap to be a
constant, while allowing the 2IP verifier to have (somewhat) long answer
sizes. Key to this approach were some
alphabet reduction lemmas initiated
in the work of Arora and Safra. 4 Here we
state two from Arora et al., 3 that suffice
for our purposes.
Lemma 4. 3 (Arora et al. 3). There exists
a constant d > 0 such that if 3SAT has a 2IP
verifier with answer size a(n) and gap e,
then 3SAT also has a 2IP verifier with answer size (log a(n) ) 2 and gap e · d .
Lemma 4. 4 (Arora et al. 3). There exist
constants c < ∞ and t > 0 such that if 3SAT
has a 2IP verifier with answer size a(n) =
o(log n) and gap e , then 3SAT also has a 2IP
verifier with answer size c and gap e · t.
Both lemmas above offer (pretty severe) reductions in answer sizes. Below,
we show how they suffice to get the
PCP theorem. Of course, the technical
on PcPs is rich
with a diversity
but we chose
to focus on only
two: the query
and the gap.
complexity is all hidden in the proofs
of the two lemmas, which we will not be
able to present. We simply mention that
these lemmas are obtained by revisiting
several popular “algebraic error-correcting codes” and showing that they admit
query efficient probabilistic algorithms
for “error-detection” and “
error-correction.” The reader is referred to the original papers3, 4 for further details.
Proof of Theorem 2. 2. We start by
noting that the classical (
deterministic) verifier for 3SAT is also a 2IP verifier
with answer size n and gap 1. Applying
Lemma 4. 3 we then get it thus has a 2IP
verifier with answer size (log n) 2 and
gap d . Applying Lemma 4. 3 again we
now see that is also has a 2IP verifier with answer size (log(log n)) 2 and
gap d 2. Since a(n) = o(log n) we can
now apply Lemma 4. 4 to see that it has
a 2IP verifier with answer size c and
gap d 2 · t. By Proposition 4. 2 we conclude
that 3SAT has a PCP verifier with query
complexity 2c and gap d 2t.
amplifying error. We now turn to
the new, arguably simpler, proof due to
Dinur12 of the PCP theorem. Since we are
hiding most of the details behind some
of the technical lemmas, we would not
be able to completely clarify the simplicity of Dinur’s approach. However,
we will be able to at least show how it
differs right from the top level.
Dinur’s approach to the PCP theorem is an iterative one, and rather than
working with large answer sizes, this
proof works with small gaps (during intermediate stages).
The approach fixes a “generalized
graph k-coloring” problem as the problem of interest and fixes a canonical 2IP
verifier for this problem. It starts by observing that 3SAT can be transformed
to this generalized graph 3-coloring
problem. It then iteratively transforms this graph into a different one,
each time increasing the “gap of the
instance.” The final instance ends up
being one that where the canonical 2IP
verifier either accepts with probability
1, or rejects with constant probability
(depending on whether the original
instance is satisfiable or not), which
is sufficient for the PCP theorem. We
go into some more details of this approach below, before getting into the
heart of the process which is the single