Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The PCP theorem, $\mathsf{NP} = \mathsf{PCP}(\mathsf{log}\, n, 1)$, involves probabilistically checkable proofs with polynomial time verifiers, so the smallest class that can be characterized in this way (that is, $\mathsf{PCP}(0, 0)$) must be $\mathsf{P}$. There are also PCP characterizations of larger complexity classes (for example, $\mathsf{NEXP} = \mathsf{PCP}(\mathsf{poly}, \mathsf{poly})$), also using polynomial time verifiers.

Can we achieve an interesting (that is, not immediately following from the definitions) PCP characterization of smaller complexity classes by restricting the time or space used by the verifier? For example, by using a logarithmic space verifier, or an $\mathsf{NC}$ circuit verifier?

share|cite|improve this question
Why not? If you restrict the space of the verifier to log, then PCP(0, 0) obviously becomes equal to L. And this is a PCP characterization of L if you count PCP(0, 0)=P as a PCP characterization of P. I cannot see the point of the question. – Tsuyoshi Ito Jul 18 '12 at 21:51
I suppose I meant are there any characterizations that don't follow immediately from the definition, in the same way that PCP(log n, 1) is non-obvious characterization of NP. – argentpepper Jul 19 '12 at 1:26
Your comment is contradictory to your question where you count “PCP(0, 0) = P” as a PCP characterization of P. – Tsuyoshi Ito Oct 1 '12 at 14:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.