{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:41Z","timestamp":1740109421779,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,4,4]],"date-time":"2019-04-04T00:00:00Z","timestamp":1554336000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004561","name":"Ministry of Education and Science of the Republic of Kazakhstan","doi-asserted-by":"publisher","award":["AP05131579"],"award-info":[{"award-number":["AP05131579"]}],"id":[{"id":"10.13039\/501100004561","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s00224-019-09920-4","type":"journal-article","created":{"date-parts":[[2019,4,4]],"date-time":"2019-04-04T07:29:55Z","timestamp":1554362995000},"page":"1388-1412","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Weak Completeness Notions for Exponential Time"],"prefix":"10.1007","volume":"63","author":[{"given":"Klaus","family":"Ambos-Spies","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5357-1099","authenticated-orcid":false,"given":"Timur","family":"Bakibayev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,4]]},"reference":[{"key":"9920_CR1","volume-title":"Randomness relativizations, and polynomial reducibilities. Structure in complexity theory (Berkeley, Calif., 1986), 23\u201334, Lecture Notes in Comput Sci., vol. 223","author":"K Ambos-Spies","year":"1986","unstructured":"Ambos-Spies, K.: Randomness relativizations, and polynomial reducibilities. Structure in complexity theory (Berkeley, Calif., 1986), 23\u201334, Lecture Notes in Comput Sci., vol. 223. Springer, Berlin (1986)"},{"key":"9920_CR2","volume-title":"Minimal pairs for polynomial time reducibilities. Computation theory and logic, 1\u201313, Lecture Notes in Comput Sci., vol. 270","author":"K Ambos-Spies","year":"1987","unstructured":"Ambos-Spies, K.: Minimal pairs for polynomial time reducibilities. Computation theory and logic, 1\u201313, Lecture Notes in Comput Sci., vol. 270. Springer, Berlin (1987)"},{"issue":"3","key":"9920_CR3","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 =? NP problem. J. Comput. Syst. Sci. 39(3), 250\u2013281 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"9920_CR4","volume-title":"Resource-bounded genericity. Computability, enumerability, unsolvability, 1\u201359, London Math. Soc. Lecture Note Ser., vol. 224","author":"K Ambos-Spies","year":"1996","unstructured":"Ambos-Spies, K.: Resource-bounded genericity. Computability, enumerability, unsolvability, 1\u201359, London Math. Soc. Lecture Note Ser., vol. 224. Cambridge Univ. Press, Cambridge (1996)"},{"key":"9920_CR5","doi-asserted-by":"crossref","unstructured":"Ambos-Spies, K.: Polynomial time reducibilities and degrees. Handbook of computability theory, 683\u2013705, Stud. Logic Found. Math., 140, North-Holland, Amsterdam (1999)","DOI":"10.1016\/S0049-237X(99)80034-2"},{"key":"9920_CR6","volume-title":"Weak completeness notions for exponential time. Automata, languages and programming. Part I, 503\u2013514, Lecture Notes in Comput Sci., vol. 6198","author":"K Ambos-Spies","year":"2010","unstructured":"Ambos-Spies, K, Bakibayev, T.: Weak completeness notions for exponential time. Automata, languages and programming. Part I, 503\u2013514, Lecture Notes in Comput Sci., vol. 6198. Springer, Berlin (2010)"},{"key":"9920_CR7","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2012.05.022","volume":"494","author":"K Ambos-Spies","year":"2013","unstructured":"Ambos-Spies, K., Bakibayev, T.: Nontriviality for exponential time w.r.t. weak reducibilities. Theoret. Comput. Sci. 494, 2\u201312 (2013)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"9920_CR8","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/s00224-011-9370-3","volume":"51","author":"K Ambos-Spies","year":"2012","unstructured":"Ambos-Spies, K., Bakibayev, T.: Comparing nontriviality for. E and EXP. Theory Comput. Syst. 51(1), 106\u2013122 (2012)","journal-title":"E and EXP. Theory Comput. Syst."},{"key":"9920_CR9","unstructured":"Ambos-Spies, K., Mayordomo, E., Zheng, X.: A comparison of weak completeness notions. In: Proceedings of the 11th annual IEEE conference on computational complexity, 171\u2013178 (1996)"},{"issue":"1-2","key":"9920_CR10","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., Zheng, X.: Resource bounded randomness and weakly complete problems. Theoret. Comput. Sci. 172(1-2), 195\u2013207 (1997)","journal-title":"Theoret. Comput. Sci."},{"key":"9920_CR11","volume-title":"Structural complexity. I. Second edition. Texts in Theoretical Computer Science. An EATCS Series","author":"J Balc\u00e1zar","year":"1995","unstructured":"Balc\u00e1zar, J., D\u00edaz, J., Gabarr\u00f3 J.: Structural complexity. I. Second edition. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (1995)"},{"key":"9920_CR12","volume-title":"Structural complexity. II. EATCS monographs on theoretical computer science, vol. 22","author":"JL Balc\u00e1zar","year":"1990","unstructured":"Balc\u00e1zar, J.L., D\u00edaz, J., Gabarr\u00f3, J.: Structural complexity. II. EATCS monographs on theoretical computer science, vol. 22. Springer, Berlin (1990)"},{"issue":"3","key":"9920_CR13","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1006\/jcss.1997.1484","volume":"54","author":"H Buhrman","year":"1997","unstructured":"Buhrman, H., Mayordomo, E.: An excursion to the Kolmogorov random strings. Tenth Annual Conference on Structure in Complexity Theory (Minneapolis, MN. J. Comput. Syst. Sci. 54(3), 393\u2013399 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9920_CR14","volume-title":"A hierarchy theorem for almost everywhere complex sets with application to polynomial complexity degrees. STACS 87 (Passau, 1987), 125\u2013135, Lecture Notes in Comput Sci., 247","author":"JG Geske","year":"1987","unstructured":"Geske, J.G., Huy\u0300nh, D.T., Selman, A.L.: A hierarchy theorem for almost everywhere complex sets with application to polynomial complexity degrees. STACS 87 (Passau, 1987), 125\u2013135, Lecture Notes in Comput Sci., 247. Springer, Berlin (1987)"},{"issue":"1","key":"9920_CR15","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(95)80030-D","volume":"143","author":"DW Juedes","year":"1995","unstructured":"Juedes, D.W., Lutz, J.H.: Weak completeness in E and E2. Theoret. Comput. Sci. 143(1), 149\u2013158 (1995)","journal-title":"Theoret. Comput. Sci."},{"key":"9920_CR16","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"RE 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":"9920_CR17","doi-asserted-by":"crossref","unstructured":"Li, M., Vit\u00e1nyi, P.: An introduction to Kolmogorov complexity and its applications Graduate texts in computer science. 2nd edn. Springer-Verlag, New York (1997)","DOI":"10.1007\/978-1-4757-2606-0"},{"issue":"6","key":"9920_CR18","doi-asserted-by":"publisher","first-page":"1170","DOI":"10.1137\/S0097539793249700","volume":"24","author":"JH Lutz","year":"1995","unstructured":"Lutz, J.H.: Weakly hard problems. SIAM J. Comput. 24(6), 1170\u20131189 (1995)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9920_CR19","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539792237498","volume":"23","author":"JH Lutz","year":"1994","unstructured":"Lutz, J.H., Mayordomo, E.: Measure stochasticity, and the density of hard languages. SIAM J. Comput. 23(4), 762\u2013779 (1994)","journal-title":"SIAM J. Comput."},{"issue":"2-3","key":"9920_CR20","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(2-3), 249\u2013265 (1987)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09920-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09920-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09920-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,2]],"date-time":"2020-04-02T23:13:35Z","timestamp":1585869215000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09920-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,4]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["9920"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09920-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2019,4,4]]},"assertion":[{"value":"4 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}