{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:04:15Z","timestamp":1725663855823},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540527534"},{"type":"electronic","value":"9783540471370"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52753-2_29","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:41:59Z","timestamp":1330206119000},"page":"1-15","source":"Crossref","is-referenced-by-count":0,"title":["Honest polynomial-time degrees of elementary recursive sets"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Ambos-Spies","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dongping","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"unstructured":"K.Ambos-Spies, On the structure of the polynomial time degrees of recursive sets (Habilitationsschrift), Tech. Rep. Nr. 206, Abteilung Informatik, Universit\u00e4t Dortmund.","key":"1_CR1"},{"key":"1_CR2","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0020-0190(86)90054-2","volume":"22","author":"K. Ambos-Spies","year":"1986","unstructured":"K. Ambos-Spies, 1986 Inhomogeneities in the polynomial time degrees: the degrees of super sparse sets, Information Processing Letters 22,113\u2013117.","journal-title":"Information Processing Letters"},{"key":"1_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-18170-9_149","volume":"270","author":"K. Ambos-Spies","year":"1987","unstructured":"K. Ambos-Spies, 1987 Minimal pairs for polynomial time reducibilities, in \"Computation Theory and Logic\" (E.B\u00f6rger, ed.) Lecture Notes in Computer Science, vol. 270,1\u201313, Springer Verlag.","journal-title":"Lecture Notes in Computer Science"},{"key":"1_CR4","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1016\/0022-0000(89)90023-8","volume":"39","author":"K. Ambos-Spies","year":"1989","unstructured":"K. Ambos-Spies, 1989 Honest polynomial time reducibilities and the P=?NP problem, Journal of Computer and System Sciences 39, 250\u2013281. [Extended Abstract: Honest polynomial reducibilities, recursively enumerable sets, and the P=?NP problem, in \"Structure in Complexity Theory Second Annual Conference\", IEEE Comput. Soc. Press, 1987, 60\u201368.]","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR5","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/3-540-52282-4_29","volume":"415","author":"K. Ambos-Spies","year":"1990","unstructured":"K. Ambos-Spies,S. Homer and R.I. Soare, 1990 Minimal pairs and complete problems, in \"STACS 90, Proceedings\", Lecture Notes in Comput. Sci. 415, 24\u201336, Springer Verlag.","journal-title":"Lecture Notes in Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"K.Ambos-Spies, S.Homer and D.Yang, Honest polynomial reductions and exptally sets, to appear in \"Recursion Theory Week, Oberwolfach 1989, Proceedings\", Lecture Notes in Math., Springer Verlag.","key":"1_CR6","DOI":"10.1007\/BFb0086110"},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"1","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis, 1977 On isomorphism and density of NP and other complete sets, SIAM J. Comput. 1, 305\u2013322.","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"P. Chew and M. Machtey, A note on structure and looking back applied to the relative complexity of computable functions, J. Comput. System Sci. 22, 53\u201359.","key":"1_CR8","DOI":"10.1016\/0022-0000(81)90021-0"},{"doi-asserted-by":"crossref","unstructured":"S.A.Cook, The complexity of theorem proving procedures, Proc. Third Annual ACM Symp. on Theory of Comput., 151\u2013158.","key":"1_CR9","DOI":"10.1145\/800157.805047"},{"unstructured":"K.Ganesan and S.Homer, Complete problems and strong polynomial reducibilities, Boston University Tech Report #88-001.","key":"1_CR10"},{"key":"1_CR11","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1145\/23005.23009","volume":"34","author":"S. Homer","year":"1987","unstructured":"S. Homer, 1987 Minimal degrees for polynomial reducibilities, J. Assoc. Comput. Mach. 34, 480\u2013491.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR12","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0304-3975(87)90036-3","volume":"51","author":"S. Homer","year":"1987","unstructured":"S. Homer and T.J. Long, 1987 Honest polynomial degrees and P=?NP, Theor. Comput. Sci. 51, 265\u2013280.","journal-title":"Theor. Comput. Sci."},{"key":"1_CR13","volume-title":"Introduction to Automata Theory","author":"J.E. Hopcroft","year":"1979","unstructured":"J.E. Hopcroft and J.D. Ullman, 1979 Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA."},{"key":"1_CR14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, 1972 Reducibility among combinatorial problems, in \"Complexity of Computer Computations\", Plenum, New York, 85\u2013103."},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"R.E. Ladner, 1975 On the structure of polynomial time reducibility, J.ACM 22, 155\u2013171.","journal-title":"J.ACM"},{"key":"1_CR16","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0304-3975(84)90124-5","volume":"31","author":"U. Sch\u00f6ning","year":"1984","unstructured":"U. Sch\u00f6ning, 1984 Minimal pairs for P, Theor. Comput. Sci. 31, 41\u201348.","journal-title":"Theor. Comput. Sci."},{"unstructured":"J.Shinoda and T.A.Slaman, On the theory of the polynomial degrees of the recursive sets, to appear. [Abstract in: \"Structure in Complexity Theory Third Annual Conference\", IEEE Comput. Soc. Press, 1988].","key":"1_CR17"},{"unstructured":"R.A.Shore and T.A.Slaman, The p-T-degrees of the recursive sets: lattice embeddings, extensions of embeddings and the two quantifier theory, to appear [Abstract in: \"Structure in Complexity Theory Fourth Annual Conference\", IEEE Comput. Soc. Press, 1989].","key":"1_CR18"},{"doi-asserted-by":"crossref","unstructured":"P.Young, Some structural properties of polynomial reducibilities and sets in NP, Proc. 15th Annu. ACM Symp. on Theory of Comput., 392\u2013401.","key":"1_CR19","DOI":"10.1145\/800061.808770"}],"container-title":["Lecture Notes in Computer Science","CSL '89"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52753-2_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:25:06Z","timestamp":1605648306000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52753-2_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540527534","9783540471370"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-52753-2_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}