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.