<p>$
\newcommand{\DSPACE}{\mathsf{DSPACE}}
\newcommand{\L}{\mathsf{L}}
\newcommand{\P}{\mathsf{P}}
\newcommand{\DTIME}{\mathsf{DTIME}}
$</p>

<p>$\L^2 \subseteq \P$ would refute the <a href="https://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="noreferrer">Exponential Time Hypothesis</a>.</p>

<p>If $\L^2 \subseteq \P$ 
then by a <a href="https://en.wikipedia.org/wiki/Padding_argument" rel="noreferrer">padding argument</a>
$\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.</p>

<p>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}})})$.</p>

<p>(This answer is expanded from a comment by @MichaelWehar.)</p>

CC BY-SA 3.0
2015-11-05T04:13:17.693Z
Thank you for expanding on the comment!  I appreciate it.  :)
Michael Wehar
CC BY-SA 3.0
2015-12-09T05:16:56.847Z
In addition, the last hypothesis also implies that $QBF$ is in DSPACE($n$) $\subseteq$ DTIME($2^{O(n^{\frac{1}{k}})}$).
Michael Wehar
CC BY-SA 3.0
2015-11-02T16:39:57.697Z
2018-01-14T00:37:13.947Z
2018-01-14T00:37:13.947Z
argentpepper
<p>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.</p>

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

CC BY-SA 3.0
2018-01-25T03:00:05.460Z
More specifically, the more general problem of quasigroup isomorphism is in $\beta_2 \mathsf{FOLL}$, which is a subclass of $\mathsf{L}^2$.
argentpepper
CC BY-SA 3.0
2018-01-25T03:01:36.150Z
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
CC BY-SA 4.0
2023-05-09T22:28:34.107Z
What is $\mathsf{\beta_2FOLL}$?
Turbo
CC BY-SA 4.0
2023-05-09T23:12:59.937Z
AC circuits of depth $O(\log \log n)$ that also accept $O(\log^2 n)$ nondeterministic bits.
Joshua Grochow
CC BY-SA 3.0
2018-01-19T22:31:34.940Z
2018-01-19T22:31:34.940Z
Joshua Grochow
<p><strong>Claim:</strong> If $L^k \subseteq P$ for some $k &gt; 2$, then $P \neq \log(CFL)$ and $P \neq NL$.</p>

<blockquote>
  <p>Suppose that $L^k \subseteq P$ for some $k &gt; 2$.</p>
  
  <p>From "<a href="https://dl.acm.org/citation.cfm?id=1687178" rel="nofollow noreferrer">Memory bounds for recognition of context-free and context-sensitive languages</a>", 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))$.</p>
  
  <p>Therefore, we get $\log(CFL) \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$.</p>
  
  <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$.</p>
</blockquote>

CC BY-SA 3.0
2018-01-20T01:38:12.183Z
2018-01-20T01:53:13.313Z
2018-01-20T01:53:13.313Z
Michael Wehar
<p>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}$.</p>

<p>By the space hierarchy theorem, $\forall \epsilon &gt; 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}$. </p>

CC BY-SA 3.0
2018-01-20T01:57:02.730Z
Small footnote: If $P \neq L$, then we have $P \neq NL$ or $NL \neq L$.
Michael Wehar
CC BY-SA 3.0
2015-10-31T14:48:43.583Z
2018-01-15T17:53:27.073Z
2018-01-15T17:53:27.073Z
Sajin Koroth
<p>We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:P#polyl" rel="noreferrer">$\mathsf{polyL}$</a>, 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}$.</p>

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

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

CC BY-SA 3.0
2012-11-02T00:35:16.820Z
Why doesn't polyL has complete problems under logarithmic space many-one reductions? I don't see why the space hierarchy theorem should be a problem. E.g., the class E (linear-exponential time) has complete problems under linear time reductions despite the time hierarchy theorem.
Or Meir
CC BY-SA 3.0
2012-11-02T05:46:38.483Z
@OrMeir I recently added an explanation of this fact to [the Wikipedia article for polyL](https://en.wikipedia.org/wiki/PolyL).
argentpepper
CC BY-SA 3.0
2012-11-07T12:57:00.687Z
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
CC BY-SA 3.0
2012-11-07T16:27:19.760Z
it would seem to be a strengthening of the [Hopcroft/Paul/Valiant result](http://rjlipton.wordpress.com/2011/01/19/we-believe-a-lot-but-can-prove-little/) which uses "pebbling" arguments. and similar to a "space compression algorithm" but complexity theory seems not to have been studied lots from that perspective, and/or the perspective is difficult (ie not any easier than hard complexity class separations that resist attack)
vzn
CC BY-SA 3.0
2012-11-12T03:49:07.837Z
@SajinKoroth It seems that no one has a better answer than yours, and although you may consider it obvious and unsurprising, it is indeed a correct answer. If you create an official "answer" to the question, I will reward the bounty to you.
argentpepper
CC BY-SA 3.0
2012-11-22T13:41:12.947Z
@argentpepper : I don't think its worthy of the bounty. :), please reserve your bounty points for such interesting questions you are going to ask in the future.
Sajin Koroth
CC BY-SA 3.0
2015-02-24T18:23:24.957Z
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
CC BY-SA 3.0
2015-05-05T19:56:20.457Z
Following @MichaelWehar's comment, the implication follows from a standard [padding argument](https://en.wikipedia.org/wiki/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
CC BY-SA 3.0
2015-05-06T21:13:42.960Z
Yep.  Thanks for the follow-up.  :)
Michael Wehar
CC BY-SA 3.0
2015-08-15T04:45:32.660Z
@SajinKoroth: I think your comment, as well as Michael Wehar's (and argentpepper's follow-up) should be answers...
Joshua Grochow
CC BY-SA 3.0
2015-10-30T21:51:04.827Z
Agreed with Joshua.  This is a satisfactory set of consequences, and one should not have to dive deep into the comment section to get it.  @SajinKoroth, would you mind writing it?
Michaël Cadilhac
CC BY-SA 3.0
2015-10-31T14:51:35.150Z
should I add the answers of Michael Wehar's answer and agent pepper's follow up as part of my answer and cite them ?
Sajin Koroth
CC BY-SA 3.0
2015-10-31T15:55:41.333Z
@SajinKoroth: Yes, that would be best, especially if you put your answer as "community wiki".
Michaël Cadilhac
CC BY-SA 3.0
2015-11-05T17:13:25.787Z
I wouldn't be too surprised if $L^2 \subseteq P$ implied that $NL^2 \subseteq NP$.  What do you think?
Michael Wehar
CC BY-SA 4.0
2018-06-08T16:23:09.547Z
Hi again!!  You can define these seemingly unnatural $L^k$ complete problems from certain $XL$-complete parameterized problems.  There are these parameterized problems (let's denote the parameter by $k$) that are $XL$-complete where if we make $k$ depend on the input size $n$ such that $k = O(\log^{k-1}(n))$, then we obtain a decision problem that is $L^k$-complete.
Michael Wehar
CC BY-SA 4.0
2018-06-08T16:54:02.343Z
@user124864 The idea for this can be found here: https://link.springer.com/chapter/10.1007/3-540-55808-X_33
Michael Wehar
CC BY-SA 4.0
2018-06-08T17:02:09.373Z
@user124864 In regards to your third question, in addition to everything else mentioned here, we would get $P \neq NL$.  But, I can't think of much else.  I'm happy to discuss this with you more if you're interested.  I hope that you have a nice day.  :)
Michael Wehar
CC BY-SA 4.0
2018-06-08T17:09:17.427Z
Unrelated observation: I think that $L^2 \subseteq P$ would also imply that $XL \subseteq$ non-uniform $FPT$.
Michael Wehar
CC BY-SA 4.0
2018-06-09T04:21:41.493Z
@user124864 We should really connect and chat about these things sometime.  :)
Michael Wehar
<cc.complexity-theory><complexity-classes><conditional-results><structural-complexity>
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
argentpepper
# What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

(Asked by: username_0 on 2012-11-01)

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}$](http://qwiki.stanford.edu/index.php/Complexity_Zoo:P#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$?

**Tags:** cc.complexity-theory, complexity-classes, conditional-results, structural-complexity
> **Comments:**
> **username_1**: Why doesn't polyL has complete problems under logarithmic space many-one reductions? I don't see why the space hierarchy theorem should be a problem. E.g., the class E (linear-exponential time) has complete problems under linear time reductions despite the time hierarchy theorem.  
> **username_0**: @OrMeir I recently added an explanation of this fact to [the Wikipedia article for polyL](https://en.wikipedia.org/wiki/PolyL).  
> **username_2**: 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$.  
> **username_3**: it would seem to be a strengthening of the [Hopcroft/Paul/Valiant result](http://rjlipton.wordpress.com/2011/01/19/we-believe-a-lot-but-can-prove-little/) which uses "pebbling" arguments. and similar to a "space compression algorithm" but complexity theory seems not to have been studied lots from that perspective, and/or the perspective is difficult (ie not any easier than hard complexity class separations that resist attack)  
> **username_0**: @SajinKoroth It seems that no one has a better answer than yours, and although you may consider it obvious and unsurprising, it is indeed a correct answer. If you create an official "answer" to the question, I will reward the bounty to you.  
> **username_2**: @argentpepper : I don't think its worthy of the bounty. :), please reserve your bounty points for such interesting questions you are going to ask in the future.  
> **username_4**: 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).  
> **username_0**: Following @MichaelWehar's comment, the implication follows from a standard [padding argument](https://en.wikipedia.org/wiki/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)}$.  
> **username_4**: Yep.  Thanks for the follow-up.  :)  
> **username_5**: @SajinKoroth: I think your comment, as well as Michael Wehar's (and argentpepper's follow-up) should be answers...  
> **username_6**: Agreed with Joshua.  This is a satisfactory set of consequences, and one should not have to dive deep into the comment section to get it.  @SajinKoroth, would you mind writing it?  
> **username_2**: should I add the answers of Michael Wehar's answer and agent pepper's follow up as part of my answer and cite them ?  
> **username_6**: @SajinKoroth: Yes, that would be best, especially if you put your answer as "community wiki".  
> **username_4**: I wouldn't be too surprised if $L^2 \subseteq P$ implied that $NL^2 \subseteq NP$.  What do you think?  
> **username_4**: Hi again!!  You can define these seemingly unnatural $L^k$ complete problems from certain $XL$-complete parameterized problems.  There are these parameterized problems (let's denote the parameter by $k$) that are $XL$-complete where if we make $k$ depend on the input size $n$ such that $k = O(\log^{k-1}(n))$, then we obtain a decision problem that is $L^k$-complete.  
> **username_4**: @user124864 The idea for this can be found here: https://link.springer.com/chapter/10.1007/3-540-55808-X_33  
> **username_4**: @user124864 In regards to your third question, in addition to everything else mentioned here, we would get $P \neq NL$.  But, I can't think of much else.  I'm happy to discuss this with you more if you're interested.  I hope that you have a nice day.  :)  
> **username_4**: Unrelated observation: I think that $L^2 \subseteq P$ would also imply that $XL \subseteq$ non-uniform $FPT$.  
> **username_4**: @user124864 We should really connect and chat about these things sometime.  :)  

---

## 4 answers

### Answer by username_2 on 2015-10-31. Score: 29 | Accepted answer

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

> **Comments:**
> **username_4**: Small footnote: If $P \neq L$, then we have $P \neq NL$ or $NL \neq L$.  

---

### Answer by username_0 on 2015-11-02. Score: 28

$
\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](https://en.wikipedia.org/wiki/Exponential_time_hypothesis).

If $\L^2 \subseteq \P$
then by a [padding argument](https://en.wikipedia.org/wiki/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.)

> **Comments:**
> **username_4**: Thank you for expanding on the comment!  I appreciate it.  :)  
> **username_4**: In addition, the last hypothesis also implies that $QBF$ is in DSPACE($n$) $\subseteq$ DTIME($2^{O(n^{\frac{1}{k}})}$).  

---

### Answer by username_5 on 2018-01-19. Score: 8

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.

> **Comments:**
> **username_0**: More specifically, the more general problem of quasigroup isomorphism is in $\beta_2 \mathsf{FOLL}$, which is a subclass of $\mathsf{L}^2$.  
> **username_0**: 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}$.  
> **username_7**: What is $\mathsf{\beta_2FOLL}$?  
> **username_5**: AC circuits of depth $O(\log \log n)$ that also accept $O(\log^2 n)$ nondeterministic bits.  

---

### Answer by username_4 on 2018-01-20. Score: 2

**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](https://dl.acm.org/citation.cfm?id=1687178)", 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$.


---

