EDIT: in this question, I was proposing a conjecture, Prop. 1. Fedor Pakhomov showed a counter-example. [In this new question](https://mathoverflow.net/questions/433954/computational-complexity-and-commuting-functions-improved-conjecture) 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](https://math.stackexchange.com/questions/4557690/computational-complexity-and-commuting-functions).


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.



Computational complexity and commuting functions
There is a counterexample to Proposition 1 iff $\mathsf{P}\ne\mathsf{PSPACE}$. The idea is to make a pair $f,g$ such that on certain inputs iterations of them individually are trivial, but their combination performs computation of a deciding algorithm for some $\mathsf{PSPACE}$-complete problem.


If $\mathsf{P}=\mathsf{PSPACE}$, then since $f^n(g^m(x))$ could be computed in polynomial space from $x$, we would be able to compute $f^n(g^m(x))$ in polynomial time.


Further assume that $\mathsf{P}\ne \mathsf{PSPACE}$. Let $L\subseteq \{0,1\}^{\star}$ be some $\mathsf{PSPACE}$-compete problem. Let $T$ be a Turing machine and $P(x)$ be a polynomial such that $T$ checks if $\alpha\in L$ using at most $P(|\alpha|)$ cells of the tape. For an appropriate polynomial $Q(x)$ that is strictly monotone as a function $\mathbb{N}\to\mathbb{N}$, we could naturally code all possible states of $T$ for computations on inputs $\alpha\in \{0,1\}^n$ as strings of the length $Q(n)$. Let $h$ be a polynomial time function preserving the lengths of strings such that whenever it maps codes of states of $T$ as above to the codes of states of $T$ after one step of computation (and we don't care what happen with the strings that are not codes as long as we preserve their lengths). For $\alpha,\beta,\gamma\in\{0,1\}^{Q(n)}$ let $\alpha'=\min(\alpha+1,2^{Q(n)}-1)$ and $\beta'=\min(\beta+1,2^{Q(n)}-1)$, where we treat strings of the length $Q(n)$ as codes for numbers $<2^{Q(n)}$, we put
$$f(\alpha\beta\gamma)=\alpha'\beta h^{\min(\alpha',\beta)-\min(\alpha,\beta)}(\gamma)\text{ and }g(\alpha\beta\gamma)=\alpha\beta'h^{\min(\alpha,\beta')-\min(\alpha,\beta)}(\gamma).$$
Clearly, $$f(g(\alpha\beta\gamma))=g(f(\alpha\beta\gamma)=\alpha'\beta'h^{\min(\alpha',\beta')-\min(\alpha,\beta)}(\gamma).$$
We don't care about the behavior's of $f,g$ on inputs of other forms (as long as we have commutation and length preservation). Since $\min(\alpha',\beta)-\min(\alpha,\beta)$ and $\min(\alpha,\beta')-\min(\alpha,\beta)$ are always either $0$ or $1$, we could make $f$ and $g$ polynomial time computable.


Assume for a contradiction that there is a polynomial time algorithm prescribed by Proposition 1. Let $u$ be the polynomial time function mapping $\alpha\in\{0,1\}^n$ to $u(\alpha)\in\{0,1\}^{Q(n)}$ that codes the initial state of $T$ for the computation on the input $\alpha$. Now for appropriate polynomial time $n'(x)$ and $m'(x)$ we should be able to compute in polynomial time $f^{2^{Q(|\alpha|)}}(g^{2^{Q(|\alpha|)}}(00u(\alpha)))$ from $2^{Q(|\alpha|)}$, $f^{n'(2^{Q(|\alpha|)})}(00u(\alpha))$ and $g^{m'(2^{Q(|\alpha|)})}(00u(\alpha))$; here I am abusing the notation and by $00u(\alpha)$ I mean the string of the length $3Q(n)$ coding triple consisting of $0,0$, and $u(\alpha)$. Clearly, $$f^{2^{Q(|\alpha|)}}(g^{2^{Q(|\alpha|)}}(00u(\alpha)))=(2^{Q(|\alpha|)-1})(2^{Q(|\alpha|)-1})h^{2^{Q(|\alpha|)}-1}(u(\alpha)),$$ $$f^{n'(2^{Q(|\alpha|)})}(00u(\alpha))= (\min(2^{Q(|\alpha|)-1},n'(2^{Q(|\alpha|)}))(0)u(\alpha)\text{, and}$$
$$g^{m'(2^{Q(|\alpha|)})}(00u(\alpha))= (0)(\min(2^{Q(|\alpha|)-1},m'(2^{Q(|\alpha|)}))u(\alpha).$$
Hence we could compute $h^{2^{Q(|\alpha|)}-1}$ in polynomial time from $\alpha$. But since $T$ on the input $\alpha$ terminates after at most $2^{Q(|\alpha|)}-1$ steps (simply due to the number of possible distinct states), $h^{2^{Q(|\alpha|)}-1}$ will always be the code of the terminal state of the computation of $T$ on the input $\alpha$. Hence we would be able to decide the problem $L$ in polynomial time. Contradiction.


