Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
