Borel sets and circuit complexity

ABSTRACT

It is shown that for every k, polynomial-size, depth-k Boolean circuits are more powerful than polynomial-size, depth-(k−1) Boolean circuits. Connections with a problem about Borel sets and other questions are discussed.

REFERENCES

• 1: D. Angluin, "On counting problems and the polynomial time hierarchy," TCS, to appear.
• 2: T. Baker and A. Selman, "A second step toward the polynomial time hierarchy," 17th FOCS, 1976, 71-75
• 3: A. Borodin, "On relating time and space to size and width," SIAM J. Comput. 6, 1977, 733-744.
• 4: Allan Borodin , Danny Dolev , Faith E. Fich , Wolfgang Paul, Bounds for width two branching programs, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.87-93, December 1983 [doi>10.1145/800061.808736]
• 5: A. Chandra, L. Stockmeyer, V. Vishkin, "A complexity theory for unbounded fan-in parallelism." 23rd FOCS, 1982, 2-13.
• 6: 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]
• 7: S. Cook, "Towards a complexity theory of synchronous parallel computation," Univ. of Toronto Computer Science Dept. Tech. Report 141/80, 1980.
• 8: P. Dymond and S. Cook, "Hardware complexity and parallel computation," 21st FOCS, 360-372, 1980.
• 9: M. Furst, J. B. Saxe, and M. Sipser, "Parity, circuits, and the polynomial time hierarchy," 22nd FOCS, 1981, 260-270.
• 10: J. Hong, "On simularity and duality of computation," 21st FOCS, 1980, 348-359.
• 11: Neil Immerman, Languages which capture complexity classes, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.347-354, December 1983 [doi>10.1145/800061.808765]
• 12: K. Kuratowski, Topology, Academic Press, 1966.
• 13: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 14: Wolfgang J. Paul, A 2.5 n-lower bound on the combinational complexity of Boolean functions, Proceedings of seventh annual ACM symposium on Theory of computing, p.27-36, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803750]
• 15: N. Pippenger, "On simultaneous resources bounds," 20th FOCS, 1979, 307-311.
• 16: W.L. Russo, "On uniform circuit complexity," 20th FOCS, 1979, 312-318.
• 17: W. L. Russo, "Tree size bounded alternation," JCSS, 21, 218-235, 1980.
• 18: C. Schnorr, "The network complexity and Turing Machine complexity of finite functions," Acts Informa., 7, 1976, 95-107.
• 19: L. J. Stockmeyer and V. Vishkin, "Simulation of parallel random access machines by circuits," RC 9362, IBM research report, 1982.
• 20: M. Sipser, "Lower bounds on the size of sweeping automata," JCSS, 21
• 21: M. Sipser, "On polynomial vs. exponentiàl growth," MIT Tech. Report, to appear.
• 22: L. G. Valiant, Exponential lower bounds for restricted monotone circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.110-117, December 1983 [doi>10.1145/800061.808739]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Theory