Problem 2079

The answer is that it does exist such a polynomial. Actually we shall prove a more general result: Let $s$ be an even integer and $t > 1$ be an arbitrary integer. Then for some constant $c > 0$ for the polynomial $P(x) = (x+1)^s + c-1$ (which is of degree $s$) we have $f(P) = t$. Indeed:
The polynomial $P$ is strictly increasing function on the interval $[-1, \infty)$. Let $x_k(c)$ be the minimal value of the polynomial $\underbrace{P(P(\dots P(x))\dots)}_{k}$ for a fixed $c > 0$,

Consider $x_k(c)$ is strictly increasing, because of $x_1(c) = c-1 > -1$ and $x_{k+1}(c) = P(x_k(c))$. The equation $x_{t-1}(c) = 0$ (where $c$ is the unknown). Since the leading coefficient of the polynomial $x_{t-1}(c)$ equals $1$ and the constant term is $-1$ (we can prove these claims trivially by induction on $t$), this polynomial has a positive zero. Let $c_0$ be one of them. Now for the polynomial $P(x) = (x+1)^s + c_0 - 1$ we have $x_{t-1}(c_0) = 0$, and therefore $x_t(c_0) = P(0) = c_0 > 0$. This completes the proof. $\square$