zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Parity, circuits, and the polynomial-time hierarchy. (English) Zbl 0534.94008
The authors investigate lower bounds on the size of Boolean circuits computing parity, multiplication and transitive closure. It is already known [O. B. Lupanov, Probl. Kibern. 6, 5-14 (1961; Zbl 0178.331)] that Boolean circuits of depth 2 computing the parity function must have an exponential number of gates (in the number of the variables). The authors investigate the more general case of constant depth and show, that the number of gates for the computation of the parity function cannot be polynomial. By reduction it is shown, that also some other problems are not computable by polynomial-size constant-depth circuits. For this purpose the authors define: f is constant-depth polynomial-size reducible to g (f cp g) if f can be realized with constant-depth polynomial-size circuits on literals, made up of , , - gates and gates computing g. It is shown, that parity can be cp -reduced to multiplication and to the transitive closure problem for Boolean matrices; thus multiplication and transitive closure are not computable by constant-depth polynomial-size circuits. Furthermore the authors give an application to the polynomial time hierarchy PH (PH A : the hierarchy relativized by the oracle A); using the complexity of the parity function, they show that there is an oracle A such that PSPACE A -PH A .
Reviewer: A.Leitsch

MSC:
94C10Switching theory, application of Boolean algebra; Boolean functions
68Q25Analysis of algorithms and problem complexity
03D15Complexity of computation
References:
[1]D. Angluin, Counting problems and the polynomial-time hierarchy.Theoretical Computer Science, to appear.
[2]N. Blum, A 2.75n lower bound for the combinational complexity of boolean functions. University of Saarbrucken, Technical Report.
[3]T. Baker, J. Gill, and R. Solovay, Relativizations of theP =? NP question.SIAM Journal of Computing, 4, 4, 1975.
[4]T. Baker and A. Selman, A second step toward the polynomial hierarchy.Theoretical Computer Science, 8, 2, 1979, pp. 177–187. · Zbl 0397.03023 · doi:10.1016/0304-3975(79)90043-4
[5]A. Chandra, D. Kozen, and L. Stockmeyer, Alternation.Journal of the ACM, 28, 1, January 1981.
[6]Digital Equipment Corporation,Decsystem 10 Assembly Language Handbook. Third Edition, 1973, pp. 51–52.
[7]M. Furst, Bounded width computation DAG’s. In preparation, 1982.
[8]M. Furst, J. B. Saxe, M. Sipser, Parity, circuits and the polynomial-time hierarchy. 22NDSymposium on the Foundations of Computer Science, 1981, pp. 260–270.
[9]M. Furst, J. B. Saxe, M. Sipser, Depth 3 circuits require Ω(n clogn ) gates to compute parity: a geometric argument. In preparation.
[10]V. Krapchenko, Complexity of the realization of a linear function in the class of II-circuits. English translation inMath. Notes Acad. Sci., USSR, 1971, pp. 21–23; orig. inMat. Zamet, 9, 1, pp. 35–40.
[11]V. Krapchenko, A method of obtaining lower bounds for the complexity of II-schemes. English translation inMath. Notes Acad. Sci USSR, 1972, pp. 474–479; orig. inMat. Zamet, 10, 1, pp. 83–92.
[12]O. Lupanov, Implementing the algebra of logic functions in terms of constant-depth formulas in the basis +,*, -. English translation inSov. Phys.-Dokl., 6, 2, 1961; orig. inDokla. Akad. Nauk SSSR, 136, 5.
[13]R. Ladner and N. Lynch, Relativization of questions about log space computability.Mathematical Systems Theory, 10, 1, 1976.
[14]C. Mead and L. Conway,Introduction to VLSI Systems. Addison-Wesley, Reading, Mass. 1980.
[15]W. Paul, A 2.5N lower bound for the combinational complexity of boolean functions. 7thAnnual ACM Symposium on Theory of Computing, 1975, pp. 27–36.
[16]J. Savage,The Complexity of Computing. John Wiley and Sons, New York, 1976, Sect. 2.4.
[17]C. P. Schnorr, A 3n lower bound on the network complexity of boolean functions.Theoretical Computer Science, 10, 1, 1980, p. 83. · Zbl 0438.68012 · doi:10.1016/0304-3975(80)90074-2
[18]L. J. Stockmeyer, The polynomial-time hierarchy.Theoretical Computer Science, 3, 1, 1976, pp. 1–22. · Zbl 0353.02024 · doi:10.1016/0304-3975(76)90061-X
[19]S. Skyum and L. G. Valiant, A complexity theory based on boolean algebra. 22ndSymposium on the Foundations of Computer Science, 1981, pp. 244–253.
[20]M. Sipser, On polynomial vs exponential growth. In preparation.
[21]L. Stockmeyer and A. Meyer, Word problems requiring exponential time, preliminary report. 5thAnnual ACM Symposium on Theory of Computing, 1973.