{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:06:00Z","timestamp":1787497560958,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540164869","type":"print"},{"value":"9783540398257","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_93","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:47:09Z","timestamp":1330177629000},"page":"105-124","source":"Crossref","is-referenced-by-count":36,"title":["The boolean hierarchy: Hardware over NP"],"prefix":"10.1007","author":[{"given":"Jin-yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lane","family":"Hemachandra","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"issue":"1","key":"9_CR1","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennett","year":"1981","unstructured":"C. Bennett and J. Gill, \u201cRelative to a Random Oracle, P A \u2260 NP A \u2260 coNP A with Probability 1,\u201d SIAM Journal on Computing, Vol. 10, #1, Feb. 1981, pp. 96\u2013113.","journal-title":"SIAM Journal on Computing"},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"55","author":"A. Blass","year":"1982","unstructured":"A. Blass and Y. Gurevich, \u201cOn the Unique Satisfiability Problem\u201d, Information and Control, 55, 1982, pp. 80\u201388.","journal-title":"Information and Control"},{"key":"9_CR3","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, \u201cA Second Step Towards the Polynomial Hierarchy,\u201d Theoretical Computer Science, 8, 1979, pp. 177\u2013187.","journal-title":"Theoretical Computer Science"},{"key":"9_CR4","unstructured":"Jin-yi Cai and Lane Hemachandra, \u201cThe Boolean Hierarchy: Hardware over NP,\u201d Cornell Computer Science Department Technical Report TR85-724, December 1985."},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"S.A. Cook, \u201cThe Complexity of Theorem-Proving Procedures,\u201d Proceedings of the 3 rd Annual Symposium on the Theory of Computation, 1971, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"9_CR6","unstructured":"J. Cai and G.E. Meyer, \u201cGraph Minimal Uncolorability is DP-Complete,\u201d Cornell Computer Science Department Technical Report TR85-688, June 1985."},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"M. Furst, J.B. Saxe and M. Sipser, \u201cParity, Circuits, and the Polynomial-Time Hierarchy,\u201d Proceedings of the 22 rd Annual Symposium on Foundations of Computer Science, 1981, pp. 260\u2013270.","DOI":"10.1109\/SFCS.1981.35"},{"key":"9_CR8","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, Freeman."},{"key":"9_CR9","unstructured":"J. Hartmanis, \u201cOn the Structure of Feasible Computations,\u201d Cornell Department of Computer Science Technical Report TR82-484, March 1982."},{"issue":"2","key":"9_CR10","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF01744434","volume":"17","author":"H. Heller","year":"1984","unstructured":"H. Heller, \u201cRelativized Polynomial Hierarchies Extending Two Levels,\u201d Mathematical Systems Theory, V. 17, #2, May 1984, pp. 71\u201384.","journal-title":"Mathematical Systems Theory"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Juris Hartmanis and Lane Hemachandra, \u201cOn Sparse Oracles Separating Feasible Complexity Classes,\u201d Proceedings of the 3 rd Annual Symposium on Theoretical Aspects of Computer Science (STACS '86), Lecture Notes in Computer Science #210, Springer-Verlag, 1986, pp. 321\u2013333.","DOI":"10.1007\/3-540-16078-7_86"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Juris Hartmanis and Lane Hemachandra, \u201cComplexity Classes Without Machines: On Complete Sets for UP,\u201d to appear in Proceedings of the 13 th Colloquium on Automata, Languages and Programming (ICALP '86), Lecture Notes in Computer Science, Springer-Verlag, 1986.","DOI":"10.1007\/3-540-16761-7_62"},{"key":"9_CR13","unstructured":"J. Hartmanis and N. Immerman, \u201cOn Complete Problems for NP\u2229coNP,\u201d Proceedings of the 12 th Colloquium on Automata, Languages and Programming (ICALP '85), Lecture Notes in Computer Science #194, Springer-Verlag, 1985."},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, V. Sewelson, and N. Immerman, \u201cSparse Sets in NP-P: EXPTIME versus NEXPTIME,\u201d Cornell Computer Science Department Technical Report TR83-544, February 1983.","DOI":"10.1145\/800061.808769"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, V. Sewelson, and N. Immerman, \u201cSparse Sets in NP-P: EXPTIME versus NEXPTIME,\u201d Proceedings of the 15 th Annual Symposium on the Theory of Computation, 1983, pp. 382\u2013391.","DOI":"10.1145\/800061.808769"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0304-3975(84)90111-7","volume":"34","author":"J. Hartmanis","year":"1984","unstructured":"J. Hartmanis and Y. Yesha, \u201cComputation Times of NP Sets of Different Densities,\u201d Theoretical Computer Science, V. 34, 1984, pp. 17\u201332.","journal-title":"Theoretical Computer Science"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"R.M. Karp and R.J. Lipton, \u201cSome Connections Between Nonuniform and Uniform Complexity Classes,\u201d Proceedings of the 12 th Annual Symposium on the Theory of Computation, 1980, pp. 302\u2013309.","DOI":"10.1145\/800141.804678"},{"key":"9_CR18","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S. Mahaney","year":"1982","unstructured":"S. Mahaney, \u201cSparse Complete Sets for NP: Solution to a Conjecture of Berman and Hartmanis,\u201d Journal of Computer and Systems Sci., 25, 1982, pp. 130\u2013143.","journal-title":"Journal of Computer and Systems Sci."},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou and D. Wolfe, \u201cThe Complexity of Facets Resolved,\u201d Proceedings of the 26 th Annual Symposium on Foundations of Computer Science, 1985.","DOI":"10.1109\/SFCS.1985.56"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou and M. Yannakakis, \u201cThe Complexity of Facets (and Some Facets of Complexity),\u201d Proceedings of the 14 th Annual Symposium on the Theory of Computation, 1982, pp. 255\u2013260.","DOI":"10.1145\/800070.802199"},{"key":"9_CR21","unstructured":"C.H. Papadimitriou and S.K. Zachos, \u201cTwo Remarks on the Complexity of Counting,\u201d MIT-LCS Technical Report MIT\/LCS\/TM-228, August 1982."},{"key":"9_CR22","unstructured":"D. A. Russo, \u201cStructural Properties of Complexity Classes,\u201d Thesis: University of California at Santa Barbara Department of Mathematics, March 1985."},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"M. Sipser, \u201cOn Relativization and the Existence of Complete Sets,\u201d Proceedings of the 9 th Colloquium on Automata, Languages and Programming (ICALP '82), Lecture Notes in Computer Science #140, Springer-Verlag, 1982, pp. 523\u2013531.","DOI":"10.1007\/BFb0012797"},{"issue":"2","key":"9_CR24","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0213023","volume":"13","author":"U. Schoning","year":"1984","unstructured":"U. Schoning and R.V. Book, \u201cImmunity, Relativizations, and Nondeterminism,\u201d SIAM Journal on Computing, Vol. 13, #2, May 1984, pp. 329\u2013337.","journal-title":"SIAM Journal on Computing"},{"key":"9_CR25","unstructured":"I. Wegner, \u201cOn the boolean closure of NP,\u201d Proceedings of the 1985 International Conference on Fundamentals of Computation Theory, Lecture Notes in Computer Science, Springer-Verlag, 1985, pp. 485\u2013493."},{"issue":"3","key":"9_CR26","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0212027","volume":"12","author":"Y. Yesha","year":"1983","unstructured":"Y. Yesha, \u201cOn Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets,\u201d SIAM Journal on Computing, Vol. 12, #3, August 1983, pp. 411\u2013425.","journal-title":"SIAM Journal on Computing"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"A. Yao, \u201cSeparating the Polynomial-Time Hierarchy by Oracles,\u201d Proceedings of the 26 th Annual Symposium on Foundations of Computer Science, 1985.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_93.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:10:33Z","timestamp":1605625833000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_93"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_93","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]}}}