Amplifying circuit lower bounds against polynomial time, with applications |
| |
Authors: | Richard J. Lipton Ryan Williams |
| |
Affiliation: | 1. College of Computing, Georgia Institute of Technology, Atlanta, GA, USA 2. Computer Science Department, Stanford University, Stanford, CA, USA
|
| |
Abstract: | We give a self-reduction for the Circuit Evaluation problem (CircEval) and prove the following consequences. - Amplifying size–depth lower bounds. If CircEval has Boolean circuits of n k size and n 1?δ depth for some k and δ, then for every ${epsilon > 0}$ , there is a δ′ > 0 such that CircEval has circuits of ${n^{1 + epsilon}}$ size and ${n^{1- delta^{prime}}}$ depth. Moreover, the resulting circuits require only ${tilde{O}(n^{epsilon})}$ 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[n c ], or the Circuit Evaluation problem cannot be solved with circuits of n d size and n e depth. This implies unconditional polynomial-time uniform circuit lower bounds for solving QBF. We also prove that QBF does not have n c -time uniform NC circuits, for all c < 2.
|
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|