Cosmological lower bound on the circuit complexity of a small problem in logic
Cosmological lower bound on the circuit complexity of a small problem in logic
复制标题
逻辑小问题电路复杂度的宇宙学下界
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Albert R. Meyer
中科院分区：
文献类型：
--
作者：
L. Stockmeyer;Albert R. Meyer
证明了决定弱一元二阶一后继理论（WS1S）电路复杂度的指数下界。电路由二进制运算或双输入门构成，它们计算任意布尔函数。特别地，在这种二阶语言中，要确定长度不超过610的逻辑公式的正确性，需要至少包含10125个门的电路。因此，即使每个门都是质子大小，电路也不适合已知的宇宙。这个结果和它的证明，由于两位作者，最初出现在1974年第一作者的博士论文中。本文给出了证明，把结果放到历史的角度，并将结果推广到概率电路
An exponential lower bound on the circuit complexity of deciding the weak monadic second-order theory of one successor (WS1S) is proved. Circuits are built from binary operations, or 2-input gates, which compute arbitrary Boolean functions. In particular, to decide the truth of logical formulas of length at most 610 in this second-order language requires a circuit containing at least 10125 gates. So even if each gate were the size of a proton, the circuit would not fit in the known universe. This result and its proof, due to both authors, originally appeared in 1974 in the Ph.D. thesis of the first author. In this article, the proof is given, the result is put in historical perspective, and the result is extended to probabilistic circuits.*