Deterministic restrictions in circuit complexity
Deterministic restrictions in circuit complexity
复制标题
电路复杂性的确定性限制
DOI：
10.1145/237814.237824
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
J. Radhakrishnan
中科院分区：
文献类型：
--
作者：
S. Chaudhuri;J. Radhakrishnan
我们研究了使用与门、或门和非门计算布尔函数的复杂性。我们证明了深度d的S门电路可以通过设置其输入值的O(S1−)（其中(d) = 4−d）来输出常数。这意味着一个超线性大小的下界对于一个大的函数类。利用这一点，我们得到了一个函数，该函数可由一组等深度多项式大小的电路计算，而不能由线性大小的等深度电路计算。我们给出了电路结构，表明界O（S1−）是接近最优的。我们还研究了计算阈值函数的复杂性。函数T r的值为1如果它的输入中至少有r个值为1。我们证明了计算tr的电路至少有Ω（r (logn)/ log r）个门，对于r≤n，改进了先前的界限。我们还展示了门限电路中门数和线数之间的权衡，即具有G （< n/2）个门和W条线计算T r的电路满足W≥Ω(nr(logn)/(log(G/ logn)))，这表明不可能同时优化门限电路中的门数和线数。我们的阈值函数的界是基于一个独立的组合引理。
We study the complexity of computing Boolean functions using AND, OR and NOT gates. We show that a circuit of depth d with S gates can be made to output a constant by setting O(S1− ) (where (d) = 4−d) of its input values. This implies a superlinear size lower bound for a large class of functions. Using this, we obtain a function computable by a uniform family of constant depth polynomial size circuits that cannot be computed by constant depth circuits of linear size. We give circuit constructions that show that the bound O(S1− ) is near optimal. We also study the complexity of computing threshold functions. The function T r has the value 1 iff at least r of its inputs have the value 1. We show that a circuit computing T r has at least Ω(r (logn)/ log r) gates, for r ≤ n, improving previous bounds. We also show a trade-off between the number of gates and the number of wires in a threshold circuit, namely, a circuit with G (< n/2) gates and W wires computing T r satisfies W ≥ Ω(nr(logn)/(log(G/ logn))), showing that it is not possible to simultaneously optimize the number of gates and wires in a threshold circuit. Our bounds for threshold functions are based on a combinatorial lemma of independent interest.