0

Let function $~f, g \in FP$. What can we say about function $h : x \to f(x)^{g(x)}$? I suggest that $h \in FP$, but I do not know how to formally prove this.

markovian
  • 451
  • 1
    With $f(x)=2$ and $g(x)=\frac12$, what is the Turing machine that ouputs all digits of $\sqrt 2$ in polynomial time? – Hagen von Eitzen Dec 11 '16 at 21:51
  • 1
    Take $f(x) = 2$ and $g(x) = x$. Then $h(x) = 2^x$, so the number of digits in $h(x)$ is exponential in the number of digits in $x$. – Rob Arthan Dec 11 '16 at 21:52

0 Answers0