<p>It can be done whenever <span class="math-container">$f$</span> is linear (over any semiring), by representing it as a matrix and using matrix exponentiation.</p>
<p>If it can be done for <span class="math-container">$f$</span>, it can be done for <span class="math-container">$f$</span> conjugated by any <span class="math-container">$FP$</span> invertible function, because of the following: <span class="math-container">$(g^{-1}\circ f\circ g)^k=g^{-1}\circ f^k\circ g$</span>.</p>

CC BY-SA 4.0
2023-07-27T05:03:54.543Z
2023-08-29T21:40:08.733Z
2023-08-29T21:40:08.733Z
Command Master
<h3>Definitions</h3>
<p>Let <span class="math-container">$f : \{0,1\}^n \rightarrow \{0,1\}^n$</span> be some boolean function where the length of the output always equals the length of the input. Let <span class="math-container">$f^{k} : \{0,1\}^n \times \mathbb{N} \rightarrow \{0,1\}^n$</span> be <span class="math-container">$f$</span> applied to the input <span class="math-container">$k$</span> times, taking at each step its previous output as the new input. Assume <span class="math-container">$k$</span> is given as an argument written in binary.</p>
<h3>Question</h3>
<p>Assuming <span class="math-container">$f \in FP$</span>, what are some broad restrictions on <span class="math-container">$f$</span> such that <span class="math-container">$f^{k} \in FP$</span>?</p>
<h3>Positive results</h3>
<p>A simple motivating example: let <span class="math-container">$f$</span> map <span class="math-container">$(a, b)$</span> to <span class="math-container">$(a+b, b)$</span>. Then <span class="math-container">$f^{k}(a, b) = (a + kb, b)$</span>, and integer multiplication is in <span class="math-container">$FP$</span>, so <span class="math-container">$f^{k} \in FP$</span>. Here we can &quot;short-circuit&quot; the evaluation of <span class="math-container">$f$</span> 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.</p>
<p>An example of the kind of class of functions for which this is true that I'm interested in: if <span class="math-container">$f^k$</span> is periodic in <span class="math-container">$k$</span> with a period <span class="math-container">$p$</span> that is independent of <span class="math-container">$n$</span>, and <span class="math-container">$f \in FP$</span>, then we can calculate <span class="math-container">$f^k$</span> by simply calculating <span class="math-container">$f^{k \text{ mod } p}$</span>. This even works if <span class="math-container">$p$</span> is a function of <span class="math-container">$n$</span>, as long as <span class="math-container">$p(n) \in O(\log(n))$</span>; we can just apply <span class="math-container">$f$</span> iteratively until we get a repeated value (which must be a polynomial number of steps), at which point we can calculate the period of <span class="math-container">$f^k$</span> and do the same trick.</p>
<h3>Negative results</h3>
<p>The naive approach of computing <span class="math-container">$f$</span> the full <span class="math-container">$k$</span> times takes time exponential in the input length. Furthermore: let <span class="math-container">$f$</span> take in the state of some fixed Turing machine, and output its computation advanced by a single step. Then <span class="math-container">$f^k$</span> is, in the worst case, <span class="math-container">$PSPACE$</span>-complete (c.f. &quot;The Complexity of Iterated Reversible Computation&quot; by David Eppstein). Therefore, any class <span class="math-container">$f$</span> that can simulate a single step of a Turing machine will (probably) not necessarily have iterated applications in <span class="math-container">$P$</span>. Although I could not find an explicit reference, I believe <span class="math-container">$AC^0$</span> is sufficiently powerful to simulate a single step of a Turing machine, so there are <span class="math-container">$AC^0$</span> functions (probably) without polytime iterated applications.</p>

CC BY-SA 4.0
2023-07-25T21:19:27.250Z
This sounds too open-ended to be answerable in a useful way in its current form.  Can you articulate what kinds of restrictions or classes of functions you are interested in?  Can you make this useful for others by identifying what classes you have already determined do lead to FP and which don't?  Can you give some examples of classes that you are uncertain about and for which you'd like to know the answer?
D.W.
<cc.complexity-theory>
Functions with polytime iterated applications
Jake
# Functions with polytime iterated applications

(Asked by: username_0 on 2023-07-25)

### 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.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: This sounds too open-ended to be answerable in a useful way in its current form.  Can you articulate what kinds of restrictions or classes of functions you are interested in?  Can you make this useful for others by identifying what classes you have already determined do lead to FP and which don't?  Can you give some examples of classes that you are uncertain about and for which you'd like to know the answer?  

---

## 1 answers

### Answer by username_2 on 2023-07-27. Score: 5

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$.


---

