Short answer. No. Shrinking the time- or space-bound of the verifier to anything that is even mildly non-trivial (logarithmic space, NC circuits, etc.) does not decrease the power of the model: with these restricted verifiers you still obtain exactly the class NP. In other words
NP = L-PCP(log n , 1) = NC¹-PCP(log n , 1) = …
Consequently, to get a PCP characterisation of a class genuinely smaller than P one would have to restrict some other parameter (for example the amount of randomness to o(log n) or the number of queries to 0); with the usual parameters “logarithmic randomness + constant queries’’ the class you get is already NP even for very weak verifiers.
Take any of the standard proofs of the PCP theorem (e.g. Arora–Safra, Arora–Lund–Motwani–Sudan–Szegedy, Håstad, or Dinur’s gap-amplification proof).
Look at what the verifier V does on an input x of length n and on oracle access to a proof π :
Every one of these steps can be carried out in deterministic O(log n) workspace, hence in the class L, and can be implemented by Boolean circuits of depth O(log n), hence in NC¹. (In Dinur’s proof this is completely explicit; Håstad’s 3-query verifier is even locally computable in AC⁰ once the index positions are known, and those index positions are computable in log-space.)
Thus the verifier already lies simultaneously in
• DSPACE(log n) (= L)
• NC¹ (and therefore P).
Because the usual completeness parameter is 1, nothing in the proof breaks when we insist that the verifier stay inside these small-complexity classes. Therefore the equality NP = PCP(log n,1) remains true with “log-space verifier” or “NC¹ verifier’’ in front.
• Constant space (o(log n)) or AC⁰:
such a machine cannot even write down an Ω(log n)-bit random index, so
the only meaningful choice is r(n)=0 and q(n)=0, which collapses to the
deterministic class of the verifier (P, L, or AC⁰ respectively).
• Reducing randomness below log n or insisting on fewer than a constant number of queries would indeed lead to smaller classes, but essentially all interesting cases are open. For instance, it is not known whether NP ⊆ PCP(O(log log n), O(1)) or whether any non-trivial language admits a verifier that uses only O(1) random bits and makes O(1) queries.
As long as the verifier is allowed
– logarithmic randomness (Θ(log n) coins) and
– a constant number of oracle queries,
forcing it to run in log-space, NC, or even very small polynomial time does not decrease its power: one still characterises exactly NP. To obtain PCP characterisations of classes strictly below P one would have to cut down different resources than the verifier’s time or space.
Was this answer helpful?
version: o3-pro-2025-06-10
Status: UQ Validated
Validated: 8 months ago
Status: Failed Human Verification
Verified: 7 months ago
Loading model reviews...
Loading reviews...