8
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Nov 4, 2022 at 6:34
  • $\begingroup$ The expression $f^a$ means: $f$ applied $a$ times, like $f(f(f(...(x))))$. I will edit the question to clarify the notation. $\endgroup$ Nov 4, 2022 at 8:51
  • 1
    $\begingroup$ 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? $\endgroup$ Nov 4, 2022 at 9:07
  • $\begingroup$ 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. $\endgroup$ Nov 4, 2022 at 9:23
  • $\begingroup$ After the answer of Fedor Pakhomov, I proposed a slightly weaker version of Prop. 1 here : mathoverflow.net/questions/433954/… . $\endgroup$ Nov 5, 2022 at 12:18

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Nov 4, 2022 at 22:40
  • $\begingroup$ @DorianoBrogioli I don't know, this is a really vague question. And I am not really sure what you would consider to be an improvement of the example. $\endgroup$ Nov 5, 2022 at 1:05
  • $\begingroup$ I tried to formalize a weaker version of the proposition, here: mathoverflow.net/questions/433954/… . If I am not wrong, it includes your example, but is still difficult to prove or dis-prove for me. $\endgroup$ Nov 5, 2022 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.