#StackBounty: #turing-machines #time-complexity Proving that a time-constructible function to the power a time-constructible function i…

Bounty: 50

A function $T: mathbb{N} rightarrow mathbb{N}$ is time-constructible if there exist a turing machine $M$ which computes $1^{T(n)}$ on input $1^{n}$ in $T(n)$ time.

Let $T_1$ and $T_2$ be two time-constructible functions in accordance to the definition above. I’m unable to prove the following:

  • $T_1(n)^{T_2(n)}$ is time-constructible

My approach:

  • I thought of constructing $T_1(n)^k$ using $T_1(n)^{k-1}$. Given $T_1(n)$ and $T_1(n)^{k-1}$ I know I can multiply them in time $T_i(n)^k$. Hence the net time to compute $T_1(n)^{T_2(n)}$ by my construction = $T_1(n) + T_1(n)^2 +….+T_1(n)^{T_2(n)} > T_1(n)^{T_2(n)}$
  • To print $T_1(n)^{T_2(n)}$ in time $T_1(n)^{T_2(n)}$ i would need to print a 1 on the output tape in every timestamp which intuitively sounds impossible to me


Get this bounty!!!

Leave a Reply