More Web Proxy on the site http://driver.im/

article

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

Authors:

Larry Stockmeyer,

Albert R. MeyerAuthors Info & Claims

Journal of the ACM (JACM), Volume 49, Issue 6

Pages 753 - 784

https://doi.org/10.1145/602220.602223

Published: 01 November 2002 Publication History

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¹²⁵ 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.*

References

[1]

Adleman, L. 1978. Two theorems on random polynomial time. In Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 75--83.

[2]

Adleman, L. M., Demarrais, J., and Huang, M.-D. A. 1997. Quantum computability. SIAM J. Comput. 26, 1524--1540.

[3]

Aharonov, D. 1998. Quantum computation--A review. In Annual Reviews of Computational Physics, Vol. IV, D. Stauffer, Ed. World Scientific Press, River Edge, N.J.

[4]

Aho, A. V., Hopcroft, J. E., and Ullman, J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass.

[5]

Ajtai, M. 1983. Σ11-formulae on finite structures. Ann. Pure Appl. Logic 24, 1--48.

[6]

Ajtai, M. 1996. Generating hard instances of lattice problems. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing. ACM, New York. Full version: Report TR96-007, Electronic Colloquium on Computational Complexity, http://www.eccc.uni-trier.de/eccc/.

[7]

Allender, E. 2001. Some pointed questions concerning asymptotic lower bounds and news from the isomorphism front. In Current Trends in Theoretical Computer Science, G. Paun, G. Rozenberg, and A. Salomaa, Eds. World Scientific Press, River Edge, N.J., 25--41.

[8]

Alon, N., and Boppana, R. B. 1987. The monotone circuit complexity of Boolean functions. Combinatorica 7, 1--23.

[9]

Andreev, A. E. 1985. On a method for obtaining lower bounds for the complexity of individual monotone functions. Dokl. Ak. Nauk SSSR 282, 1033--1037. English translation in Sov. Math. Dokl. 31, 530--534.

[10]

Baker, T., Gill, J., and Solovay, R. 1975. Relativizations of the P =? NP question. SIAM J. Comput. 4, 431--442.

[11]

Bennett, C. H., and Gill, J. 1981. Relative to a random oracle A, PA ≠ NPA ≠ co-NPA with probability 1. SIAM J. Comput. 10, 96--113.

[12]

Berman, L. 1980. The complexity of logical theories. Theoret. Comput. Sci. 11, 71--77.

[13]

Berman, L., and Hartmanis, J. 1977. On isomorphisms and density of NP and other complete sets. SIAM J. Comput. 6, 305--322.

[14]

Bernstein, E., and Vazirani, U. 1997. Quantum complexity theory. SIAM J. Comput. 26, 1411--1473.

[15]

Blum, M. 1966. Recursive function theory and speed of computation. Canadian Math. Bull. 9, 745--749.

[16]

Blum, N. 1984. A Boolean function requiring 3n network size. Theoret. Comp. Sci. 28, 337--345.

[17]

Boppana, R. B., and Sipser, M. 1990. The complexity of finite functions. In Handbook of Theoretical Computer Science, Volume A, Algorithms and Complexity, J. van Leeuwen, Ed. Elsevier, New York, Chapter 14, 757--804.

[18]

Borodin, A. 1977. On relating time and space to size and depth. SIAM J. Comput. 6, 733--743.

[19]

Büchi, J. R. 1960. Weak second order arithmetic and finite automata. Z. Math. Logik Grundl. Math. 6, 66--92.

[20]

Chaitin, G. J. 1995. The Berry paradox. Complexity 1, 26--30.

[21]

Chandra, A. K., Kozen, D. C., and Stockmeyer, L. J. 1981. Alternation. J. ACM 28, 114--133.

[22]

Cobham, A. 1965. The intrinsic computational difficulty of functions. In Proceedings of the 1964 International Congress for Logic, Methodology and Philosophy of Science, Y. Bar-Hillel, Ed. North-Holland, Amsterdam, 24--30.

[23]

Cook, S. A. 1971. The complexity of theorem proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing. ACM, New York, 151--158.

[24]

Deutsch, D. 1989. Quantum computational networks. Proc. Roy. Soc. Lond. A 425, 73--90.

[25]

Dunne, P. E. 1988. The Complexity of Boolean Networks. Academic Press, New York.

[26]

Edmonds, J. 1965. Paths, trees and flowers. Canad. J. Math. 17, 449--467.

[27]

Ehrenfeucht, A. 1975. Practical decidability. J. Comput. Syst. Sci. 11, 392--396.

[28]

Elgot, C. C. 1961. Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc. 98, 21--51.

[29]

Fischer, M. J., and Rabin, M. O. 1974. Super-exponential complexity of Presburger arithmetic. In Complexity of Computation, SIAM-AMS Proceedings, vol. 7, R. Karp, Ed. American Mathematical Society, Providence, R.I., 27--42.

[30]

Furst, M., Saxe, M., and Sipser, M. 1984. Parity, circuits, and the polynomial time hierarchy. Math. Syst. Theory 17, 13--27.

[31]

Gill, J. 1977. Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6, 675--695.

[32]

Gurevich, Y. 1991. Average case completeness. J. Comput. Syst. Sci. 42, 346--398.

[33]

Harper, L. H., Hsieh, W. N., and Savage, J. E. 1975. A class of Boolean function with linear combinational complexity. Theoret. Comput. Sci. 1, 161--183.

[34]

Harrison, M. A. 1965. Introduction to Switching and Automata Theory. McGraw-Hill, New York.

[35]

Hartmanis, J., and Stearns, R. E. 1965. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 285--306.

[36]

Håstad, J. 1986. Almost optimal lower bounds for small depth circuits. In Advances in Computer Research, Vol. 5: Randomness and Computation, S. Micali, Ed. JAI Press, Greenwich, CT.

[37]

Hopcroft, J. E., and Ullman, J. D. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass.

[38]

Impagliazzo, R., and Wigderson, A. 1997. P=BPP unless E has sub-exponential circuits: Derandomizing the XOR lemma. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM, New York, 220--229.

[39]

Kannan, R. 1982. Circuit-size lower bounds and non-reducibility to sparse sets. Inf. Cont. 55, 40--56.

[40]

Karp, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. Plenum Press, New York, 85--103.

[41]

Karp, R. M., and Lipton, R. J. 1980. Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing. ACM, New York, 302--309.

[42]

Knuth, D. E. 1969. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. Addison-Wesley, Reading, Mass.

[43]

Knuth, D. E. 1976. Mathematics and computer science: coping with finiteness. Science 194, 1235--1242. Reprinted in: D. E. Knuth, Selected Papers in Computer Science, Cambridge University Press, Cambridge, UK, 1996.

[44]

Levin, L. A. 1973. Universal sorting problems. Problemy Peredaci Informacii 9, 115--116. English translation in Prob. Inf. Trans. 9, 265--266.

[45]

Levin, L. A. 1986. Average case complete problems. SIAM J. Comput. 15, 285--286.

[46]

Li, M., and Vitányi, P. M. 1990. Kolmogorov complexity and its applications. In Handbook of Theoretical Computer Science, Volume A, Algorithms and Complexity, J. van Leeuwen, Ed. Elsevier, New York, Chapter 4, 187--254.

[47]

Lupanov, O. B. 1958. Ob odnom metode sinteza skhem. Izv. VUZ (Radiofizika) 1, 120--140.

[48]

Meyer, A. R. 1975. Weak monadic second-order theory of successor is not elementary-recursive. In Logic Colloquium: Symposium on Logic Held at Boston 1972-73. Lecture Notes in Mathematics, vol. 453, R. Parikh, Ed. Springer-Verlag, Berlin, 132--154.

[49]

Meyer, A. R., and McCreight, E. M. 1971. Computationally complex and pseudo-random zero-one valued functions. In Theory of Machines and Computations. Academic Press, New York, 19--42.

[50]

Meyer, A. R., and Stockmeyer, L. J. 1972. The equivalence problem for regular expressions with squaring requires exponential space. In Proceedings of the 13th Annual IEEE Symposium on Switching and Automata Theory. IEEE Computer Society Press, Los Alamitos, Calif., 125--129.

[51]

Motwani, R., and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press, Cambridge, UK.

[52]

Nielsen, M. A., and Chuang, I. L. 2000. Quantum Computation and Quantum Information Theory. Cambridge University Press, Cambridge, UK.

[53]

Osherson, D. 1995. Probability judgement. In An Invitation to Cognitive Science, Vol. 3: Thinking, 2nd ed., E. E. Smith and D. Osherson, Eds. MIT Press, Cambridge, MA.

[54]

Paul, W. 1977. A 2.5n-lower bound on the combinational complexity of Boolean functions. SIAM J. Comput. 6, 427--443.

[55]

Pippenger, N. 1979. On simultaneous resource bounds. In Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 307--311.

[56]

Pippenger, N., and Fischer, M. J. 1979. Relations among complexity measures. J. ACM 26, 361--381.

[57]

Pohl, F. 1980. Beyond the Blue Event Horizon. Ballantine Books, New York, Chapter 12.

[58]

Rabin, M. O. 1960. Degree of difficulty of computing a function and a partial ordering of recursive sets. Tech. Rep. 2, Hebrew Univ., Jerusalem, Israel.

[59]

Rabin, M. O. 1976. Probabilistic algorithms. In Algorithms and Complexity, New Directions and Recent Trends, J. F. Traub, Ed. Academic Press, New York, 21--29.

[60]

Razborov, A. A. 1985. Lower bounds on the monotone complexity of some Boolean functions. Dokl. Ak. Nauk SSSR 281, 798--801. English translation in Sov. Math. Dokl. 31, 354--357.

[61]

Robertson, E. L. 1974. Structure of complexity in the weak monadic second-order theories of the natural numbers. In Proceedings of the 6th Annual ACM Symposium on Theory of Computing. ACM, New York, 161--171.

[62]

Rogers, Jr., H. 1967. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York.

[63]

Ruzzo, W. L. 1981. On uniform circuit complexity. J. Comput. Syst. Sci. 22, 365--383.

[64]

Savage, J. E. 1972. Computational work and time on finite machines. J. ACM 19, 660--674.

[65]

Savage, J. E. 1976. The Complexity of Computing. Wiley, New York.

[66]

Scarpellini, B. 1985. Complex Boolean networks obtained by diagonalization. Theoret. Comput. Sci. 36, 119--125.

[67]

Schnorr, C. P. 1974. Zwei lineare untere shranken für die komplexität Boolescher funktionen. Computing 13, 155--171.

[68]

Schnorr, C. P. 1976a. A lower bound on the number of additions in monotone computations. Theoret. Comp. Sci. 2, 305--315.

[69]

Schnorr, C. P. 1976b. The network complexity and the Turing machine complexity of finite functions. Acta Inform. 7, 95--107.

[70]

Shannon, C. E. 1949. The synthesis of two-terminal switching circuits. Bell Syst. Tech. J. 28, 59--98.

[71]

Sholomov, L. A. 1975. On one sequence of functions which is hard to compute. Mat. Zametki 17, 957--966.

[72]

Solovay, R., and Strassen, V. 1977. A fast Monte-Carlo test for primality. SIAM J. Comput. 6, 84--85. Erratum: SIAM J. Comput. 7, 118.

[73]

Solovay, R., and Yao, A. 1996. Manuscript, not yet published.

[74]

Stockmeyer, L. J. 1974. The complexity of decision problems in automata theory and logic. Tech. Rep. MAC TR-133, MIT Project MAC, Cambridge, MA.

[75]

Stockmeyer, L. J. 1977a. On the combinational complexity of certain symmetric Boolean functions. Math. Syst. Th. 10, 323--366.

[76]

Stockmeyer, L. J. 1977b. The polynomial-time hierarchy. Theoret. Comput. Sci. 3, 1--22.

[77]

Stockmeyer, L. J. 1987. Classifying the computational complexity of problems. J. Symb. Logic 52, 1--43.

[78]

Stockmeyer, L. J., and Chandra, A. K. 1979. Intrinsically difficult problems. Sci. Amer. 240, May, 140--159.

[79]

Wegener, I. 1987. The Complexity of Boolean Functions. Wiley-Teubner, New York, Stuttgart.

[80]

Wilson, C. B. 1985. Relativized circuit complexity. J. Comput. Syst. Sci. 31, 169--181.

[81]

Yao, A. C. 1985. Separating the polynomial-time hierarchy by oracles. In Proceedings of the 26rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 1--10.

[82]

Yao, A. C. 1993. Quantum circuit complexity. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 352--361.

Cited By

Raya RKunčak V(2024)Succinct ordering and aggregation constraints in algebraic array theoriesJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2024.100978140(100978)Online publication date: Aug-2024
https://doi.org/10.1016/j.jlamp.2024.100978
Raya RKunčak V(2024)On algebraic array theoriesJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2023.100906136(100906)Online publication date: Jan-2024
https://doi.org/10.1016/j.jlamp.2023.100906
Geatti LMansutti AMontanari A(2024)Succinctness of Cosafety Fragments of LTL via Combinatorial Proof SystemsFoundations of Software Science and Computation Structures10.1007/978-3-031-57231-9_5(95-115)Online publication date: 6-Apr-2024
https://doi.org/10.1007/978-3-031-57231-9_5
Show More Cited By

Index Terms

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

Recommendations

On the Lower Bound to the VLSI Complexity of Number Conversion from Weighted to Residue Representation

A lower bound AT/sup 2/= Omega (n/sup 2/) for the conversion from positional to residue representation is derived according to VLSI complexity theory, and existing solutions for the same problem are briefly reviewed in the light of such a bound. A VLSI ...
Circuit Bottom Fan-in and Computational Power

We investigate the relationship between circuit bottom fan-in and circuit size when circuit depth is fixed. We show that in order to compute certain functions, a moderate reduction in circuit bottom fan-in will cause significant increase in circuit ...
A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates

In this paper, we investigate the lower bound on the number of gates in a Boolean circuit that computes the clique function with a limited number of negation gates. To derive strong lower bounds on the size of such a circuit we develop a new approach by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 49, Issue 6

November 2002

144 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/602220

Issue’s Table of Contents

Copyright © 2002 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2002

Published in JACM Volume 49, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
942
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Raya RKunčak V(2024)Succinct ordering and aggregation constraints in algebraic array theoriesJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2024.100978140(100978)Online publication date: Aug-2024
https://doi.org/10.1016/j.jlamp.2024.100978
Raya RKunčak V(2024)On algebraic array theoriesJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2023.100906136(100906)Online publication date: Jan-2024
https://doi.org/10.1016/j.jlamp.2023.100906
Geatti LMansutti AMontanari A(2024)Succinctness of Cosafety Fragments of LTL via Combinatorial Proof SystemsFoundations of Software Science and Computation Structures10.1007/978-3-031-57231-9_5(95-115)Online publication date: 6-Apr-2024
https://doi.org/10.1007/978-3-031-57231-9_5
Aminof BMurano ARubin SZuleger F(2022)Verification of agent navigation in partially-known environmentsArtificial Intelligence10.1016/j.artint.2022.103724308:COnline publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1016/j.artint.2022.103724
Boonmee ASethanan K(2016)A GLNPSO for multi-level capacitated lot-sizing and scheduling problem in the poultry industryEuropean Journal of Operational Research10.1016/j.ejor.2015.09.020250:2(652-665)Online publication date: Apr-2016
https://doi.org/10.1016/j.ejor.2015.09.020
Williams R(2014)Algorithms for Circuits and Circuits for AlgorithmsProceedings of the 2014 IEEE 29th Conference on Computational Complexity10.1109/CCC.2014.33(248-261)Online publication date: 11-Jun-2014
https://dl.acm.org/doi/10.1109/CCC.2014.33
De Giacomo GVardi M(2013)Linear temporal logic and linear dynamic logic on finite tracesProceedings of the Twenty-Third international joint conference on Artificial Intelligence10.5555/2540128.2540252(854-860)Online publication date: 3-Aug-2013
https://dl.acm.org/doi/10.5555/2540128.2540252
Silvestri R(2013)Randomness and ComplexityThe Power of Algorithms10.1007/978-3-642-39652-6_10(235-250)Online publication date: 10-Sep-2013
https://doi.org/10.1007/978-3-642-39652-6_10
Courcelle BDurand I(2012)Automata for the verification of monadic second-order graph propertiesJournal of Applied Logic10.1016/j.jal.2011.07.00110:4(368-409)Online publication date: Dec-2012
https://doi.org/10.1016/j.jal.2011.07.001
Courcelle B(2012)On the model-checking of monadic second-order formulas with edge set quantificationsDiscrete Applied Mathematics10.1016/j.dam.2010.12.017160:6(866-887)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1016/j.dam.2010.12.017
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents