# What is the correct way to define time constructible functions?

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

## 1 Answer

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

• why would the above explanation not hold for small f(n) ? – sashas Feb 16 '16 at 12:37
• 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. – Yuval Filmus Feb 16 '16 at 12:39
{"ft_lang_label":"__label__en","ft_lang_prob":0.8093067,"math_prob":0.99963176,"size":669,"snap":"2021-21-2021-25","text_gpt3_token_len":170,"char_repetition_ratio":0.10977443,"word_repetition_ratio":0.32478634,"special_character_ratio":0.2541106,"punctuation_ratio":0.037593983,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99998224,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-06-12T17:19:17Z\",\"WARC-Record-ID\":\"<urn:uuid:82a2c42e-2623-4e08-a89e-154fb29f4ffc>\",\"Content-Length\":\"163537\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:2aab795e-ce57-492c-b494-7cd4a2471d44>\",\"WARC-Concurrent-To\":\"<urn:uuid:f54fc851-e6ed-4bf9-a990-a31afca2f873>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/53189/what-is-the-correct-way-to-define-time-constructible-functions\",\"WARC-Payload-Digest\":\"sha1:57DYLZF7TMDYSNMEBNE4NNAMUELQ2Z4M\",\"WARC-Block-Digest\":\"sha1:QQUZMEIQ33S4M4NM6Q7I5GXITJZ4772W\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-25/CC-MAIN-2021-25_segments_1623487586239.2_warc_CC-MAIN-20210612162957-20210612192957-00554.warc.gz\"}"}