2
$\begingroup$

Sipser defines a time constructible function as

$f(n)$ is time constructible if there exists a turing machine which given input $1^n$ writes value of $f(n)$ in binary to the output tape in $O(f(n))$ time.

whereas Sanjeev Arora and Barak defines it as

$f(n)$ is time constructible if there exists a turing machine which given input $1^n$ writes value of $1^{f(n)}$ in binary to the output tape in $O(f(n))$ time.

I am unable to see how are these two definitions equivalent. Isn't there a case where writing value in binary takes less time that writing it in unary ? Also what is the reason for inputs being given in unary rather than binary or some other base $k > 2 $ ?

$\endgroup$
1
$\begingroup$

The two definitions are probably equivalent (perhaps $f(n)$ need be not too small): given $f(n)$ in binary you can write $1^{f(n)}$ in $O(f(n))$ time, and vice versa. The ideas are as follows.

Binary to unary: Inductively construct $1^{b_m b_{m-1} \ldots b_{m-t}}$, where $b_m\ldots b_0$ is the binary representation of $1^{f(n)}$. At each step we need to roughly double the string of 1s, and in stage $t$ this takes roughly $O(f(n)/2^{m-t})$ time. Taking into account all stages, we get roughly $O(f(n))$.

Unary to binary: Construct the binary representation of $f(n)$ from LSB to MSB by repeatedly dividing $f(n)$ by two. The $t$th division by two requires time $O(f(n)/2^t)$, so overall this runs in time roughly $O(f(n))$.

As to why the input is in unary rather than in binary, this ionly affects small $f(n)$; as we have seen, converting between $1^n$ and $n$ should take time $O(n)$, and this is affordable as long as $f(n) = \Omega(n)$.

$\endgroup$
  • $\begingroup$ why would the above explanation not hold for small f(n) ? $\endgroup$ – sashas Feb 16 '16 at 12:37
  • $\begingroup$ It might, but you'll have to check the details to make sure. Also, for small $n$ it might take too much time to read the input. $\endgroup$ – Yuval Filmus Feb 16 '16 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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