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?

$\endgroup$
  • 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 Jul 18 '12 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 Jul 19 '12 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 Oct 1 '12 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.