Supose I define a function $f$ as $$\begin{cases}f(0)=1\\f(n+1)=p(f(0)+\dots+f(n))\end{cases}$$ where $p$ is some function computable in polynomial time.
Can I say that $f$ is also computable in polynomial time?
I saw this paper with a recursion-theoretic characterization of $\mathsf{FP}$ but didn't manage to use this characterization to prove/disprove this claim.
Thanks in advance
I assume you mean $f$ and $p$ are computable in poly(log(input)) time, i.e. polynomial in the length of the input as a binary string.
Let $p(n)=(n+1)^2$ which is definitely computable in $O(\log^2(n))$ time. It's easy to show that $f(n)\ge 2^n$ by induction: whenever $n\ge 1$ $$f(n+1)= (f(0)+\cdots+f(n)+1)^2 \ge f(n)^2 \ge (2^n)^2 = 2^{2n}\ge 2^{n+1}$$
Therefore even to write down the answer $f(n)$ bit by bit takes at least $\log_2 f(n)\ge n$ steps, which is exponential in $\log(n)$.
P.S. If you mean polynomial in $n$, then let $p(n) = 2^n$ which is computable in poly($n$) time. If $f(n)$ is computable in $q(n)$ time for a polynomial $q$, then $f(n)\le 2^{q(n)}$ because in $\le q(n)$ time, one can write down at most $2^{q(n)}$-bits. Then for all $n$, $$f(n+1) = p(f(0) + f(1) + \cdots + f(n)) = 2^{f(0)+f(1)+\cdots+f(n)}\le 2^{q(n+1)}$$ $$f(n)\le f(0)+\cdots+f(n)\le q(n+1)$$ but $f(n)$ grows way faster than exponential function $2^n$, so it cannot be bounded by a polynomial.
So either way, the answer is false.