It is well-known that every permutation can be written as the composition of two involutions.

Suppose that $p$ is a polynomial. Then does there exist a polynomial $q$ such that if $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ and its inverse are permutations which are computable by combinatorial circuits with at most $p(n)$ gates, then there exists involutions $g,h:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ such that $f=g\circ h$ and where $g,h$ are computable by a combinatorial circuit with at most $q(n)$ gates?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.