5
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Jul 25, 2023 at 21:19

1 Answer 1

5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.