The space hierarchy theorem shows that $$\mathrm{\mathbf{L}}^{1} \subsetneq \mathrm{\mathbf{L}}^{2} \subsetneq \cdots \subsetneq \mathrm{\mathbf{L}}^{m} \subsetneq \cdots \subsetneq \mathrm{\mathbf{PSPACE}}$$ and $$\mathrm{\mathbf{NL}}^{1} \subsetneq \mathrm{\mathbf{NL}}^{2} \subsetneq \cdots \subsetneq \mathrm{\mathbf{NL}}^{m} \subsetneq \cdots \subsetneq \mathrm{\mathbf{NPSPACE}} = \mathrm{\mathbf{PSPACE}}$$ where $$\mathrm{\mathbf{L}}^{m} = \mathrm{\mathbf{DSPACE}}\left( \log^{m}(n) \right)$$ and $$\mathrm{\mathbf{NL}}^{m} = \mathrm{\mathbf{NSPACE}}\left( \log^{m}(n) \right)$$

Thus, there exists a function $\varphi \colon \mathbb{N}^{+} \mapsto \mathbb{N}^{+}$ such that for every $m \in \mathbb{N}^{+}$,

$$\mathrm{\mathbf{L}}^{\varphi(m)-1} \subset \mathrm{\mathbf{NL}}^{m} \subset \mathrm{\mathbf{L}}^{\varphi(m)} \subsetneq \mathrm{\mathbf{PSPACE}}$$

The Savitch's theorem shows that for every $m \in \mathbb{N}^{+}$, $$\mathrm{\mathbf{L}}^{m} \subset \mathrm{\mathbf{NL}}^{m} \subset \mathrm{\mathbf{L}}^{2m}$$

Now, we know that $m+1 \leq \varphi(m) \leq 2m$ and $\varphi(1) = 2$.

Can we find $\varphi$ ? Is it an open problem or not?


It is not known whether $\mathsf{L} = \mathsf{NL}$, and this is a famous open question. More generally, I believe that no better bound than $\phi(m) \leq 2m$ is known for any value of $m$, nor is this bound known to be optimal for any value of $m$.

| 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.