Suppose that $p$ is a polynomial. Then does there exist a polynomial $q$ where if $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ is a bijection where both $f$ and $f^{-1}$ are computable by circuits with at most $p(n)$ gates, then there exists involutions $\iota_{1},\dots,\iota_{k}:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ where $$f=\iota_{k}\circ\dots\circ\iota_{1}$$ and where each $\iota_{i}$ is computable by a circuit with at most $q(n)$ gates and where $k\leq q(n)$.


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.