So I\'ve been thinking about verifiers and a possible relation between a languag

Question

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?

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects