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

  • $\begingroup$ For $NP$, the verifier is feeded not only with the certificate $y$, but also with the input $x$ of the original problem. If you want a similar logarithmic time verifier for $P$ then there is not enough time to read the whole original input. You should "switch" to logarithmic space verifiers. See class NL on Complexity Zoo $\endgroup$ – Vor Dec 16 '12 at 18:31
  • $\begingroup$ Ah, I see. Silly question, then! $\endgroup$ – Chris Pressey Dec 16 '12 at 18:35
  • $\begingroup$ silly if you consider logarithmic time, but "open" if you consider the logarithmic space, because the analogy with NP are only apparent, indeed $NL \subseteq P$ :-) $\endgroup$ – Vor Dec 16 '12 at 18:41

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.