49

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

Oliphaunt
  • 111
  • 3
argentpepper
  • 2,281
  • 15
  • 27
  • 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. – Or Meir Nov 02 '12 at 00:35
  • 4
    @OrMeir I recently added an explanation of this fact to the Wikipedia article for polyL. – argentpepper Nov 02 '12 at 05:46
  • 14
    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 07 '12 at 12:57
  • 1
    it would seem to be a strengthening of the Hopcroft/Paul/Valiant result 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 Nov 07 '12 at 16:27
  • @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 Nov 12 '12 at 03:49
  • @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 Nov 22 '12 at 13:41
  • 13
    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
  • 3
    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 05 '15 at 19:56
  • Yep. Thanks for the follow-up. :) – Michael Wehar May 06 '15 at 21:13
  • 3
    @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 04:45
  • 1
    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 Oct 30 '15 at 21:51
  • 1
    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 Oct 31 '15 at 14:51
  • 1
    @SajinKoroth: Yes, that would be best, especially if you put your answer as "community wiki". – Michaël Cadilhac Oct 31 '15 at 15:55
  • I wouldn't be too surprised if $L^2 \subseteq P$ implied that $NL^2 \subseteq NP$. What do you think? – Michael Wehar Nov 05 '15 at 17:13
  • 1
    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 Jun 08 '18 at 16:23
  • 1
    @user124864 The idea for this can be found here: https://link.springer.com/chapter/10.1007/3-540-55808-X_33 – Michael Wehar Jun 08 '18 at 16:54
  • 1
    @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 Jun 08 '18 at 17:02
  • 1
    Unrelated observation: I think that $L^2 \subseteq P$ would also imply that $XL \subseteq$ non-uniform $FPT$. – Michael Wehar Jun 08 '18 at 17:09
  • @user124864 We should really connect and chat about these things sometime. :) – Michael Wehar Jun 09 '18 at 04:21

4 Answers4

29

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

Oliphaunt
  • 111
  • 3
Sajin Koroth
  • 566
  • 5
  • 13
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.

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

Oliphaunt
  • 111
  • 3
argentpepper
  • 2,281
  • 15
  • 27
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.

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • 1
    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 03:00
  • 1
    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 03:01
  • What is $\mathsf{\beta_2FOLL}$? – Turbo May 09 '23 at 22:28
  • AC circuits of depth $O(\log \log n)$ that also accept $O(\log^2 n)$ nondeterministic bits. – Joshua Grochow May 09 '23 at 23:12
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", 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$.

Michael Wehar
  • 5,127
  • 1
  • 24
  • 54