Exponential lower bounds for restricted monotone circuits
Exponential lower bounds for restricted monotone circuits
复制标题
受限单调电路的指数下界
DOI：
10.1145/800061.808739
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
L. Valiant
中科院分区：
文献类型：
--
作者：
L. Valiant
在本文中，我们考虑具有三种交替的单调布尔电路，按“或”、“和”、“或”的顺序。每当交替次数限制为固定常数时，公式和电路尺寸度量就彼此呈多项式相关。因此，我们将该度量可互换地称为 ΣπΣ 公式大小或 ΣπΣ 电路大小。我们将证明，任何用于检测 N 节点图中是否存在派系的电路或公式对于某些与 N 无关的 ε > 0 至少具有 2Ω(Nε) 个门。
In this paper we consider monotone Boolean circuits with three alternations, in the order “or”, “and”, “or.” Whenever the number of alternations is limited to a fixed constant the formula and circuit size measures are polynomially related to each other. We shall therefore refer to this measure interchangeably as ΣπΣ-formula size or ΣπΣ-circuit size. We shall prove that any such circuit or formula for detecting the existence of cliques in an N-node graph has at least 2Ω(Nε) gates for some ε > 0 independent of N.