EDIT: in this question, I was proposing a conjecture, Prop. 1. Fedor Pakhomov showed a counter-example. [In this new question][1] I propose a slightly weaker conjecture that holds even for that example and seems to be still hard to prove. There is also an [older version][2]. 

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 binary representations of 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.


  [1]: https://mathoverflow.net/questions/433954/computational-complexity-and-commuting-functions-improved-conjecture
  [2]: https://math.stackexchange.com/questions/4557690/computational-complexity-and-commuting-functions