Functions with polytime iterated applications

Question

Definitions

Let $f : \{0,1\}^n \rightarrow \{0,1\}^n$ be some boolean function where the length of the output always equals the length of the input. Let $f^{k} : \{0,1\}^n \times \mathbb{N} \rightarrow \{0,1\}^n$ be $f$ applied to the input $k$ times, taking at each step its previous output as the new input. Assume $k$ is given as an argument written in binary.

Question

Assuming $f \in FP$, what are some broad restrictions on $f$ such that $f^{k} \in FP$?

Positive results

A simple motivating example: let $f$ map $(a, b)$ to $(a+b, b)$. Then $f^{k}(a, b) = (a + kb, b)$, and integer multiplication is in $FP$, so $f^{k} \in FP$. Here we can "short-circuit" the evaluation of $f$ and avoid the repeated calculations; I'm interested in more broad classes of functions for which we can do this. This example also works for modular multiplication, which just becomes modular exponentiation when iterated.

An example of the kind of class of functions for which this is true that I'm interested in: if $f^k$ is periodic in $k$ with a period $p$ that is independent of $n$, and $f \in FP$, then we can calculate $f^k$ by simply calculating $f^{k \text{ mod } p}$. This even works if $p$ is a function of $n$, as long as $p(n) \in O(\log(n))$; we can just apply $f$ iteratively until we get a repeated value (which must be a polynomial number of steps), at which point we can calculate the period of $f^k$ and do the same trick.

Negative results

The naive approach of computing $f$ the full $k$ times takes time exponential in the input length. Furthermore: let $f$ take in the state of some fixed Turing machine, and output its computation advanced by a single step. Then $f^k$ is, in the worst case, $PSPACE$-complete (c.f. "The Complexity of Iterated Reversible Computation" by David Eppstein). Therefore, any class $f$ that can simulate a single step of a Turing machine will (probably) not necessarily have iterated applications in $P$. Although I could not find an explicit reference, I believe $AC^0$ is sufficiently powerful to simulate a single step of a Turing machine, so there are $AC^0$ functions (probably) without polytime iterated applications.

Answer 1

It can be done whenever $f$ is linear (over any semiring), by representing it as a matrix and using matrix exponentiation.

If it can be done for $f$, it can be done for $f$ conjugated by any $FP$ invertible function, because of the following: $(g^{-1}\circ f\circ g)^k=g^{-1}\circ f^k\circ g$.