NP can be characterized in two different ways, one of them is that it's the class of languages that can be certified by a witness in a polynomial time.

I wonder, if we consider the same notion but with space considerations to get a class $X$, Is such a class known to be of any importance? Why?

To be more precise, $L\in X$ iff there exists a TM $M$ s.t.

$\forall x\in \{0,1\}^* (x\in L \iff \exists u \in \{0,1\}^{p(n)}$ s.t. $M(x,u)=1$ s.t. $M$ uses space bounded by a polynomial $P$.

Clearly, NP$\subset$ X. Is there any interesting thing that we can know about $X$?


(Note that X is not known to differ from NP.) ​ Yes - X is equal to PSPACE. ​ In fact, one gets that from just brute force, rather than needing Savitch's theorem.

You might also be interested in NL, which is only known to satisfy
L ​ $\subseteq$ ​ NL ​ $\subseteq$ ​ coNLOGLOGTIME-uniform SAC1 ​ ​ .

(Note that, to get a certificate characterization of NL, we probably must
"restrict the verifier to have one-way access to the certificate".)

| cite | improve this answer | |

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.