Amplifying circuit lower bounds against polynomial time, with applications
Amplifying circuit lower bounds against polynomial time, with applications
复制标题
放大电路针对多项式时间的下限及其应用
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Ryan Williams
中科院分区：
文献类型：
--
作者：
R. Lipton;Ryan Williams
本文给出了电路评估问题（CircEval）的一个自归约，并证明了下列结论。
放大大小深度下限。如果CircEval有nk大小和n1−δ深度的布尔电路，对于某个k和δ，则对于每个$${\displaystyle\delta ^{1-\delta ^{\prime}}$$，有一个δ′ > 0使得CircEval有$${n^{1 + \delta}}$$大小和$${n^{1- \delta^{\prime}}$$$深度的电路。此外，所得到的电路只需要$${\tilde{O}（n^{\displaystyle}）}$$位的非均匀性来构造。因此，足够强的电路评估深度下限意味着P和NC的完全分离（即使具有弱大小下限）。设c，d > 1且e < 1满足c <（1 − e + d）/d。识别有效量化布尔公式（QBF）的问题在TIME[nc]中是不可解的，或者电路评估问题不能用ND大小和NE深度的电路来解决。这意味着无条件的多项式时间均匀电路下限解决QBF。我们还证明了QBF不具有nc-时间一致的NC回路，对所有的c < 2。
AbstractWe 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 nk size and n1−δ 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[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. We also prove that QBF does not have nc-time uniform NC circuits, for all c < 2.