A decision problem is in NP if a candidate "yes" can be verified in polynomial time.

Are there decision problems whose "yes" is verified with an algorithm that is P-complete (reducible in logspace)? Are those problems in NP?

If so, can the "yes" be verified in logspace?

I'm told "for every NP language we can find a verifier that uses only logspace."


Every language in NP has a logspace verifier.

Indeed, let $L$ be any language in NP. Therefore, there is a polynomial time machine $T$ and a polynomial $p$ such that $x \in L$ iff some string $y$ of size at most $p(|x|)$ makes $T(x,y)$ accept.

While the witness $y$ may be hard to check, we can make help a logspace machine verify it by including the transcript of the accepting computation. We construct another machine $T'$ which accepts a new witness $z$. The witness $z$ consists of a sequence of configurations of the machine $T$, starting with an initial configuration encoding $x$ and $y$, and ending at an accepting configuration. Since each configuration has polynomial length, a logspace machine can verify that $z$ indeed consists of a valid sequence of configurations.

  • $\begingroup$ When T is a verifier we can design it so that it only accepts valid certificates y. But when T (or its sequence of states) is part of a witness z, it can be anything and T' then needs to check that T is not some random but valid sequence that accepts a bogus certificate y. Can T' be designed in that way? $\endgroup$ – Albert Hendriks May 9 '20 at 16:17
  • $\begingroup$ The machine $T$ is fixed ahead of time. It is hard-coded inside $T’$. $\endgroup$ – Yuval Filmus May 9 '20 at 16:24

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.