{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:03Z","timestamp":1725488523497},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_35","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T12:03:24Z","timestamp":1186056204000},"page":"419-430","source":"Crossref","is-referenced-by-count":2,"title":["Almost Complete Sets"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Ambos-Spies","sequence":"first","affiliation":[]},{"given":"Wolfgang","family":"Merkle","sequence":"additional","affiliation":[]},{"given":"Jan","family":"Reimann","sequence":"additional","affiliation":[]},{"given":"Sebastiaan A.","family":"Terwijn","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"35_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 Annual IEEE Symposium an Foundations of Computer Science, p.867\u2013818, IEEE Computer Society Press, 1994.","DOI":"10.1109\/SFCS.1994.365713"},{"key":"35_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/BFb0055796","volume-title":"Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science","author":"K. Ambos-Spies","year":"1998","unstructured":"K. Ambos-Spies, S. Lempp, and G. Mainhardt. Randomness vs. completeness: on the diagonalization strength of resource bounded random sets. In: Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, p. 465\u2013473, Lecture Notes in Computer Science, Vol. 1450, Springer, 1998."},{"key":"35_CR3","first-page":"1","volume-title":"Complexity, logic, and recursion theory","author":"K. Ambos-Spies","year":"1997","unstructured":"K. Ambos-Spies and E. Mayordomo. Resource-bounded measure and randomness. In: A. Sorbi (ed.), Complexity, logic, and recursion theory, p.1\u201347. Dekker, New York, 1997."},{"key":"35_CR4","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies, E. Mayordomo and X. Zheng. A comparison of weak completeness notions. In: Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.171\u2013178, IEEE Computer Society Press, 1996.","DOI":"10.1109\/CCC.1996.507679"},{"key":"35_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(96)89424-2","volume":"168","author":"K. Ambos-Spies","year":"1996","unstructured":"K. Ambos-Spies, H.-C. Neis and S. A. Terwijn. Genericity and measure for exponential time. Theoretical Computer Science, 168:3\u201319, 1996.","journal-title":"Theoretical Computer Science"},{"key":"35_CR6","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0304-3975(95)00260-X","volume":"172","author":"K. Ambos-Spies","year":"1997","unstructured":"K. Ambos-Spies, S. A. Terwijn and X. Zheng. Resource bounded randomness and weakly complete problems. Theoretical Computer Science, 172:195\u2013207, 1997.","journal-title":"Theoretical Computer Science"},{"key":"35_CR7","doi-asserted-by":"crossref","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity, volume I. Springer-Verlag, 1995.","DOI":"10.1007\/978-3-642-79235-9"},{"key":"35_CR8","unstructured":"L. Berman. Polynomial reducibilities and complete sets. Ph.D. thesis, Cornell University, 1977."},{"key":"35_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BFb0028558","volume-title":"Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science","author":"H. Buhrman","year":"1998","unstructured":"H. Buhrman, D. van Melkebeek, K. Regan, D. Sivakumar, M. Strauss. A generalization of resource bounded measure, with application to the BPP vs. EXP problem. In: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, p.161\u2013171, Lecture Notes in Computer Science, Vol. 1373, Springer, 1998."},{"key":"35_CR10","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0304-3975(93)90126-E","volume":"115","author":"S. Homer","year":"1993","unstructured":"S. Homer, S. Kurtz and J. Royer. On 1-truth-table-hard languages. Theoretical Computer Science, 115:383\u2013389, 1993.","journal-title":"Theoretical Computer Science"},{"key":"35_CR11","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BF01206322","volume":"5","author":"D. W. Juedes","year":"1995","unstructured":"D. W. Juedes. Weakly complete problems are not rare. Computational Complexity, 5:267\u2013283, 1995.","journal-title":"Computational Complexity"},{"key":"35_CR12","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:279\u2013295, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"35_CR13","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(95)80016-6","volume":"143","author":"D. W. Juedes","year":"1995","unstructured":"D. W. Juedes and J. H. Lutz. Weak completeness in E and E 2. Theoretical Computer Science, 143:149\u2013158, 1995.","journal-title":"Theoretical Computer Science"},{"key":"35_CR14","doi-asserted-by":"publisher","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":"35_CR15","doi-asserted-by":"publisher","first-page":"1170","DOI":"10.1137\/S0097539793249700","volume":"24","author":"J. H. Lutz","year":"1995","unstructured":"J. H. Lutz. Weakly hard problems. SIAM Journal on Computing 24:1170\u20131189, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"35_CR16","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/978-1-4612-1872-2_10","volume-title":"Complexity theory retrospective","author":"J. H. Lutz","year":"1997","unstructured":"J. H. Lutz. The quantitative structure of exponential time. In: Hemaspaandra, Lane A. (ed.) et al., Complexity theory retrospective II, p.225\u2013260. Springer, New York, 1997."},{"key":"35_CR17","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:487\u2013506, 1994.","journal-title":"Theoretical Computer Science"},{"key":"35_CR18","doi-asserted-by":"crossref","unstructured":"K. Regan, D. Sivakumar and J.-Y. Cai. Pseudorandom generators, measure theory and natural proofs. In: Proceedings of the 36th Annual IEEE Symposium an Foundations of Computer Science, p.171\u2013178, IEEE Computer Society Press, 1995.","DOI":"10.1109\/SFCS.1995.492459"},{"key":"35_CR19","unstructured":"K. Regan, D. Sivakumar. Improved Resource-Bounded Borel-Cantelli and Stochasticity Theorems. Technical Report UBCS-TR 95-08, Department of Computer Science, State University of New York at Buffalo, 1995."},{"key":"35_CR20","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0304-3975(87)90132-0","volume":"54","author":"O. Watanabe","year":"1987","unstructured":"O. Watanabe. A comparison of polynomial time completeness notions. Theoretical Computer Science, 54:249\u2013265, 1987.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T14:10:08Z","timestamp":1556719808000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_35","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}