Are any problems in P known to have logarithmic-time-verifiable certificates?

Question

Problems in NP have certificates which can be verified in polynomial time.

It seems conceivable that there could be problems in P which have certificates which can be verified in logarithmic time. (Such certificates would also have to be logarithmic in size, naturally.)

However, it is also conceivable that there are no such problems. I've tried to come up with examples, but none of them have worked out so far.

Have problems like this been studied and shown to exist (or not exist)?

I can't seem to find a complexity class that would describe them in the Complexity Zoo, although it's certainly possible that there's one there and I'm just having a hard time identifying it. (L and LOG usually refer to space, and neither LH nor NLOG looks like it necessarily captures the idea.)

Answer 1

The question here is that in the certificate definition of $\mathsf{NP}$, what is more important is the size of the certificate (in the size of the input), the complexity class that the certificate verifier belongs too is less important. In fact you can take the verifier to be in $\mathsf{AC^0}$ as long as the size of the certificates are polynomial in the size of the input and you will still get the whole problems in $\mathsf{NP}$. $\mathsf{AC^0}$ is a very small complexity class that is included in almost every complexity class you have heard of.

To obtain smaller classes you also need to restrict the way the certificate verifier accesses the certificate. One kind of restriction that is considered is restricting the number of times the verifier can read the input using a log-space verifier. Something similar may work to capture $\mathsf{P}$, but just capturing it in this way is not interesting. The certificate definition should be nice and interesting so that it would give us some insight about $\mathsf{P}$. The certificate definition of $\mathsf{NP}$ is interesting because it is an exceptionally nice, it is even more intuitive than the original definition using non-intuitive non-deterministic machines. It allows us to cast the question regarding $\mathsf{P}$ vs. $\mathsf{NP}$ as "efficient solving vs. efficient verifying". Just having a certificate definition by itself is not very interesting.