{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:40:12Z","timestamp":1742600412171,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_8","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:05:04Z","timestamp":1330290304000},"page":"87-97","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Observations on measure and lowness for \u0394 2 P"],"prefix":"10.1007","author":[{"given":"Jack H.","family":"Lutz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"E. Allender and M. Strauss. Measure on small complexity classes with applications for BPP. In Proceedings of the 35th Symposium on Foundations of Computer Science, pages 807\u2013818. IEEE Computer Society Press, 1994.","DOI":"10.1109\/SFCS.1994.365713"},{"key":"8_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-79235-9","volume-title":"Structural Complexity I","author":"J. L. Balc\u00e1zar","year":"1995","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I (second edition). Springer-Verlag, Berlin, 1995.","edition":"second edition"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1137\/S0097539792228289","volume":"23","author":"M. Bellare","year":"1994","unstructured":"M. Bellare and S. Goldwasser. The complexity of decision versus search. SIAM Journal on Computing, 23:97\u2013119, 1994.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR4","unstructured":"Daniel Pierre Bovet and Pierluigi Crescenzi. Introduction to the Theory of Complexity. Prentice Hall, 1994."},{"key":"8_CR5","unstructured":"D. W. Juedes. The Complexity and Distribution of Computationally Useful Problems. PhD thesis, Iowa State University, 1994."},{"key":"8_CR6","unstructured":"D. W. Juedes and J. H. Lutz. Completeness and weak completeness under polynomial-size circuits. Information and Computation. To appear."},{"issue":"2","key":"8_CR7","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1137\/S0097539792238133","volume":"24","author":"D. W. Juedes","year":"1995","unstructured":"D. W. Juedes and J. H. Lutz. The complexity and distribution of hard problems. SIAM Journal on Computing, 24(2):279\u2013295, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In Proc. 12th ACM Symp. Theory of Computer Science, pages 302\u2013309, 1980.","DOI":"10.1145\/800141.804678"},{"key":"8_CR9","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/BF02088291","volume":"22","author":"A. Klapper","year":"1989","unstructured":"A. Klapper. Generalized lowness and highness and probabilistic classes. Mathematical Systems Theory, 22:37\u201345, 1989.","journal-title":"Mathematical Systems Theory"},{"key":"8_CR10","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1145\/77600.77623","volume":"37","author":"K. Ko","year":"1990","unstructured":"K. Ko. Separating and collapsing results on the relativized probablistic polynomial-time hierarchy. Journal of the Association for Computing Machinery, 37:415\u2013438, 1990.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"8_CR11","doi-asserted-by":"publisher","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 J. Comput., 14:41\u201351, 1985.","journal-title":"SIAM J. Comput."},{"key":"8_CR12","unstructured":"J. K\u00f6bler. On the structure of low sets. In Proceedings of the Tenth Structure in Complexity Theory Conference, pages 246\u2013261. IEEE Computer Society Press, 1995."},{"key":"8_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The Graph Isomorphism Problem","author":"J. K\u00f6bler","year":"1993","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, and J. Tor\u00e1n. The Graph Isomorphism Problem. Birkh\u00e4user, Berlin, 1993."},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"J. K\u00f6bler and O. Watanabe. New collapse consequences of NP having small circuits. In Proceedings of the 22nd International Colloquium on Automata, Languages, and Programming. Springer-Verlag, 1995. To appear.","DOI":"10.1007\/3-540-60084-1_74"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"14","author":"C. Lautemann","year":"1983","unstructured":"C. Lautemann. BPP and the polynomial hierarchy. Information Processing Letters, 14:215\u2013217, 1983.","journal-title":"Information Processing Letters"},{"key":"8_CR16","unstructured":"J. H. Lutz. Resource-bounded measure. In preparation."},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. Weakly hard problems. SIAM Journal on Computing, 24. To appear, 1995. See also Proceedings of the Ninth Structure in Complexity Theory Conference, 1994, pp. 146\u2013161. IEEE Computer Society Press.","DOI":"10.1109\/SCT.1994.315808"},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90320-2","volume":"81","author":"J. H. Lutz","year":"1991","unstructured":"J. H. Lutz. An upward measure separation theorem. Theoretical Computer Science, 81:127\u2013135, 1991.","journal-title":"Theoretical Computer Science"},{"key":"8_CR19","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J. H. Lutz","year":"1992","unstructured":"J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44:220\u2013258, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1137\/0222065","volume":"22","author":"J. H. Lutz","year":"1993","unstructured":"J. H. Lutz. A pseudorandom oracle characterization of BPP. SIAM Journal on Computing, 22:1075\u20131086, 1993.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. The quantitative structure of exponential time. In Proceedings of the Eighth Structure in Complexity Theory Conference, pages 158\u2013175. IEEE Computer Society Press, 1993.","DOI":"10.1109\/SCT.1993.336530"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"J. H. Lutz and E. Mayordomo. Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theoretical Computer Science. To appear. See also Proceedings of the Eleventh Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, 1994, pp. 415\u2013426.","DOI":"10.1007\/3-540-57785-8_159"},{"key":"8_CR23","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539792237498","volume":"23","author":"J. H. Lutz","year":"1994","unstructured":"J. H. Lutz and E. Mayordomo. Measure, stochasticity, and the density of hard languages. SIAM Journal on Computing, 23:762\u2013779, 1994.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR24","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(93)90256-S","volume":"107","author":"J. H. Lutz","year":"1993","unstructured":"J. H. Lutz and W. J. Schmidt. Circuit size relative to pseudorandom oracles. Theoretical Computer Science, 107:95\u2013120, March 1993.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"8_CR25","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/0304-3975(94)00023-C","volume":"136","author":"E. Mayordomo","year":"1994","unstructured":"E. Mayordomo. Almost every set in exponential time is P-bi-immune. Theoretical Computer Science, 136(2):487\u2013506, 1994.","journal-title":"Theoretical Computer Science"},{"key":"8_CR26","volume-title":"PhD thesis","author":"E. Mayordomo","year":"1994","unstructured":"E. Mayordomo. Contributions to the Study of Resource-Bounded Measure. PhD thesis, Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain, 1994."},{"key":"8_CR27","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"N. Nisan and A. Wigderson. Hardness vs randomness. Journal of Computer and System Sciences, 49:149\u2013167, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR28","unstructured":"Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"8_CR29","doi-asserted-by":"publisher","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 and high hierarchy within NP. Journal of Computer and System Sciences, 27:14\u201328, 1983.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR30","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":"8_CR31","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/0022-0000(89)90020-2","volume":"39","author":"U. Sch\u00f6ning","year":"1989","unstructured":"U. Sch\u00f6ning. Probabilistic complexity classes and lowness. Journal of Computer and System Sciences, 39:84\u2013100, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR32","doi-asserted-by":"crossref","unstructured":"M. Sipser. A complexity-theoretic approach to randomness. In Proceedings of the 15th ACM Symposium on Theory of Computing, pages 330\u2013335, 1983.","DOI":"10.1145\/800061.808762"},{"key":"8_CR33","doi-asserted-by":"publisher","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. Theoretical Computer Science, 3:1\u201322, 1977.","journal-title":"Theoretical Computer Science"},{"key":"8_CR34","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C. B. Wilson","year":"1985","unstructured":"C. B. Wilson. Relativized circuit complexity. Journal of Computer and System Sciences, 31:169\u2013181, 1985.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR35","doi-asserted-by":"publisher","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. Theoretical Computer Science, 3:23\u201333, 1977.","journal-title":"Theoretical Computer Science"},{"key":"8_CR36","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0019-9958(86)80044-4","volume":"69","author":"S. Zachos","year":"1986","unstructured":"S. Zachos and H. Heller. A decisive characterization of BPP. Information and Control, 69:125\u2013135, 1986.","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:50Z","timestamp":1742598650000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_8"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"7 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}