Exponential Lower Bounds for AC~0-Frege Imply Superpolynomial Frege Lower Bounds

摘要

We give a general transformation that turns polynomial-size Frege proofs into subexponential-size AC~0-Frege proofs. This indicates that proving truly exponential lower bounds for AC~0-Frege is hard, as it is a long-standing open problem to prove superpolynomial lower bounds for Frege. Our construction is optimal for proofs of formulas of unbounded depth. As a consequence of our main result, we are able to shed some light on the question of automatizability for bounded-depth Frege systems. First, we present a simpler proof of the results of Bonet et al. showing that under cryptographic assumptions, bounded-depth Frege proofs are not automatizable. Second, we show that because our proof is more general, under the right cryptographic assumptions, it could resolve the automatizability question for lower-depth Frege systems.