# Are there NP languages whose verification is P-complete?

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?

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.
• The machine $T$ is fixed ahead of time. It is hard-coded inside $T’$. – Yuval Filmus May 9 '20 at 16:24