Abstract
We reprove a result of Boppana and Lagarias: If
$\Pi _2^{\rm{P}}\, \ne \,\Sigma _2^{\rm{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, if
$\Pi _2^{\rm{P}}\, \ne \,\Sigma _2^{\rm{P}}$
, 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^{\rm{P}}\, \ne \,\Sigma _2^{\rm{P}}$
, that there exist polynomially balanced total surjective functions that are one-way by circuit size; here non-uniformity is used.