Computational complexity and commuting functions

Question

EDIT: in this question, I was proposing a conjecture, Prop. 1. Fedor Pakhomov showed a counter-example. In this new question 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.

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.

Answer 1

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.