{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:23Z","timestamp":1725558983050},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_43","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"503-514","source":"Crossref","is-referenced-by-count":1,"title":["Weak Completeness Notions for Exponential Time"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Ambos-Spies","sequence":"first","affiliation":[]},{"given":"Timur","family":"Bakibayev","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"43_CR1","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/0022-0000(89)90023-8","volume":"39","author":"K. Ambos-Spies","year":"1989","unstructured":"Ambos-Spies, K.: Honest polynomial time reducibilities and the P\u2009=\u2009 ?NP problem. J. Comput. System Sci. 39, 250\u2013281 (1989)","journal-title":"J. Comput. System Sci."},{"key":"43_CR2","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Computation Theory and Logic","author":"K. Ambos-Spies","year":"1987","unstructured":"Ambos-Spies, K.: Minimal pairs for polynomial time reducibilities. LNCS 270, 1\u201313 (1987)"},{"key":"43_CR3","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1016\/S0049-237X(99)80034-2","volume":"140","author":"K. Ambos-Spies","year":"1999","unstructured":"Ambos-Spies, K.: Polynomial time reducibilities and degrees. Stud. Logic Found. Math. 140, 683\u2013705 (1999)","journal-title":"Stud. Logic Found. Math."},{"key":"43_CR4","first-page":"1","volume":"224","author":"K. Ambos-Spies","year":"1996","unstructured":"Ambos-Spies, K.: Resource-bounded genericity. London Math. Soc. Lecture Note Ser. 224, 1\u201359 (1996)","journal-title":"London Math. Soc. Lecture Note Ser."},{"key":"43_CR5","unstructured":"Ambos-Spies, K., Bakibayev, T.: Comparing nontriviality for E and EXP. Submitted for publication"},{"key":"43_CR6","doi-asserted-by":"crossref","unstructured":"Ambos-Spies, K., Bakibayev, T.: Nontriviality for exponential time w.r.t. weak reducibilities. To appear in the proceedings of TAMC 2010","DOI":"10.1007\/978-3-642-13562-0_9"},{"key":"43_CR7","first-page":"1","volume":"187","author":"K. Ambos-Spies","year":"1997","unstructured":"Ambos-Spies, K., Mayordomo, E.: Resource-bounded measure and randomness. Lecture Notes in Pure and Appl. Math. 187, 1\u201347 (1997)","journal-title":"Lecture Notes in Pure and Appl. Math."},{"key":"43_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(96)89424-2","volume":"168","author":"K. Ambos-Spies","year":"1996","unstructured":"Ambos-Spies, K., Neis, H.-C., Terwijn, S.A.: Genericity and measure for exponential time. Theoret. Comput. Sci. 168, 3\u201319 (1996)","journal-title":"Theoret. Comput. Sci."},{"key":"43_CR9","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0304-3975(95)00260-X","volume":"172","author":"K. Ambos-Spies","year":"1997","unstructured":"Ambos-Spies, K., Terwijn, S.A. and Zheng, X.: Resource bounded randomness and weakly complete problems. Theoret. Comput. Sci. 172, 195\u2013207 (1997)","journal-title":"Theoret. Comput. Sci."},{"key":"43_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-79235-9","volume-title":"Structural complexity","author":"J.L. Balc\u00e1zar","year":"1995","unstructured":"Balc\u00e1zar, J.L., D\u00edaz, J., Gabarr\u00f3, J.: Structural complexity. I, 2nd edn.. Springer, Berlin (1995)","edition":"2"},{"key":"43_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-75357-2","volume-title":"Structural complexity","author":"J.L. Balc\u00e1zar","year":"1990","unstructured":"Balc\u00e1zar, J.L., D\u00edaz, J., Gabarr\u00f3, J.: Structural complexity II. Springer, Berlin (1990)"},{"key":"43_CR12","doi-asserted-by":"crossref","unstructured":"Ambos-Spies K., Mayordomo E., Zheng X.: A Comparison of Weak Completeness Notions. Proceedings of the 11th Annual IEEE Conference on Computational Complexity, 171\u2013178 (1996)","DOI":"10.1109\/CCC.1996.507679"},{"key":"43_CR13","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1006\/jcss.1997.1484","volume":"54","author":"H. Buhrman","year":"1997","unstructured":"Buhrman, H. and Mayordomo, E.: An excursion to the Kolmogorov random strings. J. Comput. System Sci. 54, 393\u2013399 (1997)","journal-title":"J. Comput. System Sci."},{"key":"43_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BFb0039600","volume-title":"STACS 1987","author":"J.G. Geske","year":"1987","unstructured":"Geske, J.G., Hu\u1ef3nh, D.T., Selman, A.L.: A hierarchy theorem for almost everywhere complex sets with application to polynomial complexity degrees. LNCS 247, 125\u2013135 (1987)"},{"key":"43_CR15","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1137\/S0097539792238133","volume":"24","author":"D.W. Juedes","year":"1995","unstructured":"Juedes, D.W., Lutz, J.H.: The complexity and distribution of hard problems. SIAM J. Comput. 24, 279\u2013295 (1995)","journal-title":"SIAM J. Comput."},{"key":"43_CR16","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(95)80016-6","volume":"143","author":"D.W. Juedes","year":"1995","unstructured":"Juedes, D.W., Lutz, J.H. Weak completeness in E and ${\\rm E}\\sb 2$ . Theoret. Comput. Sci. 143, 149\u2013158 (1995)","journal-title":"Theoret. Comput. Sci."},{"key":"43_CR17","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J. Assoc. Comput. Mach. 22, 155\u2013171 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"key":"43_CR18","volume-title":"Graduate Texts in Computer Science","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.: An introduction to Kolmogorov complexity and its applications. Graduate Texts in Computer Science, 2nd edn., xx+637. Springer, New York (1997)","edition":"2"},{"key":"43_CR19","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J.H. Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. J. Comput. System Sci. 44, 220\u2013258 (1992)","journal-title":"J. Comput. System Sci."},{"key":"43_CR20","doi-asserted-by":"publisher","first-page":"1170","DOI":"10.1137\/S0097539793249700","volume":"24","author":"J.H. Lutz","year":"1995","unstructured":"Lutz, J.H.: Weakly hard problems. SIAM J. Comput. 24, 1170\u20131189 (1995)","journal-title":"SIAM J. Comput."},{"key":"43_CR21","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/0304-3975(94)00023-C","volume":"136","author":"E. Mayordomo","year":"1994","unstructured":"Mayordomo, E.: Almost every set in exponential time is P-bi-immune. Theoret. Comput. Sci. 136, 487\u2013506 (1994)","journal-title":"Theoret. Comput. Sci."},{"key":"43_CR22","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0304-3975(87)90132-0","volume":"54","author":"O. Watanabe","year":"1987","unstructured":"Watanabe, O.: A comparison of polynomial time completeness notions. Theoret. Comput. Sci. 54, 249\u2013265 (1987)","journal-title":"Theoret. Comput. Sci."},{"key":"43_CR23","doi-asserted-by":"publisher","first-page":"1100","DOI":"10.1137\/0219076","volume":"19","author":"J.H. Lutz","year":"1990","unstructured":"Lutz, J.H.: Category and measure in complexity classes. SIAM J. Comput. 19, 1100\u20131131 (1990)","journal-title":"SIAM J. Comput."},{"key":"43_CR24","doi-asserted-by":"crossref","unstructured":"Lutz, J.H.: The quantitative structure of exponential time. Complexity theory retrospective II, 225\u2013260 (1997)","DOI":"10.1007\/978-1-4612-1872-2_10"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:48:20Z","timestamp":1606186100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}