{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:40Z","timestamp":1781078200242,"version":"3.54.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1984,12,1]],"date-time":"1984-12-01T00:00:00Z","timestamp":470707200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1984,12]]},"DOI":"10.1007\/bf01744431","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T01:31:02Z","timestamp":1118885462000},"page":"13-27","source":"Crossref","is-referenced-by-count":603,"title":["Parity, circuits, and the polynomial-time hierarchy"],"prefix":"10.1007","volume":"17","author":[{"given":"Merrick","family":"Furst","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James B.","family":"Saxe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Sipser","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01744431_CR1","doi-asserted-by":"crossref","unstructured":"D. Angluin, Counting problems and the polynomial-time hierarchy.Theoretical Computer Science, to appear.","DOI":"10.1016\/0304-3975(80)90027-4"},{"key":"BF01744431_CR2","unstructured":"N. Blum, A 2.75n lower bound for the combinational complexity of boolean functions. University of Saarbrucken, Technical Report."},{"key":"BF01744431_CR3","doi-asserted-by":"crossref","unstructured":"T. Baker, J. Gill, and R. Solovay, Relativizations of theP =? NP question.SIAM Journal of Computing, 4, 4, 1975.","DOI":"10.1137\/0204037"},{"issue":"2","key":"BF01744431_CR4","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(79)90043-4","volume":"8","author":"T. Baker","year":"1979","unstructured":"T. Baker and A. Selman, A second step toward the polynomial hierarchy.Theoretical Computer Science, 8, 2, 1979, pp. 177\u2013187.","journal-title":"Theoretical Computer Science"},{"key":"BF01744431_CR5","doi-asserted-by":"crossref","unstructured":"A. Chandra, D. Kozen, and L. Stockmeyer, Alternation.Journal of the ACM, 28, 1, January 1981.","DOI":"10.1145\/322234.322243"},{"key":"BF01744431_CR6","unstructured":"Digital Equipment Corporation,Decsystem 10 Assembly Language Handbook. Third Edition, 1973, pp. 51\u201352."},{"key":"BF01744431_CR7","unstructured":"M. Furst, Bounded width computation DAG's. In preparation, 1982."},{"key":"BF01744431_CR8","doi-asserted-by":"crossref","unstructured":"M. Furst, J. B. Saxe, M. Sipser, Parity, circuits and the polynomial-time hierarchy. 22NDSymposium on the Foundations of Computer Science, 1981, pp. 260\u2013270.","DOI":"10.1109\/SFCS.1981.35"},{"key":"BF01744431_CR9","unstructured":"M. Furst, J. B. Saxe, M. Sipser, Depth 3 circuits require \u03a9(n clogn ) gates to compute parity: a geometric argument. In preparation."},{"key":"BF01744431_CR10","doi-asserted-by":"crossref","unstructured":"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\u201323; orig. inMat. Zamet, 9, 1, pp. 35\u201340.","DOI":"10.1007\/BF01405045"},{"key":"BF01744431_CR11","doi-asserted-by":"crossref","unstructured":"V. Krapchenko, A method of obtaining lower bounds for the complexity of II-schemes. English translation inMath. Notes Acad. Sci USSR, 1972, pp. 474\u2013479; orig. inMat. Zamet, 10, 1, pp. 83\u201392.","DOI":"10.1007\/BF01747074"},{"key":"BF01744431_CR12","unstructured":"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."},{"key":"BF01744431_CR13","doi-asserted-by":"crossref","unstructured":"R. Ladner and N. Lynch, Relativization of questions about log space computability.Mathematical Systems Theory, 10, 1, 1976.","DOI":"10.1007\/BF01683260"},{"key":"BF01744431_CR14","volume-title":"Introduction to VLSI Systems","author":"C. Mead","year":"1980","unstructured":"C. Mead and L. Conway,Introduction to VLSI Systems. Addison-Wesley, Reading, Mass. 1980."},{"key":"BF01744431_CR15","doi-asserted-by":"crossref","unstructured":"W. Paul, A 2.5N lower bound for the combinational complexity of boolean functions. 7thAnnual ACM Symposium on Theory of Computing, 1975, pp. 27\u201336.","DOI":"10.1145\/800116.803750"},{"key":"BF01744431_CR16","volume-title":"The Complexity of Computing","author":"J. Savage","year":"1976","unstructured":"J. Savage,The Complexity of Computing. John Wiley and Sons, New York, 1976, Sect. 2.4."},{"issue":"1","key":"BF01744431_CR17","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0304-3975(80)90074-2","volume":"10","author":"C. P. Schnorr","year":"1980","unstructured":"C. P. Schnorr, A 3n lower bound on the network complexity of boolean functions.Theoretical Computer Science, 10, 1, 1980, p. 83.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"BF01744431_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1976","unstructured":"L. J. Stockmeyer, The polynomial-time hierarchy.Theoretical Computer Science, 3, 1, 1976, pp. 1\u201322.","journal-title":"Theoretical Computer Science"},{"key":"BF01744431_CR19","doi-asserted-by":"crossref","unstructured":"S. Skyum and L. G. Valiant, A complexity theory based on boolean algebra. 22ndSymposium on the Foundations of Computer Science, 1981, pp. 244\u2013253.","DOI":"10.1109\/SFCS.1981.3"},{"key":"BF01744431_CR20","unstructured":"M. Sipser, On polynomial vs exponential growth. In preparation."},{"key":"BF01744431_CR21","doi-asserted-by":"crossref","unstructured":"L. Stockmeyer and A. Meyer, Word problems requiring exponential time, preliminary report. 5thAnnual ACM Symposium on Theory of Computing, 1973.","DOI":"10.1145\/800125.804029"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01744431.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01744431\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01744431","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T19:20:16Z","timestamp":1586287216000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01744431"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,12]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1984,12]]}},"alternative-id":["BF01744431"],"URL":"https:\/\/doi.org\/10.1007\/bf01744431","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1984,12]]}}}