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.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "It supports pointers indexing the input" did you mean, if the input size is $n$ then indexing will take $O( \log n) $? $\endgroup$
    – user35837
    Mar 14, 2017 at 13:51
  • $\begingroup$ Right, to count from 1 to $n$ you need $\log n$ bits. $\endgroup$
    – Yuval Filmus
    Mar 14, 2017 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$
    – user35837
    Mar 14, 2017 at 15:59
  • $\begingroup$ @Shivd : ​ closed , composition , work tapes ​ ​ ​ ​ $\endgroup$
    – user12859
    Mar 14, 2017 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!"

Improve this answer
$\endgroup$
4
  • 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$
    – user35837
    Mar 14, 2017 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, 2017 at 13:22
  • 1
    $\begingroup$ Mathematical properties of logarithmic space. $\endgroup$
    – user35837
    Mar 14, 2017 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, 2017 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.