### Cosmological lower bound on the circuit complexity of a small problem in logicCosmological lower bound on the circuit complexity of a small problem in logic

Access Restriction
Subscribed

 Author Stockmeyer, Larry ♦ Meyer, Albert R. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2002 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Circuit complexity ♦ WS1S ♦ Computational complexity ♦ Decision problem ♦ Logic ♦ Lower bound ♦ Practical undecidability Abstract 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 $10^{125}$ 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.* ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2002-11-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 49 Issue Number 6 Page Count 32 Starting Page 753 Ending Page 784

#### Open content in new tab

Source: ACM Digital Library