# Computational complexity and commuting functions

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.

• What exactly do you mean by $h^a$ and $h^b$? Are they taken modulo something? Or how else do you make it a length-preserving function? Nov 4, 2022 at 6:34
• The expression $f^a$ means: $f$ applied $a$ times, like $f(f(f(...(x))))$. I will edit the question to clarify the notation. Nov 4, 2022 at 8:51
• When you talk about the polynomial dependency on $n$ and $m$ do you mean that they are represented as binary expansions and the algorithms are working in polynomial time of their lengths? Nov 4, 2022 at 9:07
• Yes! The binary representations of $n$ and $m$ are part of the input. If we used the unary representation, Prop. 1 would become easy to prove. I will edit the question. Nov 4, 2022 at 9:23
• After the answer of Fedor Pakhomov, I proposed a slightly weaker version of Prop. 1 here : mathoverflow.net/questions/433954/… . Nov 5, 2022 at 12:18

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.
• I think it is correct: it proves that Prop. 1 is false. It is very ingenious, but maybe too much ad-hoc: I have the feeling that Prop. 1 could be slightly corrected to include this counter-example. It's just a feeling, due to the fact that there is a single "hard task", calculate $h^n$ for large $n$, that is carried on step-by-step by both $f$ and $g$. Suggestions to modify Prop. 1, or further counter-examples, are welcome. Nov 4, 2022 at 22:40