{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:43Z","timestamp":1725663643137},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56503-5_5","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:16:39Z","timestamp":1330254999000},"page":"28-37","source":"Crossref","is-referenced-by-count":4,"title":["Locating P\/poly optimally in the extended low hierarchy"],"prefix":"10.1007","author":[{"given":"Johannes","family":"K\u00f6bler","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"5_CR1","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"D. Angluin. Queries and concept learning. Machine Learning, 2:319\u2013342, 1988.","journal-title":"Machine Learning"},{"issue":"1","key":"5_CR2","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1145\/147508.147546","volume":"39","author":"E. Allender","year":"1992","unstructured":"E. Allender and L. Hemachandra. Lower bounds for the low hierarchy. Journal of the ACM, 39(1):234\u2013250, 1992.","journal-title":"Journal of the ACM"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"V. Arvind, J. K\u00f6bler, M. Mundhenk. Lowness and the complexity of sparse and tally descriptions. To appear in Proceedings 3rd Symposium on Algorithms and Computation, Springer-Verlag, 1992.","DOI":"10.1007\/3-540-56279-6_78"},{"key":"5_CR4","first-page":"679","volume":"23","author":"J. L. Balc\u00e1zar","year":"1986","unstructured":"J.L. Balc\u00e1zar, R. Book, and U. Sch\u00f6ning. Sparse sets, lowness and highness. SIAM J. Comput., 23:679\u2013688, 1986.","journal-title":"SIAM J. Comput."},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"J.L. Balc\u00e1zar, J. D\u00edaz, J. Gabarr\u00f3. Structural Complexity Theory I + II. Springer-Verlag, 1988 and 1990.","DOI":"10.1007\/978-3-642-75357-2"},{"key":"5_CR6","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman, J. Hartmanis. On isomorphism and density of NP and other complexity classes. SIAM J. Comput., 6:305\u2013327, 1977.","journal-title":"SIAM J. Comput."},{"key":"5_CR7","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J. L. Carter","year":"1979","unstructured":"J.L. Carter and M.N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences 18:143\u2013154, 1979.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"R. Gavalda. Bounding the complexity of advice functions. In Proceedings of the 7th Structure in Complexity Theory Conference, 249\u2013254. IEEE Computer Society Press, June 1992.","DOI":"10.1109\/SCT.1992.215399"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"L. Hemachandra, M. Ogiwara, and O. Watanabe. How hard are sparse sets. In Proceedings of the 7th Structure in Complexity Theory Conference, 222\u2013238. IEEE Computer Society Press, June 1992.","DOI":"10.1109\/SCT.1992.215396"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"R.M. Karp and R.J. Lipton. Some connections between nonuniform and uniform complexity classes. Proc. 12th ACM Symp. Theory of Comput. Science, 302\u2013309, 1980.","DOI":"10.1145\/800141.804678"},{"key":"5_CR11","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1137\/0214003","volume":"14","author":"K. Ko","year":"1985","unstructured":"K. Ko and U. Sch\u00f6ning. On circuit-size complexity and the low hierarchy in NP. SIAM Journ. Comput. 14:41\u201351, 1985.","journal-title":"SIAM Journ. Comput."},{"key":"5_CR12","unstructured":"J. K\u00f6bler. Strukturelle Komplexit\u00e4t von Anzahlproblemen. Doctoral Dissertation. University of Stuttgart, 1989."},{"key":"5_CR13","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/BF00276023","volume":"26","author":"J. K\u00f6bler","year":"1989","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, J. Tor\u00e1n. On counting and approximation. Acta Informatica, 26:363\u2013379, 1989.","journal-title":"Acta Informatica"},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"J. K\u00f6bler and T. Thierauf. Complexity classes with advice. Proceedings 5th Structure in Complexity Theory Conference, 305\u2013315, IEEE Computer Society, 1990.","DOI":"10.1109\/SCT.1990.113979"},{"key":"5_CR15","unstructured":"T.J. Long and M.-J. Sheu. A refinement of the low and high hierarchies. Technical Report OSU-CISRC-2\/91-TR6, The Ohio State University, 1991."},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"M.-J. Sheu and T.J. Long. The extended low hierarchy is an infinite hierarchy. Proceedings of 9th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, #577:187\u2013189, Springer-Verlag 1992.","DOI":"10.1007\/3-540-55210-3_183"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"N. Pippenger. On simultaneous resource bounds. In Proceedings 20th Symposium on Foundations of Computer Science, 307\u2013311, IEEE Computer Society, 1979.","DOI":"10.1109\/SFCS.1979.29"},{"key":"5_CR18","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1137\/0204018","volume":"4","author":"V. Pratt","year":"1975","unstructured":"V. Pratt. Every prime has a succinct certificate. SIAM Journal on Computing 4 (1975), 214\u2013220.","journal-title":"SIAM Journal on Computing"},{"key":"5_CR19","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0022-0000(83)90027-2","volume":"27","author":"U. Sch\u00f6ning","year":"1983","unstructured":"U. Sch\u00f6ning. A low hierarchy within NP. Journal of Computer and System Sciences, 27:14\u201328, 1983.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning. Complexity and Structure. Springer-Verlag Lecture Notes in Computer Science 211, 1986.","DOI":"10.1007\/3-540-16079-5"},{"key":"5_CR21","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U. Sch\u00f6ning","year":"1988","unstructured":"U. Sch\u00f6ning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37:312\u2013323, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"M. Sipser. A complexity theoretic approach to randomness. Proc. 15th ACM Symp. Theory of Comput. Science, 330\u2013335, 1983.","DOI":"10.1145\/800061.808762"},{"key":"5_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"L.J. Stockmeyer. The polynomial-time hierarchy. Theor. Comput. Science, 3:1\u201322, 1977.","journal-title":"Theor. Comput. Science"},{"key":"5_CR24","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1137\/0214060","volume":"14","author":"L. J. Stockmeyer","year":"1985","unstructured":"L.J. Stockmeyer. On approximation algorithms for #P. SIAM Journ. Comput. 14:849\u2013861, 1985.","journal-title":"SIAM Journ. Comput."},{"issue":"5","key":"5_CR25","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. W. Wagner","year":"1990","unstructured":"K.W. Wagner. Bounded query classes. SIAM Journ. Comput. 19(5):833\u2013846, 1990.","journal-title":"SIAM Journ. Comput."},{"key":"5_CR26","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1977","unstructured":"C. Wrathall. Complete sets and the polynomial-time hierarchy. Theor. Comput. Science 3:23\u201333, 1977.","journal-title":"Theor. Comput. Science"}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T14:50:50Z","timestamp":1713624650000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}