<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2012-07-18T21:51:16.323Z
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
CC BY-SA 3.0
2012-07-19T01:26:02.210Z
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
CC BY-SA 3.0
2012-10-01T14:18:35.300Z
Your comment is contradictory to your question where you count “PCP(0, 0) = P” as a PCP characterization of P.
Tsuyoshi Ito
<cc.complexity-theory><complexity-classes><pcp>
Interesting PCP characterization of classes smaller than P?
argentpepper
# Interesting PCP characterization of classes smaller than P?

(Asked by: username_0 on 2012-07-18)

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?

**Tags:** cc.complexity-theory, complexity-classes, pcp
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: Your comment is contradictory to your question where you count “PCP(0, 0) = P” as a PCP characterization of P.  

---

## 0 answers

