Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Parity, circuits, and the polynomial-time hierarchy

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

A super-polynomial lower bound is given for the size of circuits of fixed depth computing the parity function. Introducing the notion of polynomial-size, constant-depth reduction, similar results are shown for the majority, multiplication, and transitive closure functions. Connections are given to the theory of programmable logic arrays and to the relativization of the polynomial-time hierarchy.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

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.

    Google Scholar 

  4. T. Baker and A. Selman, A second step toward the polynomial hierarchy.Theoretical Computer Science, 8, 2, 1979, pp. 177–187.

    Google Scholar 

  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.

    Google Scholar 

  14. C. Mead and L. Conway,Introduction to VLSI Systems. Addison-Wesley, Reading, Mass. 1980.

    Google Scholar 

  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.

    Google Scholar 

  17. C. P. Schnorr, A 3n lower bound on the network complexity of boolean functions.Theoretical Computer Science, 10, 1, 1980, p. 83.

    Google Scholar 

  18. L. J. Stockmeyer, The polynomial-time hierarchy.Theoretical Computer Science, 3, 1, 1976, pp. 1–22.

    Google Scholar 

  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.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Carnegie-Mellon University, 15213, Pittsburgh, Pa., USA

    Merrick Furst & James B. Saxe

  2. Department of Mathematics, Massachusetts Institute of Technology, 02139, Boston, Mass., USA

    Michael Sipser

Authors
  1. Merrick Furst
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. James B. Saxe
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michael Sipser
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research partially funded by NSF Grant MCS-81-05555 and ONR Grant N00014-76-C-0370.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Furst, M., Saxe, J.B. & Sipser, M. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory 17, 13–27 (1984). https://doi.org/10.1007/BF01744431

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01744431

Keywords

Search

Navigation