×

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.33104)] 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\leq_{cp}g)\) if f can be realized with constant-depth polynomial-size circuits on literals, made up of \(\wedge\), \(\vee\), - gates and gates computing g. It is shown, that parity can be \(\leq_{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\neq \emptyset\).
Reviewer: A.Leitsch

MSC:

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)

Citations:

Zbl 0178.33104

Software:

PAL-11A
Full Text: DOI

References:

[1] D. Angluin, Counting problems and the polynomial-time hierarchy.Theoretical Computer Science, to appear. · Zbl 0499.68020
[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. · Zbl 0323.68033
[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 {\(\Omega\)}(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. · Zbl 0104.24102
[13] R. Ladner and N. Lynch, Relativization of questions about log space computability.Mathematical Systems Theory, 10, 1, 1976. · Zbl 0341.68036
[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. · Zbl 0391.68025
[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. · Zbl 0515.68040
[21] L. Stockmeyer and A. Meyer, Word problems requiring exponential time, preliminary report. 5thAnnual ACM Symposium on Theory of Computing, 1973. · Zbl 0359.68050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.