I already tried to ask this question here. Probably the question is too difficult but I will appreciate any comment, e.g. suggestions on connections with other fields or literature on similar problems.

We have two functions: $$ f: \{0,1\}^* \to \{0,1\}^* $$ $$ g: \{0,1\}^* \to \{0,1\}^* $$ that commute: $$ f[g(x)] = g[f(x)] $$

These two functions can be calculated in polynomial time (in the length of the input). Moreover, the outputs have the same length of the inputs: $|f(x)| = |x|$ and $|g(x)| = |x|$ .

A trivial example of functions that commute can be easily constructed by splitting the strings into two parts and defining: $$ f(x,y) = ( h(x), y ) $$ and $$ g(x,y) = ( x, l(y) ) $$ where the functions $h(x)$ and $l(y)$ can be calculated in polynomial time (in their inputs).

I was able to construct slightly more complex examples, but not much more complex. In all the examples, the evolution obtained by repeatedly applying $f$ seems to be independent of the evolution obtained by repeatedly applying $g$. More rigorously, in my examples, the following proposition holds:

Proposition 1

There are two functions $n'$ and $m'$ depending on $n$ and $m$, at most polynomial, such that there is an algorithm that, for any integers $n$ and $m$, calculates the function $f^n[g^m(x)]$, operating in polynomial time (in the length of its input), and taking the following inputs: the numbers $n$ and $m$, $f^{n'}(x)$, and $g^{m'}(x)$.

Important note The expression $f^n$ means $f$ applied $n$ times. For example $f^2(x)$ means $f[f(x)]$, $f^3(x)$ means $f\{f[f(x)]\}$.

I remark that this happens even if $n$ and $m$ increase exponentially in $|x|$.

In the trivial example above, setting $n'=n$ and $m'=m$, we see that $f^n(x)= ( h^n(x), y )$ and $g^m(x) = (x, l^m(y) )$, from which it is easy to calculate $f^n[g^m(x,y)] = ( h^n(x), l^m(y) ) $.

The question is: is Prop. 1 a general theorem? Alternatively, is there a counter-example to Prop. 1?

Thanks to comments already received, I know that Prop. 1 holds for sure in the following cases:

1. if $f=h^a$ and $g=h^b$ (with $a$ and $b$ two natural numbers);
2. if $f^n$ can be calculated in polynomial time in the size (number of bits) of $n$.

Maybe the question is too difficult to be answered; thus any help is welcome.