Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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, NC₁, 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-AC₀ is that while an oracle separation between (say) ParityP and PH implies that PARITY is not contained in AC₀, the reverse implication is not known to be true. On the other hand, PARITY is not contained in quasi-AC₀ if and only if there is an oracle separation between ParityP and PH. Similarly, the classes quasi-TC₀ and quasi-AC₀ 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₀, ACC₀ and TC₀ respectively. Similarly, the argument used in Toda's theorem (PH is contained in P^PP) can be used to show that quasi-AC₀ is contained in depth-3 quasi-TC₀. (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.)