Amplifying Circuit Lower Bounds against Polynomial Time with Applications
Richard J. Lipton, Ryan Williams · 2012
We give a self-reduction for the Circuit Evaluation problem (CircEval), and prove the following consequences. · Amplifying Size-Depth Lower Bounds. If CIRCEVAL ϵ SIZEDEPTH [nk, n1-δ] for some k and δ, then for every ε >; 0, there is a δ >; 0, there is a δ' >; 0 such that CIRCEVAL ϵ SIZEDEPTH [nk, n1-δ']. Moreover, the resulting circuits require only O(nε) bits of non-uniformity to construct. As a consequence, strong enough depth lower bounds for Circuit Evaluation imply a full separation of P and NC (even with a weak size lower bound). · Lower Bounds for Quantified Boolean Formulas. Let c,d >; 1 and e <; 1 satisfy c <; (1 - e + d)/d. Either the problem of recognizing valid quantified Boolean formulas (QBF) is not solvable in TIME[nc], or the Circuit Evaluation problem cannot be solved with circuits of nd size and ne depth. This implies unconditional polynomial-time uniform circuit lower bounds for solving QBF.