2
$\begingroup$

So I've been thinking about verifiers and a possible relation between a language's class and it's verifier complexity. From the book, "NP is the class of languages that have polynomial time verifiers". Is there an analog statement that can be said about a P-class verification complexity? Because P is a subset of NP, I understand that the statement of NP still applies to P. Still, my intuition is that there is something more that can be said about a verifier for P that relates to oracles. Is there more that can be said?

$\endgroup$
4
$\begingroup$

It is an open question whether $P=NL$, where $NL$ is the class of languages verifiable in logarithmic space. It is known that $NL \subseteq P$ (why?), and strongly suspected that $NL \neq P$, but we don't know for sure.

$\endgroup$

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.