# What is the relationship between the complexity class $L^n$ and $NL^m$?

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