<p>Log-space guarantees polynomial time, since there are at most $2^{O(\log n)} = \operatorname{poly}(n)$ configurations of a given log-space Turing machine.  The complete problems of Undirected Reach and Directed Reach (for L and NL, respectively) are very "nice" to think about.</p>

<p>Note that your definition of PolyL also gives PolyL = NPolyL, by Savitch's theorem, since $\text{NSPACE}[\log^k n] \subseteq \text{SPACE}[\log^{2k}n]$.</p>

<p>When polylog space is concerned, work has been done to consider polylog-space with simultaneous polynomial time, giving the SC hierarchy: $\text{SC}^k = \text{TISP}[\operatorname{poly}(n), \log^k n]$.  </p>

CC BY-SA 2.5
2010-12-02T02:04:58.813Z
If we use polylog reductions instead, will reachability become a complete problem for $\mathsf{polyL}$? (I do think so, by the same reachability method proving reachability an $\mathsf{NL}$-complete problem) If so, $\mathsf{polyL}$ is still "nice" in some sence.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-02T02:22:21.770Z
If you use polylog reductions for PolyL problems, the language $\{1\}$ is PolyL-complete.
Derrick Stolee
CC BY-SA 2.5
2010-12-02T05:54:24.197Z
You are right, sorry for the stupid question :(
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-01T18:33:08.720Z
2010-12-01T18:33:08.720Z
Derrick Stolee
<p>One issue is that it is unknown whether $\text{SPACE}[\log^2 n] \subseteq \text{P}$. That pretty much kills the notion of efficiency. On another note, determining if the intersection of the languages recognized by $\log^{k-1}(n)$ automata is non-empty is $\text{NSPACE}$$[\log^k n]$$\text{-complete}$ under logspace reductions <a href="http://www.springerlink.com/content/q270n64140737108/">[Lange-Rossmanith]</a>. Perhaps there are some similar problems for deterministic polylog-space.</p>

<p>The class $\text{PLOSS} = \bigcup_k \text{TISP}[n^k, k \, \log^2 n]$ has been studied in the past. <a href="http://portal.acm.org/citation.cfm?id=800135.804426">[Cook]</a> proved that $\text{DCFL} \subseteq \text{PLOSS}$. As noted by Derrick Stolee, this class is now known as $\text{SC}^2$ and has been generalized to $\text{SC}^k$. More informations <a href="http://en.wikipedia.org/wiki/SC_%28complexity%29">here</a>.</p>

CC BY-SA 2.5
2010-12-01T18:36:12.173Z
Can we use $\mathsf{QuasiP} = \bigcup_{k \geq 0} \mathsf{TIME}[2^{\log^k n}]$ instead of $\mathsf{P}$?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-01T18:37:52.257Z
Is this a known open problem? Could you provide a reference?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-01T19:48:36.767Z
Your PLOSS class is the same as $\text{SC}^2$ in modern terms.  SC stands for "Steve's Class" probably for that result of Cook's that you cite.
Derrick Stolee
CC BY-SA 2.5
2010-12-01T23:07:13.590Z
Note that SC was named by Nick Pippenger, in an allegedly reciprocal arrangement with Steve Cook to name NC after him :)
Suresh Venkat
CC BY-SA 2.5
2010-12-02T01:42:26.657Z
so is this correct: since $\mathsf{P}$ is a MUCH important class representing efficiency, so instead of changing from $\mathsf{P}$ to $\mathsf{QuasiP}$ in order to fit $\mathsf{polyL}$, we use $\mathsf{L}$ to fit $\mathsf{P}$? Then, if at some time the relation $\mathsf{SPACE}[\log^k n] \subseteq \mathsf{P}$ is proved for some $k$, will the class $\mathsf{L^k}$ become more important?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-01T18:32:35.617Z
2010-12-02T13:54:37.007Z
2010-12-02T13:54:37.007Z
Michael Blondin
<p>I think all the other answers are very good; I'll try to give a different perspective on the issue. </p>

<p>I don't know how well P models "efficient" computation in the real world, but we like the class because of its nice closure properties and other mathematical reasons. Similarly, L is also a nice class due to some of the aforementioned reasons.</p>

<p>However, as you commented, if we relax our definition of "efficient" to quasi-polynomial time, then PolyL is also efficient. We could discuss complexity theory where we allow classes defined with a logarithmic bound on some resource to use polylog resources instead. Correspondingly, we would also relax our definitions of NC, NL, etc. to allow quasi-polynomial size circuits instead. If we do this, NC<sub>1</sub>, L, NL and NC all coincide with the class PolyL. In this sense PolyL is a robust class since many natural classes coincide with it. For more information on complexity theory with log -> polylog and polynomial -> quasi-polynomial, see 
<a href="http://dx.doi.org/10.1109/SCT.1992.215383">Quasipolynomial size circuit classes</a> by Barrington.</p>

<p>Another reason to study polyL or similar classes like quasi-AC<sub>0</sub> is that while an oracle separation between (say) ParityP and PH implies that PARITY is not contained in AC<sub>0</sub>, the reverse implication is not known to be true. On the other hand, PARITY is not contained in quasi-AC<sub>0</sub> if and only if there is an oracle separation between ParityP and PH. Similarly, the classes quasi-TC<sub>0</sub> and quasi-AC<sub>0</sub> are different if and only if there is an oracle separation between CH and PH. So the usual complexity classes like PH, ModPH, CH, etc. when scaled down by an exponential to prove oracle results turn into quasi-polynomial versions of the usual classes AC<sub>0</sub>, ACC<sub>0</sub> and TC<sub>0</sub> respectively. Similarly, the argument used in Toda's theorem (PH is contained in P<sup>PP</sup>) can be used to show that quasi-AC<sub>0</sub> is contained in depth-3 quasi-TC<sub>0</sub>. (I don't know if the same conclusion is known for the usual versions of these classes. I have seen this listed as an open problem in some papers.)</p>

CC BY-SA 2.5
2010-12-02T06:08:43.407Z
Your answer really helps, thank you for sharing your opinion. I'm amazed that Quasi-something have been studied A LOT!!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-02T05:04:04.327Z
2010-12-02T05:04:04.327Z
Robin Kothari
<p>The smallest class containing linear time and closed under subroutines is P. The smallest class containing log space and closed under subroutines is still log space. So P and L are the smallest robust classes for time and space respectively which is why they feel right for modeling efficient computation. </p>

CC BY-SA 2.5
2010-12-02T02:26:26.337Z
This looks like the best answer to the actual question asked.
Derrick Stolee
CC BY-SA 2.5
2010-12-02T14:56:49.560Z
Among all these good answers, I do think the answer by Lance is the most precise one, and I'll accept it. But still many thanks to every thoughtful answers!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-02T15:17:26.497Z
Also, it is an open problem whether P=L.
didest
CC BY-SA 2.5
2010-12-02T00:44:09.580Z
2010-12-02T00:44:09.580Z
Lance Fortnow
<p>This might be a subjective question rather than one with a concrete answer, but anyway.</p>

<p>In complexity theory we study the notion of efficient computations. There are classes like $\mathsf{P}$ stands for <a href="http://en.wikipedia.org/wiki/P_%28complexity%29">polynomial time</a>, and $\mathsf{L}$ stands for <a href="http://en.wikipedia.org/wiki/L_%28complexity%29">log space</a>. Both of them are considered to be represented as a kind of "efficiency", and they capture the difficulties of some problems pretty well.</p>

<p>But there is a difference between $\mathsf{P}$ and $\mathsf{L}$: while the polynomial time, $\mathsf{P}$, is defined as the union of problems which runs in $O(n^k)$ time for any constant $k$, that is,</p>

<p>$\mathsf{P} = \bigcup_{k \geq 0} \mathsf{TIME[n^k]}$,</p>

<p>the log space, $\mathsf{L}$, is defined as $\mathsf{SPACE[\log n]}$. If we mimics the definition of $\mathsf{P}$, it becomes</p>

<p>$\mathsf{PolyL} = \bigcup_{k \geq 0} \mathsf{SPACE[\log^k n]}$,</p>

<p>where $\mathsf{PolyL}$ is called the class of <strong><a href="http://en.wikipedia.org/wiki/PolyL">polylog space</a></strong>.
My question is:</p>

<blockquote>
  <p>Why do we use log space as the notion of efficient computation, instead of polylog space?</p>
</blockquote>

<p>One main issue may be about the complete problem sets. Under logspace many-one reductions, both $\mathsf{P}$ and $\mathsf{L}$ have complete problems. In contrast, if $\mathsf{PolyL}$ has complete problems under such reductions, then we would have contradict to the space hierarchy theorem. But what if we moved to the polylog reductions?
Can we avoid such problems? In general, if we try our best to fit $\mathsf{PolyL}$ into the notion of efficiency, and (if needed) modify some of the definitions to get every good properties a "nice" class should have, how far can we go?</p>

<blockquote>
  <p>Is there any theoretical and/or practical reasons for using log space instead of polylog space?</p>
</blockquote>

CC BY-SA 2.5
2010-12-01T18:46:06.603Z
It's known that $polyL \ne P$. As far as I'm personally aware, the exact relationship between $P$ and $polyL$ is unclear. As in, it's possible that some problems are solvable in $polyL$ that are not solvable in $P$ *AND* vice versa. (This actually partially speaks your question about why $polyL$ is an odd candidate for a notion of efficient computation.) For some more on $polyL$, you can check out [Papadimitriou's complexity textbook](http://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read/3258#3258), specifically the exercises and discussion at the end of Chapter 16.
Daniel Apon
CC BY-SA 2.5
2010-12-01T18:59:15.467Z
Actually, another quick comment about a minor piece of your overall question: Polylog space reductions won't tell you much about $polyL$, for the same reasons polynomial time reductions don't tell you much about $P$.
Daniel Apon
CC BY-SA 2.5
2010-12-02T02:11:03.507Z
@Daniel Apon: Thank you for mentioning the book, and it is nice :) For the second comment, by the same argument we can use linear reductions instead of polynomial ones to get more informations about $\mathsf{P}$, right?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-02T21:22:39.697Z
Chih Chang: Well, I don't know about linear-time reductions per say, but there *are* other, [interesting notions of reductions](http://www.eecs.berkeley.edu/~virgi/tria-mmult-conf.pdf) that give information about complexity inside $P$.
Daniel Apon
<cc.complexity-theory><space-bounded><big-picture>
Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?
Hsien-Chih Chang 張顯之
# Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

(Asked by: username_0 on 2010-12-01)

This might be a subjective question rather than one with a concrete answer, but anyway.

In complexity theory we study the notion of efficient computations. There are classes like $\mathsf{P}$ stands for [polynomial time](http://en.wikipedia.org/wiki/P_%28complexity%29), and $\mathsf{L}$ stands for [log space](http://en.wikipedia.org/wiki/L_%28complexity%29). Both of them are considered to be represented as a kind of "efficiency", and they capture the difficulties of some problems pretty well.

But there is a difference between $\mathsf{P}$ and $\mathsf{L}$: while the polynomial time, $\mathsf{P}$, is defined as the union of problems which runs in $O(n^k)$ time for any constant $k$, that is,

$\mathsf{P} = \bigcup\_{k \geq 0} \mathsf{TIME[n^k]}$,

the log space, $\mathsf{L}$, is defined as $\mathsf{SPACE[\log n]}$. If we mimics the definition of $\mathsf{P}$, it becomes

$\mathsf{PolyL} = \bigcup\_{k \geq 0} \mathsf{SPACE[\log^k n]}$,

where $\mathsf{PolyL}$ is called the class of **[polylog space](http://en.wikipedia.org/wiki/PolyL)**.
My question is:

> Why do we use log space as the notion of efficient computation, instead of polylog space?

One main issue may be about the complete problem sets. Under logspace many-one reductions, both $\mathsf{P}$ and $\mathsf{L}$ have complete problems. In contrast, if $\mathsf{PolyL}$ has complete problems under such reductions, then we would have contradict to the space hierarchy theorem. But what if we moved to the polylog reductions?
Can we avoid such problems? In general, if we try our best to fit $\mathsf{PolyL}$ into the notion of efficiency, and (if needed) modify some of the definitions to get every good properties a "nice" class should have, how far can we go?

> Is there any theoretical and/or practical reasons for using log space instead of polylog space?

**Tags:** cc.complexity-theory, space-bounded, big-picture
> **Comments:**
> **username_1**: It's known that $polyL \ne P$. As far as I'm personally aware, the exact relationship between $P$ and $polyL$ is unclear. As in, it's possible that some problems are solvable in $polyL$ that are not solvable in $P$ *AND* vice versa. (This actually partially speaks your question about why $polyL$ is an odd candidate for a notion of efficient computation.) For some more on $polyL$, you can check out [Papadimitriou's complexity textbook](http://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read/3258#3258), specifically the exercises and discussion at the end of Chapter 16.  
> **username_1**: Actually, another quick comment about a minor piece of your overall question: Polylog space reductions won't tell you much about $polyL$, for the same reasons polynomial time reductions don't tell you much about $P$.  
> **username_0**: @Daniel Apon: Thank you for mentioning the book, and it is nice :) For the second comment, by the same argument we can use linear reductions instead of polynomial ones to get more informations about $\mathsf{P}$, right?  
> **username_1**: Chih Chang: Well, I don't know about linear-time reductions per say, but there *are* other, [interesting notions of reductions](http://www.eecs.berkeley.edu/~virgi/tria-mmult-conf.pdf) that give information about complexity inside $P$.  

---

## 4 answers

### Answer by username_7 on 2010-12-02. Score: 60 | Accepted answer

The smallest class containing linear time and closed under subroutines is P. The smallest class containing log space and closed under subroutines is still log space. So P and L are the smallest robust classes for time and space respectively which is why they feel right for modeling efficient computation.

> **Comments:**
> **username_2**: This looks like the best answer to the actual question asked.  
> **username_0**: Among all these good answers, I do think the answer by Lance is the most precise one, and I'll accept it. But still many thanks to every thoughtful answers!  
> **username_8**: Also, it is an open problem whether P=L.  

---

### Answer by username_3 on 2010-12-01. Score: 26

One issue is that it is unknown whether $\text{SPACE}[\log^2 n] \subseteq \text{P}$. That pretty much kills the notion of efficiency. On another note, determining if the intersection of the languages recognized by $\log^{k-1}(n)$ automata is non-empty is $\text{NSPACE}$$[\log^k n]$$\text{-complete}$ under logspace reductions [[Lange-Rossmanith]](http://www.springerlink.com/content/q270n64140737108/). Perhaps there are some similar problems for deterministic polylog-space.

The class $\text{PLOSS} = \bigcup\_k \text{TISP}[n^k, k \, \log^2 n]$ has been studied in the past. [[Cook]](http://portal.acm.org/citation.cfm?id=800135.804426) proved that $\text{DCFL} \subseteq \text{PLOSS}$. As noted by Derrick Stolee, this class is now known as $\text{SC}^2$ and has been generalized to $\text{SC}^k$. More informations [here](http://en.wikipedia.org/wiki/SC_%28complexity%29).

> **Comments:**
> **username_0**: Can we use $\mathsf{QuasiP} = \bigcup_{k \geq 0} \mathsf{TIME}[2^{\log^k n}]$ instead of $\mathsf{P}$?  
> **username_4**: Is this a known open problem? Could you provide a reference?  
> **username_2**: Your PLOSS class is the same as $\text{SC}^2$ in modern terms.  SC stands for "Steve's Class" probably for that result of Cook's that you cite.  
> **username_5**: Note that SC was named by Nick Pippenger, in an allegedly reciprocal arrangement with Steve Cook to name NC after him :)  
> **username_0**: so is this correct: since $\mathsf{P}$ is a MUCH important class representing efficiency, so instead of changing from $\mathsf{P}$ to $\mathsf{QuasiP}$ in order to fit $\mathsf{polyL}$, we use $\mathsf{L}$ to fit $\mathsf{P}$? Then, if at some time the relation $\mathsf{SPACE}[\log^k n] \subseteq \mathsf{P}$ is proved for some $k$, will the class $\mathsf{L^k}$ become more important?  

---

### Answer by username_2 on 2010-12-01. Score: 20

Log-space guarantees polynomial time, since there are at most $2^{O(\log n)} = \operatorname{poly}(n)$ configurations of a given log-space Turing machine. The complete problems of Undirected Reach and Directed Reach (for L and NL, respectively) are very "nice" to think about.

Note that your definition of PolyL also gives PolyL = NPolyL, by Savitch's theorem, since $\text{NSPACE}[\log^k n] \subseteq \text{SPACE}[\log^{2k}n]$.

When polylog space is concerned, work has been done to consider polylog-space with simultaneous polynomial time, giving the SC hierarchy: $\text{SC}^k = \text{TISP}[\operatorname{poly}(n), \log^k n]$.

> **Comments:**
> **username_0**: If we use polylog reductions instead, will reachability become a complete problem for $\mathsf{polyL}$? (I do think so, by the same reachability method proving reachability an $\mathsf{NL}$-complete problem) If so, $\mathsf{polyL}$ is still "nice" in some sence.  
> **username_2**: If you use polylog reductions for PolyL problems, the language $\{1\}$ is PolyL-complete.  
> **username_0**: You are right, sorry for the stupid question :(  

---

### Answer by username_6 on 2010-12-02. Score: 14

I think all the other answers are very good; I'll try to give a different perspective on the issue.

I don't know how well P models "efficient" computation in the real world, but we like the class because of its nice closure properties and other mathematical reasons. Similarly, L is also a nice class due to some of the aforementioned reasons.

However, as you commented, if we relax our definition of "efficient" to quasi-polynomial time, then PolyL is also efficient. We could discuss complexity theory where we allow classes defined with a logarithmic bound on some resource to use polylog resources instead. Correspondingly, we would also relax our definitions of NC, NL, etc. to allow quasi-polynomial size circuits instead. If we do this, NC1, L, NL and NC all coincide with the class PolyL. In this sense PolyL is a robust class since many natural classes coincide with it. For more information on complexity theory with log -> polylog and polynomial -> quasi-polynomial, see
[Quasipolynomial size circuit classes](http://dx.doi.org/10.1109/SCT.1992.215383) by Barrington.

Another reason to study polyL or similar classes like quasi-AC0 is that while an oracle separation between (say) ParityP and PH implies that PARITY is not contained in AC0, the reverse implication is not known to be true. On the other hand, PARITY is not contained in quasi-AC0 if and only if there is an oracle separation between ParityP and PH. Similarly, the classes quasi-TC0 and quasi-AC0 are different if and only if there is an oracle separation between CH and PH. So the usual complexity classes like PH, ModPH, CH, etc. when scaled down by an exponential to prove oracle results turn into quasi-polynomial versions of the usual classes AC0, ACC0 and TC0 respectively. Similarly, the argument used in Toda's theorem (PH is contained in PPP) can be used to show that quasi-AC0 is contained in depth-3 quasi-TC0. (I don't know if the same conclusion is known for the usual versions of these classes. I have seen this listed as an open problem in some papers.)

> **Comments:**
> **username_0**: Your answer really helps, thank you for sharing your opinion. I'm amazed that Quasi-something have been studied A LOT!!  

---

