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?
Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?
cc.complexity theory;space bounded;big picture
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. 