If $f \in R = \Bbb{Z}_p[x]$ is irreducible or doesn't have many factors then it could be hard to compute? Possibly, I'm not saying, but... any way, what if $f = h - g$ where $h, g$ are heavily "factored"? Then in terms of computational complexity $f$ is now easy to compute.
Let $f$ be some irreducible. Suppose there exist no $f = h + g$ such that $h, g$ are easy to compute. Then $f$ is hard to compute. Because if $f$ were easy to compute, then $f = h + g$ where $h$ is all the operations in memory to compute $f$ up to the last and $g$ equals the last operation. Thus both $h, g$ are easy to compute and contradiction.
Thus I'm in search of an irreducible $f$ such that $f \neq h + g$ for any easy to compute $h, g$.
Now I think we need some sort of recursive definition using both $+, \cdot$. This is a tough problem. Any ideas??