8
$\begingroup$

We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) Turing machine that for $n$ given, halts after exactly $f(n)$ steps, and just asked if we could now prove that $n!$ is fully time constructible (and moved on).

I am not sure how the proof goes, but I am thinking it has to use $n^k$ time constructability to some extent, or some identity involving factorials, since we showed $n^k$ is (fully) time constructible using $n^k = n + \sum_{i=1}^{i=k-1}(n - 1)n^i$.

Hints would be appreciated too, really. Thanks in advance.

$\endgroup$
1
$\begingroup$

Let us assume we have find $n!$ on input $n$. Our complexity is terms of length of the input ( we assume it to be $L=O(logn)$ ). Multiplication of a $k$ bit by $l$ bit number via standard multiplication takes $O(kl)$ operations ( also after multiplication number of bits in the resultant if $O(k+l)$ ) . We multiply linearly in a loop from $1$ to $n$ to get $n!$. So number of operations carried out are upper bounded by $\# = L^2 ( 1 + 2 ...(n-1) ) = \frac{L^2n(n-1)}{2} = O(L^22^{O(L)})=o(L!)$. Thus it is space and time constructible.

$\endgroup$
2
  • 1
    $\begingroup$ The problem is that you need to prove (construct a machine, give "a description" of its steps - and then count them) that, if n is an input length, machine halts after exactly f(n) steps. Upper bound is, in this, case, irrelevant (because it, in fact, immediately follows from given proof). $\endgroup$
    – coptus
    Apr 13 '16 at 12:43
  • $\begingroup$ @coptus According to Wikipedia it seems like there are 2 different definitions for time-constructible function. One only requires the function to halt after exactly $f(n)$ steps, while the other requires halting in $O(f(n))$ steps but also requires the output to be the binary representation of $f(n)$. It seems to me like sashas proved according to the second definition $\endgroup$ Oct 20 '18 at 17:12

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.