[Solved]: Notation: SPACE(n) vs SPACE(O(n))

Problem Detail: 

I want to denote the class of problems solvable by linear space multi-tape Turing machines. I have seem in many places this class being denoted by $SPACE(n)$. But why is the notation $SPACE(O(n))$ not preferred in this case? In particular, I'm writing a project in which I need to distinguish between problems solvable in space $c_1\cdot n$ and problems solvable in space $c_2\cdot n$ for $c_2>c_1$.

1. Which notation should I use? $SPACE(n)$ or $SPACE(O(n))$?
2. And how to distinguish between space $c_1\cdot n$ and $c_2\cdot n$ without confusion?

Asked By : Springberg

Answered By : David Richerby

It depends on what definitions you use. Sipser [1] defines $\mathrm{SPACE}(f(n))$ to be the class of languages decided by Turing machines using $O(f(n))$ cells on their work tapes for inputs of length $n$. Papadimitriou [2], on the other hand defines it to be the class of languages decided by Turing machines using at most $f(n)$ cells on the work tapes.

However, the space analogue of the linear speedup theorem implies that, actually, these two definitions are equivalent, so you should pick whichever one is most convenient for you. Since you want to distinguish between machines that use up to $c_1n$ work space and those that use up to $c_2n$, the Papadimitriou-style definition seems more appropriate to your needs. Make sure you clearly and explicitly define $\mathrm{SPACE}(f(n))$ before using it. But do be aware that anything you can do with $n$ worktape cells using a $k$-symbol alphabet, I can do with $n/2$ cells by using an alphabet of size about $k^2$. Unless you're using a fixed tape alphabet, $\mathrm{SPACE}(c_1n)$ and $\mathrm{SPACE}(c_2n)$ are the same complexity class, even with the Papadimitriou-style definition.

---

References

1. Michael Sipser, Introduction to the Theory of Computation. Cengage Learning, 3rd edition, 2013. (Earlier editions almost certainly use the same definition.)

2. Christos H. Papadimitirou, Computational Complexity. Addison Wesley Longman, 1994.

Acknowledgments
Thanks to The Vee for pointing out an error in an earlier version of this answer.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65135