Charanjit S. Jutla,
Anindya C. Patthak and Atri Rudra
On the Relativization of
Probabilistically Checkable Proofs
Abstract :
Building on the work of Fortnow, we look at the relationship between
relativized nondeterministic polynomial time NP and relativized
probabilistic checkable proofs PCP.
It is known that the PCP theorem NP=
PCP(logn,1))
does not relativize.
Previous works have tried to pinpoint which part of the proof of the
PCP
theorem does not relativize. In the first set of results, we show that the
gap amplification part of the proof does
relativize. On closer scrutiny, this surprising result turns out to be due to
the way oracles
are accessed by the relativized PCP machine. The importance of the role
of the oracle access mechanism in interpreting relativization results,
especially when dealing with ``non-traditional" complexity classes like
PCP,
was pointed out earlier by Fortnow.
We revisit our results by looking at a stronger oracle access mechanism
proposed by Fortnow which we call the pointer model.
We refine the pointer model of Fortnow further, and show that in this
oracle access model the gap amplification step of the PCP
theorem does
not relativize. This refinement of the pointer model is necessary as
without this refinement even the PCP theorem can be shown to relativize.
We believe that our refined oracle access mechanism is the right one when
dealing with PCPs.
Versions