Computational complexity and commuting functions, examples and conjectures

Question

History of the question. I was proposing a conjecture here, called Prop. 1. Fedor Pakhomov showed a counter-example. Here I am proposing a slightly weaker version of the conjecture, Prop. 2, that holds for that counter-example and is still apparently hard to prove. An old version of the problem is also here.

Here is the question. We have two functions, $ f: \{0,1\}^* \to \{0,1\}^* $ and $ 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. An ingenious example is shown by Fedor Pakhomov as an answer to my previous question. However, in all the examples, the evolution obtained by repeatedly applying $f$ seems to be either independent of the evolution obtained by repeatedly applying $g$, or exactly the same. More rigorously, in the examples I have seen, the following proposition holds:

Proposition 2

For every polynomially-computable commuting functions $f$ and $g$ preserving the string length, there is an algorithm that gets as input the binary representation of two integers, $n$ and $m$, and a string $x$; it calculates the function $f^n[g^m(x)]$, operating in polynomial time (in the length of its input); it accesses at most once an oracle that calculates $f^{n'}(y)$ and $g^{m'}(z)$ (both), with some desired $n'$, $m'$, $y$, and $z$.

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$, $m'=m$, and $y=z=x$, 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 example shown by Fedor Pakhomov in the answer to my previous question also satisfies Prop. 2. In that case, it is enough to call an oracle that calculates $f^{n'}(y)$ ($g$ is not needed).

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

Answer 1

This is not a proper answer. I will give a construction of a pair of functions $f,g$ assuming the access to some cryptographic function $e$ that probably should form a counterexample for Proposition 2 under some reasonable computability-theoretic assumptions which I will not properly specify. Unfortunately my knowledge of complexity theory is a bit too shaky and hence it is a bit too hard for me to properly isolate the complexity-theoretic and cryptographic assumptions.

Assume that there is a polynomial time-computable length-preservable bijection $e\colon \{0,1\}^\star \to \{0,1\}^\star$ such that its inverse, even when restricted to the sequences consisting just of zeroes, is not polynomial time computable. This essentially is a cryptographic bijective hash function. Given the current state of the field, clearly there are no proofs for such a thing to exist, I don't know if there are reasonable candidates for such a function or if it is known that such kind of function couldn't exist (although, the latter would be very surprising).

Now I will modify an example from my answer to the previous question Computational complexity and commuting functions

I will construct functions $f_1,g_1$ that work in non-trivial way on strings of the form $\alpha\beta\gamma\delta\epsilon$, where $\alpha,\beta,\gamma\in \{0,1\}^Q(n)$ and $\delta,\epsilon\in\{0,1\}^n$. Naturally I will treat $\delta,\epsilon$ as elements of the additive group $\mathbb{Z}/\mathbb{Z}2^n$. Given an input $\alpha\beta\gamma\delta\epsilon$, let

1. $\alpha''=\alpha$ if $e(\delta)=0^n$ and $\alpha''=0$, otherwise;

2. $\beta''=\beta$ if $e(\epsilon)=0^n$ and $\beta''=0$, otherwise;

3. $\delta'=\delta$ if $e(\delta)=0^n$ and $\delta+1$, otherwise;

4. $\epsilon'=\epsilon$ if $e(\epsilon)=0^n$ and $\epsilon+1$, otherwise;

5. $\alpha'''=\min(\alpha''+1,2^{Q(n)}-1)$ if $e(\delta)=0^n$ and $\alpha'''=0$, otherwise;

6. $\beta'''=\min(\beta''+1,2^{Q(n)}-1)$ if $e(\epsilon)=0^n$ and $\beta'''=0$, otherwise;

7. $f_1(\alpha\beta\gamma\delta\epsilon)=\alpha'''\beta''h^{\min(\alpha''',\beta'')-\min(\alpha'',\beta'')}(\gamma)\delta'\epsilon$;

8. $g_1(\alpha\beta\gamma\delta\epsilon)=\alpha''\beta'''h^{\min(\alpha'',\beta''')-\min(\alpha'',\beta'')}(\gamma)\delta\epsilon'$.

The idea is essentially the same as in the previous example but now the precondition for two counter behaviour as in the previous example is that the unbounded search have already found a hard to find witness. Note that unless $e(\delta)=0^n$ (and $e^{-1}(0^n)$ should be hard to find), $f_1^{n'}(\alpha\beta\gamma\delta\epsilon)$ will be polynomial-time computable from $e^{-1}(0^n)$. So the idea of why Proposition 2 should fail is that for polynomial-time computable $n',m',z,y$, the only kind of extra information that could be in general extracted from $f_1^{n'}(y)$ and $g_1^{m'}(z)$ are $e$-preimages of some strings consisting just of zeroes. This $e$-preimages shouldn't be of much help to compute instances of the $\mathsf{PSPACE}$-complete problem in vast majority of cases.

This of course, is just a rough idea of why I expect examples of this kind to be counterexamples for your Proposition 2. The problem with formulating proper assumptions here is that we want to exclude several possible non-trivial interactions between the function $e$ and the hardness of $\mathsf{PSPACE}$-complete problem of choice. I could formulate something, but it will look quite ugly. Hope that nevertheless this answer transmits the intuition of why I think the conjecture from the question to be false.