We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ $\mathsf{polyL}$, where $\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n)$. We also know that $\mathsf{polyL} \neq \mathsf{P}$ because the latter has complete problems under logarithmic space many-one reductions while the former does not (due to the space hierarchy theorem). In order to understand the relationship between $\mathsf{polyL}$ and $\mathsf{P}$, it may help to first understand the relationship between $\mathsf{L}^2$ and $\mathsf{P}$.

What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

What about the stronger $\mathsf{L}^{k} \subseteq \mathsf{P}$ for $k>2$, or the weaker $\mathsf{L}^{1 + \epsilon} \subseteq \mathsf{P}$ for $\epsilon > 0$?

  • 4
    $\begingroup$ @OrMeir I recently added an explanation of this fact to the Wikipedia article for polyL. $\endgroup$ Commented Nov 2, 2012 at 5:46
  • 14
    $\begingroup$ I think the following is an obvious consequence, and especially not a surprising one : $L^2 \subseteq P$ would imply that $L \neq P$, because otherwise it would contradict the space hierarchy $L \subsetneq L^2$. $\endgroup$ Commented Nov 7, 2012 at 12:57
  • 13
    $\begingroup$ Neat question! I think it's definitely worth a bounty. Btw, here is a simple observation, if $L^2 \subseteq P$, then $DSPACE(n) \subseteq DTIME(2^{O(\sqrt{n})})$. Therefore, we have a more efficient algorithm for CNF-SAT and we refute ETH (Exponential time hypothesis). $\endgroup$ Commented Feb 24, 2015 at 18:23
  • 3
    $\begingroup$ Following @MichaelWehar's comment, the implication follows from a standard padding argument that extends to weaker hypotheses: if $L^{1 + \epsilon}$ is in $P$, then any problem that can be solved in linear space (including the satisfiability problem), can be solved in time $2^{O\left(n^{\frac{1}{1 + \epsilon}}\right)}$. $\endgroup$ Commented May 5, 2015 at 19:56
  • 3
    $\begingroup$ @SajinKoroth: I think your comment, as well as Michael Wehar's (and argentpepper's follow-up) should be answers... $\endgroup$ Commented Aug 15, 2015 at 4:45

4 Answers 4


The following is an obvious consequence: $\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ would imply $\mathsf{L} \subsetneq \mathsf{P}$ and therefore $\mathsf{L} \neq \mathsf{P}$.

By the space hierarchy theorem, $\forall \epsilon > 0: \mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon}$ . If $\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ then $\mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$.

  • $\begingroup$ Small footnote: If $P \neq L$, then we have $P \neq NL$ or $NL \neq L$. $\endgroup$ Commented Jan 20, 2018 at 1:57

$ \newcommand{\DSPACE}{\mathsf{DSPACE}} \newcommand{\L}{\mathsf{L}} \newcommand{\P}{\mathsf{P}} \newcommand{\DTIME}{\mathsf{DTIME}} $

$\L^2 \subseteq \P$ would refute the Exponential Time Hypothesis.

If $\L^2 \subseteq \P$ then by a padding argument $\DSPACE(n) \subseteq \DTIME(2^{O(\sqrt n)})$. This means that the satisfiability problem $\mathsf{SAT} \in \DSPACE(n)$ can be decided in $2^{o(n)}$ steps, refuting the Exponential Time Hypothesis.

More generally, $\DSPACE(\log^{k} n) \subseteq \P$ for $k\geq1$ implies $\mathsf{SAT} \in \DSPACE(n) \subseteq \DTIME(2^{O(n^{\frac{1}{k}})})$.

(This answer is expanded from a comment by @MichaelWehar.)

  • $\begingroup$ Thank you for expanding on the comment! I appreciate it. :) $\endgroup$ Commented Nov 5, 2015 at 4:13
  • 1
    $\begingroup$ In addition, the last hypothesis also implies that $QBF$ is in DSPACE($n$) $\subseteq$ DTIME($2^{O(n^{\frac{1}{k}})}$). $\endgroup$ Commented Dec 9, 2015 at 5:16

Group isomorphism (with groups given as multiplication tables) would be in P. Lipton, Snyder, and Zalcstein showed this problem is in $\mathsf{L}^2$, but it is still open whether it is in P. The best current upper bound is $n^{O(\log n)}$-time, and because it reduces to graph isomorphism, stands as a significant obstacle to putting graph iso into P.

Makes me wonder what other natural and important problems this would apply to: that is, in $\mathsf{L}^2$ but with their best known time upper bound quasi-polynomial.

  • 1
    $\begingroup$ More specifically, the more general problem of quasigroup isomorphism is in $\beta_2 \mathsf{FOLL}$, which is a subclass of $\mathsf{L}^2$. $\endgroup$ Commented Jan 25, 2018 at 3:00
  • 1
    $\begingroup$ Also, the group rank problem (given a finite group G as a multiplication table and an integer k, does G have a generating set of cardinality k?) also has this property. The algorithm is just a search over the subsets of G of cardinality k but uses two important facts: (1) each finite group has a generating set of logarithmic size and (2) subgroup membership is in $\mathsf{SL}$, which equals $\mathsf{L}$. $\endgroup$ Commented Jan 25, 2018 at 3:01
  • $\begingroup$ What is $\mathsf{\beta_2FOLL}$? $\endgroup$
    – Turbo
    Commented May 9, 2023 at 22:28
  • $\begingroup$ AC circuits of depth $O(\log \log n)$ that also accept $O(\log^2 n)$ nondeterministic bits. $\endgroup$ Commented May 9, 2023 at 23:12

Claim: If $L^k \subseteq P$ for some $k > 2$, then $P \neq \log(CFL)$ and $P \neq NL$.

Suppose that $L^k \subseteq P$ for some $k > 2$.

From "Memory bounds for recognition of context-free and context-sensitive languages", we know that $CFL \subseteq DSPACE(\log^2(n))$. By the space hierarchy theorem, we know that $DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n))$.

Therefore, we get $\log(CFL) \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$.

Also, by Savitch's Theorem, we know that $NL \subseteq L^2$. Therefore, we get $NL \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.