20
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Jul 18, 2012 at 21:51
  • 10
    $\begingroup$ 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. $\endgroup$
    – argentpepper
    Commented Jul 19, 2012 at 1:26
  • 2
    $\begingroup$ Your comment is contradictory to your question where you count “PCP(0, 0) = P” as a PCP characterization of P. $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 1, 2012 at 14:18

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.