48
$\begingroup$

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, and $\mathsf{L}$ stands for log space. 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. 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?

$\endgroup$
  • $\begingroup$ Hsien-Chih, Nice question. $\endgroup$ – Mohammad Al-Turkistany Dec 1 '10 at 18:39
  • 9
    $\begingroup$ 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, specifically the exercises and discussion at the end of Chapter 16. $\endgroup$ – Daniel Apon Dec 1 '10 at 18:46
  • $\begingroup$ 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$. $\endgroup$ – Daniel Apon Dec 1 '10 at 18:59
  • $\begingroup$ @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? $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 2 '10 at 2:11
  • $\begingroup$ Chih Chang: Well, I don't know about linear-time reductions per say, but there are other, interesting notions of reductions that give information about complexity inside $P$. $\endgroup$ – Daniel Apon Dec 2 '10 at 21:22
50
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ This looks like the best answer to the actual question asked. $\endgroup$ – Derrick Stolee Dec 2 '10 at 2:26
  • 1
    $\begingroup$ 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! $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 2 '10 at 14:56
  • 1
    $\begingroup$ Also, it is an open problem whether P=L. $\endgroup$ – Diego de Estrada Dec 2 '10 at 15:17
25
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Can we use $\mathsf{QuasiP} = \bigcup_{k \geq 0} \mathsf{TIME}[2^{\log^k n}]$ instead of $\mathsf{P}$? $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 1 '10 at 18:36
  • $\begingroup$ Is this a known open problem? Could you provide a reference? $\endgroup$ – Mohammad Al-Turkistany Dec 1 '10 at 18:37
  • $\begingroup$ 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. $\endgroup$ – Derrick Stolee Dec 1 '10 at 19:48
  • 5
    $\begingroup$ Note that SC was named by Nick Pippenger, in an allegedly reciprocal arrangement with Steve Cook to name NC after him :) $\endgroup$ – Suresh Venkat Dec 1 '10 at 23:07
  • $\begingroup$ 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? $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 2 '10 at 1:42
20
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 2 '10 at 2:04
  • $\begingroup$ If you use polylog reductions for PolyL problems, the language $\{1\}$ is PolyL-complete. $\endgroup$ – Derrick Stolee Dec 2 '10 at 2:22
  • $\begingroup$ You are right, sorry for the stupid question :( $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 2 '10 at 5:54
13
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Your answer really helps, thank you for sharing your opinion. I'm amazed that Quasi-something have been studied A LOT!! $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 2 '10 at 6:08

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.