What is the correct way to define time constructible functions?

Question

Are these two definitions of a time constructible function the same?

$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.

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

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

• Emil Jeřábek: "value of 1ドル^{f(n)}$ in binary" does not make any sense. The notation 1ドル^{f(n)},ドル by definition, means unary. 1ドル^{f(n)}$ is not a number, but a string; only numbers can be "written in binary", not strings. Anyway, the only possibly meaningful way of interpreting "1ドル^{f(n)}$ in binary" is that it is a clumsy way of writing "$f(n)$ in binary", unless you intend 1ドル^{f(n)}$ to denote powering, in which case it equals 1ドル$. Finally, the wording in Arora and Barak is completely different: "... TM $M$ that computes the function $x\mapsto\llcorner T(|x|)\lrcorner$ ..." (which denotes binary).
• advocateofnone: @EmilJeřábek Thanks. Corrected the wording. I dont' remember if this coincides with the book, but captures the question I had long back.

Answer 1

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)$.

• advocateofnone: why would the above explanation not hold for small f(n) ?
• Yuval Filmus: 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.