Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.