In the last few days I thought a lot about (fully) time-constructible functions and I will present what I found out by answering Q1 and Q3. Q2 seems too hard.
Q3:
Kobayashi in his article (the reference is in the question) proved that a function $f:\mathbb{N}\rightarrow\mathbb{N}$, for which there exists an $\epsilon>0$ s.t. $f(n)\geq (1+\epsilon)n$, is fully time constructible iff it is computable in $O(f(n))$ time. (note that it is irrelevant whether the input or output is in unary/binary since we can transform between these two representations in linear time). This makes the following functions fully time-constructible: $2^n$, $2^{2^n}$, $n!$, $n\lfloor \log n \rfloor$, all polynomials $p$ over $\mathbb{N}$ s.t. $p(n)\geq (1+\epsilon)n$ ... Kobayashi also proved fully time-constructibility for some functions that grow slower than $(1+\epsilon)n$, like $n+\lfloor\lfloor\log n\rfloor^q\rfloor$ for $q\in\mathbb{Q}^+$ ...
To continue with examples of fully time-constructible functions, one can prove that if $f_1$ and $f_2$ are fully time-constructible, then $f_1+f_2$, $f_1f_2$, $f_1^{f_2}$ and $f_1\circ f_2$ are also fully time-constructible (the later follows directly from Theorem 3.1 in Kobayashi). This altogether convince me that many nice functions are indeed fully time-constructible.
It is surprising that Kobayashi did not see a way to prove fully time-constructibility of the (nice) function $\lfloor n\log n\rfloor$ (and neither do I).
Let us also comment the definition from Wikipedia article: A function $f$ is time-constructible, if there exists a Turing machine $M$ which, given a string $1^n$, outputs $f(n)$ in $O(f(n))$ time. We see that this definition is equivallent to our definition of fully time-constructibility for functions $f(n)\geq (1+\epsilon)n$.
Q1:
This question has a really interesting answer. I claim that if all time-constructible functions are fully time-constructible, then $EXP-TIME=NEXP-TIME$. To prove that, let us take an arbitrary problem $L\in NEXP-TIME$, $L\subseteq\{0,1\}^*$. Then there exists a $k\in\mathbb{N}$, s.t. $L$ can be solved by a NDTM $M$ in $2^{n^k-1}$ steps. We can assume that at each step $M$ goes in at most two different states for simplicity. Now define the function
$$f(n)=\left\{\begin{array}{ll}
8n+2 & \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\
8n+1 & \mbox{else}
\end{array}
\right.$$
I claim that $f$ is time-construcible. Consider the following deterministic Turing machine $T$:
- on input $w$ of length $n$ it computes $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ in $O(n)$ time
- then it simulates $M$ on these bits, where the bits of $w$ determine which (formerly nondeterminisic) choices to take.
- accept iff $\left(M\textrm{ accepts using choices given by }w\right)$.
Note that the length of $w$ ($=n$) is enough that it determines all nondeterministic choices, since $M$ on input $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ makes at most $n$ steps.
We can make $T$ run in at most $8n+1$ steps. Now the following Turing machine proves that $f$ is time-constructible:
- on input $w$ of length $n$ run $T$ and count steps in parallel so that exacly $8n$ steps are done.
- if $T$ rejected or would reject in the next step, go to a halting state in the next step. Else, make one more step and then go to a halting state.
Now suppose that $f$ is fully time-constructible. We will prove that this leads to $EXP-TIME=NEXP-TIME$.
The following algorithm solves $L$:
- on input $x$, let $n$ be the number with binary representation $x00\ldots 0$ ($|x|^{k-1}$ zeros). It follows that $x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$.
- compute $f(n)$ in time $f(n)$ and check whether it is divisible by 2.
This algorithm runs in exponential time and solves $L$. Since $L\in NEXP-TIME$ was arbitrary, $EXP-TIME=NEXP-TIME$.
J. E. Hopcroft, J. D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley Series in Computer Science, 1979
The same definition can be found here: http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fivese2.html
– David G Jan 10 '13 at 11:04