Amplifying circuit lower bounds against polynomial time, with applications

被引:10
作者
Lipton, Richard J. [1 ]
Williams, Ryan [2 ]
机构
[1] Georgia Inst Technol, Coll Comp, Atlanta, GA 30332 USA
[2] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA
基金
美国国家科学基金会;
关键词
Circuit evaluation; quantified Boolean formulas; lower bounds; NC; size-depth trade-offs; SPACE TRADEOFFS; SIZE; DEPTH;
D O I
10.1007/s00037-013-0069-5
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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-delta) depth for some k and delta, then for every epsilon > 0, there is a delta' > 0 such that CircEval has circuits of n(1+epsilon) size and n(1-delta') depth. Moreover, the resulting circuits require only (O) over tilde (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.
引用
收藏
页码:311 / 343
页数:33
相关论文
共 50 条
[31]   Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity [J].
Forbes, Michael A. ;
Kumar, Mrinal ;
Saptharishi, Ramprasad .
31ST CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC 2016), 2016, 50
[32]   New Lower Bounds on Circuit Size of Multi-output Functions [J].
Demenkov, Evgeny ;
Kulikov, Alexander S. ;
Melanich, Olga ;
Mihajlin, Ivan .
THEORY OF COMPUTING SYSTEMS, 2015, 56 (04) :630-642
[33]   New Lower Bounds on Circuit Size of Multi-output Functions [J].
Evgeny Demenkov ;
Alexander S. Kulikov ;
Olga Melanich ;
Ivan Mihajlin .
Theory of Computing Systems, 2015, 56 :630-642
[34]   Lower Bounds Against Weakly-Uniform Threshold Circuits [J].
Chen, Ruiwen ;
Kabanets, Valentine ;
Kinne, Jeff .
ALGORITHMICA, 2014, 70 (01) :47-75
[35]   On sub-polynomial lower error bounds for quadrature of SDEs with bounded smooth coefficients [J].
Yaroslavtseva, Larisa ;
Mueller-Gronbach, Thomas .
STOCHASTIC ANALYSIS AND APPLICATIONS, 2017, 35 (03) :423-451
[36]   Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas [J].
Kayal, Neeraj ;
Limaye, Nutan ;
Saha, Chandan ;
Srinivasan, Srikanth .
STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, :119-127
[37]   Lower Bounds on Key Derivation for Square-Friendly Applications [J].
Skorski, Maciej .
34TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2017), 2017, 66
[38]   Range partitioning within sublinear time: Algorithms and lower bounds [J].
Ning, Baoling ;
Li, Jianzhong ;
Jiang, Shouxu .
THEORETICAL COMPUTER SCIENCE, 2021, 857 :177-191
[39]   LOWER BOUNDS FOR THE BLOWUP TIME OF SOLUTIONS TO A NONLINEAR PARABOLIC PROBLEM [J].
Li, Haixia ;
Gao, Wenjie ;
Han, Yuzhu .
ELECTRONIC JOURNAL OF DIFFERENTIAL EQUATIONS, 2014,
[40]   OPTIMAL LOWER BOUNDS ON THE DEPTH OF POLYNOMIAL-SIZE THRESHOLD CIRCUITS FOR SOME ARITHMETIC FUNCTIONS [J].
WEGENER, I .
INFORMATION PROCESSING LETTERS, 1993, 46 (02) :85-87