1
$\begingroup$

Is there a reference somewhere for the result SPACE($O(\log n)$) = SPACE($\log n$)? i.e. Big-O doesn't matter in logspace since you can compress the space. I feel like this is an elementary result but I can't figure out if it was stated somewhere, or if it's a corollary of something, or if it's just folklore.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Usually the notation SPACE(f(n)) means problems that can be solved in O(f(n)) space, so there is no difference between the left and right hand sides -- just different notation for the same thing. E.g. see here: en.wikipedia.org/wiki/DSPACE#Complexity_classes ... I don't think you can compress the space in general, but maybe I'm mistaken. Is that something you read somewhere? (Also, I didn't downvote, but this is probably better suited for cs.stackexchange.com ) $\endgroup$
    – Areawoman
    Sep 1, 2020 at 23:36
  • 7
    $\begingroup$ SPACE(f(n)) is usually formally defined with TMs, and the "space" required by a computation refers to the number of tape cells it requires. You can, in general, reduce the space used by any given TM by modifying it to use a larger tape alphabet, where each tape symbol can encode the contents of multiple tape cells from the original TM. So, for the definition to make sense, you pretty much have to allow space O(f(n)), not specifically f(n). You can find such "speedup" theorems in older texts on computability. $\endgroup$
    – Neal Young
    Sep 2, 2020 at 1:20
  • 1
    $\begingroup$ I think this is not a research level question. The mentioned speedup theorem is explained here: en.wikipedia.org/wiki/Blum%27s_speedup_theorem $\endgroup$
    – Hermann Gruber
    Sep 2, 2020 at 15:42
  • $\begingroup$ My apologies, I wasn't aware of the distinction between cs and tcs Stack Exchange. Thanks for the comments. $\endgroup$
    – user59894
    Sep 2, 2020 at 16:27
  • $\begingroup$ Suppose that you have a Turing machine computation that uses $k$ tapes, each over an alphabet of size $c$, and you access at most $f(n)$ cells per tape for inputs of length $n$. You should be able to simulate this computation using $k$ tapes, each over an alphabet of size $c^2$, and $\frac{f(n)}{2}$ cells per tape. In other words, by increasing alphabet size, you can decrease the number of cells. $\endgroup$
    – Michael Wehar
    Sep 13, 2020 at 6:46

0

Reset to default