2
$\begingroup$

$L$ is the class of languages that are decideable in logarithmic space on a deterministic Turing machine. In other words,

L = SPACE$( \log n)$

But why $\log n$, instead of $\log^2 n$ or $\sqrt n$. This is what, I find out in the Theory of computation book by Michael Sipser Theory of computation book by Michael Sipser, Chapter 8

Logarithmic space is just large enough to solve a number of interesting computational problems, and it has attractive mathematical properties such as robustness even when mathematical model and input encoding method change.

I am not able to understand completely, how mathematical properties and input encoding are related to defining L complexity class.

$\endgroup$
5
$\begingroup$

The complexity class $\mathsf{L}$ satisfies many desirable properties:

  • It is closed under concatenation and iteration.
  • The corresponding function class is closed under composition.
  • The same complexity class is obtained for any number of work tapes.
  • It is resilient under "reasonable" input transformations with polynomial blowup (see below).
  • It can accommodate most known NP-hardness reductions.
  • It is a subset of $\mathsf{P}$.
  • It supports pointers indexing the input.

What is an input transformation? Consider the case of graphs. We can encode a graph either as an adjacency matrix of as adjacency lists. We can convert between the two in logspace, and so a graph problem which is in $\mathsf{L}$ under one of them is also in $\mathsf{L}$ under the other.

Logspace is the natural space analog of $\mathsf{P}$, considering the containment $\mathsf{SPACE}(f(n)) \subseteq \mathsf{TIME}(2^{f(n)})$.

It also shows up in the refined Schaefer's dichotomy theorem, as the lowest non-trivial complexity class.

$\endgroup$
  • $\begingroup$ "It supports pointers indexing the input" did you mean, if the input size is $n$ then indexing will take $O( \log n) $? $\endgroup$ – aaag Mar 14 '17 at 13:51
  • $\begingroup$ Right, to count from 1 to $n$ you need $\log n$ bits. $\endgroup$ – Yuval Filmus Mar 14 '17 at 13:51
  • $\begingroup$ what is a difference between "corresponding function class is closed under composition" and "The same complexity class is obtained for any number of work tapes" . $\endgroup$ – aaag Mar 14 '17 at 15:59
  • $\begingroup$ @Shivd : ​ closed , composition , work tapes ​ ​ ​ ​ $\endgroup$ – user12859 Mar 14 '17 at 19:41
0
$\begingroup$

Why? Because that's the definition. Why is $\pi$ defined to be the ratio between the circumference and diameter of a circle, rather than the base of natural logarithms or the golden ratio? Because it is.

You seem to be looking at it backwards. It's not that somebody said, "Hmm. My name's Logan and I want to have a complexity class called L. What class should I choose?" Rather, the class of problems that can be solved in $O(\log n)$ steps for inputs of length $n$ is a useful and important class of problems. People talked about it a lot, so they needed to give it a name. The name they chose was L, which is a logical and mnemonic name for that class of problems. Just like people said, "Hey, we seem to be using this circumference-to-diameter ratio a lot. What name should we give it?" rather than, "Hey, $\pi$'s a pretty shape. We should use it for a constant!"

$\endgroup$
  • 1
    $\begingroup$ @ David Richerby I am not asking why they gave name "L" to it. My question is "how mathematical properties and input encoding are related to defining L complexity class". Please read the last line of the question. $\endgroup$ – aaag Mar 14 '17 at 13:12
  • $\begingroup$ I answered the question in the title of your post, which is the only actual question you posted. I don't understand the last sentence of your question. The definition is the definition. Mathematical properties of what? The definition doesn't mention input encoding anywhere. $\endgroup$ – David Richerby Mar 14 '17 at 13:22
  • 1
    $\begingroup$ Mathematical properties of logarithmic space. $\endgroup$ – aaag Mar 14 '17 at 13:28
  • $\begingroup$ @DavidRicherby I think he probably asks what are the advantages of L defined the way it is defined. Why L is a relevant complexity class and not, say, DSPACE(log^2 n). I linked above the answer frmo Lance Fortnow on a related question from TCS.stackexchange $\endgroup$ – PsySp Mar 14 '17 at 13:29

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.