Michael Sipser
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.
- 1.D. Angluin, "On counting problems and the polynomial time hierarchy," TCS, to appear.Google Scholar
- 2.T. Baker and A. Selman, "A second step toward the polynomial time hierarchy," 17th FOCS, 1976, 71-75Google Scholar
- 3.A. Borodin, "On relating time and space to size and width," SIAM J. Comput. 6, 1977, 733-744.Google ScholarDigital Library
- 4.A. Borodin, D. Dolev, F. Fich, and W. Paul, "Bounds for width two branching programs," 15th STOCL. Google ScholarDigital Library
- 5.A. Chandra, L. Stockmeyer, V. Vishkin, "A complexity theory for unbounded fan-in parallelism." 23rd FOCS, 1982, 2-13.Google Scholar
- 6.A. Chandra, D. Kozen, and L. Stockmeyer, "Alternation," JACM, 28, 1981 Google ScholarDigital Library
- 7.S. Cook, "Towards a complexity theory of synchronous parallel computation," Univ. of Toronto Computer Science Dept. Tech. Report 141/80, 1980.Google Scholar
- 8.P. Dymond and S. Cook, "Hardware complexity and parallel computation," 21st FOCS, 360-372, 1980.Google Scholar
- 9.M. Furst, J. B. Saxe, and M. Sipser, "Parity, circuits, and the polynomial time hierarchy," 22nd FOCS, 1981, 260-270.Google Scholar
- 10.J. Hong, "On simularity and duality of computation," 21st FOCS, 1980, 348-359.Google Scholar
- 11.N. Immerman, "Languages which capture complexity classes," 15th STOC, 1983. Google ScholarDigital Library
- 12.K. Kuratowski, Topology, Academic Press, 1966.Google Scholar
- 13.C. Mead and C. Conway, Introduction to VLSI Systems, Addison-Wesley, Reading, Mass., 1980. Google ScholarDigital Library
- 14.W. Paul, "A 2.5n lower bound for the combinatorial complexity of Boolean functions," 7th SIGACT, 1975, 27-36. Google ScholarDigital Library
- 15.N. Pippenger, "On simultaneous resources bounds," 20th FOCS, 1979, 307-311.Google Scholar
- 16.W.L. Russo, "On uniform circuit complexity," 20th FOCS, 1979, 312-318.Google Scholar
- 17.W. L. Russo, "Tree size bounded alternation," JCSS, 21, 218-235, 1980.Google Scholar
- 18.C. Schnorr, "The network complexity and Turing Machine complexity of finite functions," Acts Informa., 7, 1976, 95-107.Google ScholarDigital Library
- 19.L. J. Stockmeyer and V. Vishkin, "Simulation of parallel random access machines by circuits," RC 9362, IBM research report, 1982.Google Scholar
- 20.M. Sipser, "Lower bounds on the size of sweeping automata," JCSS, 21Google Scholar
- 21.M. Sipser, "On polynomial vs. exponentiàl growth," MIT Tech. Report, to appear.Google Scholar
- 22.L. Valiant, "Exponential lower bounds for restricted monotone formulae," 15th STOC. Google ScholarDigital Library
Index Terms
- Borel sets and circuit complexity
Recommendations
On the (non) NP-hardness of computing circuit complexity
CCC '15: Proceedings of the 30th Conference on Computational ComplexityThe Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. ...
An Isomorphism Theorem for Circuit Complexity
CCC '96: Proceedings of the 11th Annual IEEE Conference on Computational ComplexityWe show that all sets complete for NC1 under AC0 reductions are isomorphic under AC0-computable isomorphisms. Although our proof does not generalize directly to other complexity classes, we do show that, for all complexity classes C closed under NC1-...
Comments