pith. sign in

arxiv: 0912.3730 · v2 · pith:KEW7ZC2Lnew · submitted 2009-12-18 · 💻 cs.CC

On the circuit-size of inverses

classification 💻 cs.CC
keywords computabletherecircuitcircuitsdifferentexistfamilyfunctions
0
0 comments X
read the original abstract

We reprove a result of Boppana and Lagarias: If Pi_2^P is different from Sigma_2^P then there exists a partial function f that is computable by a polynomial-size family of circuits, but no inverse of f is computable by a polynomial-size family of circuits. We strengthen this result by showing that there exist length-preserving total functions that are one-way by circuit size and that are computable in uniform polynomial time. We also prove, if Pi_2^P is different from Sigma_2^P, that there exist polynomially balanced total surjective functions that are one-way by circuit size; here non-uniformity is used.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.