2002/11/01 by Larry Stockmeyer, Albert R. Meyer · 2 citations
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Quantum Computing Algorithms and Architecture #Benford’s Law and Fraud Detection
paper · doi:10.1145/602220.602223
openalex publication_date 2002/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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.*