The question asks whether we can obtain interesting (non-trivial) PCP characterizations for complexity classes smaller than P by restricting the verifier's resources (e.g., to logarithmic space or NC circuits). Here's the analysis:

Key Observations:

1. Standard PCP Context: The PCP theorem characterizes NP using polynomial-time verifiers with logarithmic proof queries (NP = PCP(log n, 1))...

Short answer: Restricting the verifier to be “much weaker” than polynomial time—e.g., logspace or NC—does not lead to a PCP characterization of a class smaller than P. In fact, one can obtain PCP theorems for NP with verifiers that use only logarithmic space and that are highly parallel (NC), so the characterized class remains NP. To get below P in a meaningful way you have to change the model (e....

Below is a “high‐level’’ summary of why one does ​not​ get any new “in‐between–P’’ classes by simply insisting that the PCP–verifier be, say, log‐space or NC‐circuit. Roughly speaking, as long as you allow the verifier any nonzero amount of randomness ​and​ at least one query, you recover NP; the only way to drop below P is to kill off randomness or queries altogether, in which case the PCP‐model...

Let us write
PCP(_{\mathcal{C}}(r,q)) for the class of languages that have a probabilistically-checkable proof whose verifier

• uses at most (r(n)) random bits,
• looks at at most (q(n)) places of the proof, and
• belongs to the machine class (\mathcal{C}) (det-time/space/circuit class).

The usual PCP theorem is the statement NP = PCP(_{{\sf P}}(\log n ,1)); here the verifier is ...

This is an excellent question about extending PCP characterizations to complexity classes smaller than P by restricting the computational power of the verifier.

Current State of Knowledge

The standard PCP characterizations indeed use polynomial-time verifiers, making P the smallest class naturally characterized this way. However, there has been some work on restricted verifiers:

Logarith...

Excellent question! This gets to the heart of how computational resources interplay in the PCP framework. The standard definition of implicitly assumes a polynomial-time verifier. To talk about classes smaller than , we need to explicitly restrict the verifier's power, just as you suggest.

Let's denote by the class of languages...

PCP Characterizations of Complexity Classes Below P

This is an interesting theoretical question about extending the PCP (Probabilistically Checkable Proofs) framework to characterize complexity classes smaller than P.

What We Know

The standard PCP theorem states that NP = PCP(log n, 1), where the verifier:

• Uses O(log n) random bits
• Reads only a constant number of bits from the proof
• ...

Recall that the PCP theorem says NP = PCP(log n, O(1)). The class P is trivially PCP(0,0) because the verifier can just read the entire proof and decide in polynomial time. But we are interested in classes below P.

We consider two...

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 g...