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

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: Leonard M. Adleman , Jonathan DeMarrais , Ming-Deh A. Huang, Quantum Computability, SIAM Journal on Computing, v.26 n.5, p.1524-1540, Oct. 1997 [doi>10.1137/S0097539795293639]
• 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: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 5: Ajtai, M. 1983. Σ11-formulae on finite structures. Ann. Pure Appl. Logic 24, 1--48.
• 6: M. Ajtai, Generating hard instances of lattice problems (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.99-108, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237838]
• 7: Eric Allender, Some pointed questions concerning asymptotic lower bounds, and news from the isomorphism front, Current trends in theoretical computer science: entering the 21st centuary, World Scientific Publishing Co., Inc., River Edge, NJ, 2001
• 8: N. Alon , R. B. Boppana, The monotone circuit complexity of Boolean functions, Combinatorica, v.7 n.1, p.1-22, Jan. 1987 [doi>10.1007/BF02579196]
• 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: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 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: Ravi B. Boppana , Michael Sipser, The complexity of finite functions, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 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: Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
• 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: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 24: Deutsch, D. 1989. Quantum computational networks. Proc. Roy. Soc. Lond. A 425, 73--90.
• 25: P. E. Dunne, The complexity of Boolean networks, Academic Press Professional, Inc., San Diego, CA, 1988
• 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: Yuri Gurevich, Average case completeness, Journal of Computer and System Sciences, v.42 n.3, p.346-398, June 1991 [doi>10.1016/0022-0000(91)90007-R]
• 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: John E. Hopcroft , Rajeev Motwani , Rotwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computability, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 38: Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
• 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: Richard M. Karp , Richard J. Lipton, Some connections between nonuniform and uniform complexity classes, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.302-309, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804678]
• 42: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 43: Donald E. Knuth, Selected papers on computer science, Cambridge University Press, New York, NY, 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: Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
• 46: Ming Li , Paul M. B. Vitányi, Kolmogorov complexity and its applications, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 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: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 52: Nielsen, M. A., and Chuang, I. L. 2000. Quantum Computation and Quantum Information Theory. Cambridge University Press, Cambridge, UK.
• 53: Daniel N. Osherson, Judgement, Thinking (vol. 3): an invitation to cognitive science, MIT Press, Cambridge, MA, 1990
• 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: Nicholas Pippenger , Michael J. Fischer, Relations Among Complexity Measures, Journal of the ACM (JACM), v.26 n.2, p.361-381, April 1979 [doi>10.1145/322123.322138]
• 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: Edward L. Robertson, Structure of complexity in the weak monadic second-order theories of the natural numbers, Proceedings of the sixth annual ACM symposium on Theory of computing, p.161-171, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803895]
• 62: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 63: Ruzzo, W. L. 1981. On uniform circuit complexity. J. Comput. Syst. Sci. 22, 365--383.
• 64: J. E. Savage, Computational Work and Time on Finite Machines, Journal of the ACM (JACM), v.19 n.4, p.660-674, Oct. 1972 [doi>10.1145/321724.321731]
• 65: John E. Savage, The Complexity of Computing, Krieger Publishing Co., Inc., Melbourne, FL, 1987
• 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: Ingo Wegener, The complexity of Boolean functions, John Wiley & Sons, Inc., New York, NY, 1987
• 80: Christopher B Wilson, Relativized circuit complexity, Journal of Computer and System Sciences, v.31 n.2, p.169-181, Sept. 1985 [doi>10.1016/0022-0000(85)90040-6]
• 81: Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States
• 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Mechanical theorem proving

General Terms:
Theory, Verification

Keywords:
Circuit complexity, WS1S, computational complexity, decision problem, logic, lower bound, practical undecidability