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$ – argentpepper Nov 2 '12 at 5:46
  • 13
    $\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$ – Sajin Koroth Nov 7 '12 at 12:57
  • 12
    $\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$ – Michael Wehar Feb 24 '15 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$ – argentpepper May 5 '15 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$ – Joshua Grochow Aug 15 '15 at 4:45

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$ – Michael Wehar Jan 20 '18 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$ – Michael Wehar Nov 5 '15 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$ – 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.

  • 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$ – argentpepper Jan 25 '18 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$ – 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$.


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.