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

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

• @OrMeir I recently added an explanation of this fact to the Wikipedia article for polyL. – argentpepper Nov 2 '12 at 5:46
• 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$. – Sajin Koroth Nov 7 '12 at 12:57
• 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). – Michael Wehar Feb 24 '15 at 18:23
• 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)}$. – argentpepper May 5 '15 at 19:56
• @SajinKoroth: I think your comment, as well as Michael Wehar's (and argentpepper's follow-up) should be answers... – Joshua Grochow Aug 15 '15 at 4:45

## 4 Answers

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

• Small footnote: If $P \neq L$, then we have $P \neq NL$ or $NL \neq L$. – Michael Wehar Jan 20 '18 at 1:57


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

• Thank you for expanding on the comment! I appreciate it. :) – Michael Wehar Nov 5 '15 at 4:13
• In addition, the last hypothesis also implies that $QBF$ is in DSPACE($n$) $\subseteq$ DTIME($2^{O(n^{\frac{1}{k}})}$). – Michael Wehar Dec 9 '15 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.

• More specifically, the more general problem of quasigroup isomorphism is in $\beta_2 \mathsf{FOLL}$, which is a subclass of $\mathsf{L}^2$. – argentpepper Jan 25 '18 at 3:00
• 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}$. – argentpepper Jan 25 '18 at 3:01

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