PP

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 definitions.

 

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. ⁴

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. ⁴ Here we state two from Arora et al., ³ that suffice for our purposes.

 

Lemma 4. 3 (Arora et al. ³). 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) ) ² and gap e · d .

 

Lemma 4. 4 (Arora et al. ³). 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

the literature
on PcPs is rich
with a diversity
of parameters,
but we chose
to focus on only
two: the query
complexity
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 papers^{3, 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) ² and gap d . Applying Lemma 4. 3 again we now see that is also has a 2IP verifier with answer size (log(log n)) ² and gap d ². 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 ² · t. By Proposition 4. 2 we conclude that 3SAT has a PCP verifier with query complexity 2c and gap d ²t.

amplifying error. We now turn to the new, arguably simpler, proof due to Dinur¹² 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 iteration.