<p>Is there a reference somewhere for the result SPACE(<span class="math-container">$O(\log n)$</span>) = SPACE(<span class="math-container">$\log n$</span>)? 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.</p>

CC BY-SA 4.0
2020-09-01T23:36:45.500Z
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: https://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 https://cs.stackexchange.com/ )
Elle Najt
CC BY-SA 4.0
2020-09-02T01:20:25.613Z
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.
Neal Young
CC BY-SA 4.0
2020-09-02T15:42:47.827Z
I think this is not a research level question. The mentioned speedup theorem is explained here: https://en.wikipedia.org/wiki/Blum%27s_speedup_theorem
Hermann Gruber
CC BY-SA 4.0
2020-09-02T16:27:27.377Z
My apologies, I wasn't aware of the distinction between cs and tcs Stack Exchange. Thanks for the comments.
user59894
CC BY-SA 4.0
2020-09-13T06:46:34.613Z
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.
Michael Wehar
CC BY-SA 4.0
2020-09-13T06:51:20.540Z
As a result, some authors that discuss space complexity might say things like $SPACE(f(n)) = SPACE(\frac{f(n)}{2})$ because they measure space complexity in terms of number of cells used (or number of cells used per tape) over all Turing machines regardless of alphabet size.
Michael Wehar
CC BY-SA 4.0
2020-09-13T06:53:33.297Z
If you measure space complexity for a fixed number of tapes and a fixed alphabet size, then you should be able to show that $SPACE(f(n)) \neq SPACE(\frac{f(n)}{2})$ using techniques from the space hierarchy theorem.
Michael Wehar
CC BY-SA 4.0
2020-09-13T06:56:22.760Z
I think this question is actually quite reasonable for discussion here on cstheory.  Especially since (in my opinion) the literature isn't always that clear on this topic.
Michael Wehar
<reference-request><complexity-classes><space-complexity><logspace>
Reference to "compressibility" of logarithmic space
user59894
# Reference to "compressibility" of logarithmic space

(Asked by: username_0 on 2020-09-01)

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.

**Tags:** reference-request, complexity-classes, space-complexity, logspace

> **Comments:**
> **username_1**: 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: https://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 https://cs.stackexchange.com/ )  
> **username_2**: 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.  
> **username_3**: I think this is not a research level question. The mentioned speedup theorem is explained here: https://en.wikipedia.org/wiki/Blum%27s_speedup_theorem  
> **username_0**: My apologies, I wasn't aware of the distinction between cs and tcs Stack Exchange. Thanks for the comments.  
> **username_4**: 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.  
> **username_4**: As a result, some authors that discuss space complexity might say things like $SPACE(f(n)) = SPACE(\frac{f(n)}{2})$ because they measure space complexity in terms of number of cells used (or number of cells used per tape) over all Turing machines regardless of alphabet size.  
> **username_4**: If you measure space complexity for a fixed number of tapes and a fixed alphabet size, then you should be able to show that $SPACE(f(n)) \neq SPACE(\frac{f(n)}{2})$ using techniques from the space hierarchy theorem.  
> **username_4**: I think this question is actually quite reasonable for discussion here on cstheory.  Especially since (in my opinion) the literature isn't always that clear on this topic.  

---

## 0 answers

