patternMinor
The class of languages that can be certified in a small amount of space
Viewed 0 times
canthespacelanguagesamountthatsmallcertifiedclass
Problem
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$?
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$?
Solution
(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".)
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".)
Context
StackExchange Computer Science Q#60774, answer score: 3
Revisions (0)
No revisions yet.