2
$\begingroup$

I have a problem with definition of space constructable function.

As I understood we use this definition just for simplification of further proofs and idea behind this definition is very clear, but definition itself is very vague.

Sipser's definition: A function $f : \mathbb N \rightarrow \mathbb N$, where $f(n)$ is at least $O(\log n)$, is called space constructable if the function that maps the string $1^{n}$ to the binary representation of $f(n)$ is computable in space $O(f(n))$.

The role of this definition described very well in the book. But I just want to understand

  1. Why we use boundary with $\log n$ function and not any other?

  2. What's the role of $1^{n}$ input?

Thanks!

1 Answers 1

1

Regarding question 2. $1^n$ is just the input number represented in unary. Remember that we want this function to be computable in $O(f(n))$ space, where $n$ is the length of the input. The only way for a number $n$ to count $n$ digits, is to use unary notation.

Regarding question 1, I think that there aren't many space constructible functions that are $o(f(n))$. Also, I don't think if there were I don't think they would be very useful (I could be wrong), since going much lower then $\log n$, we would have functions like $O(1)$ etc.

Extra: The reason why time constructible functions have $n$ as lower bound is much more clear. This is because a Turing machine needs to read the whole input first, which takes linear time.