{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:52:27Z","timestamp":1725663147719},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540502418"},{"type":"electronic","value":"9783540459606"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-50241-6_25","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:18:20Z","timestamp":1330201100000},"page":"1-16","source":"Crossref","is-referenced-by-count":9,"title":["Diagonalizing over deterministic polynomial time"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Ambos-Spies","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans","family":"Fleischhack","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hagen","family":"Huwig","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-13331-3_30","volume":"171","author":"K. Ambos-Spies","year":"1984","unstructured":"K. Ambos-Spies, P-mitotic sets, in \"Logic and Machines: Decision Problems and Complexity\", Lecture Notes Comput. Sci. 171 (1984) 1\u201323, Springer-Verlag.","journal-title":"Lecture Notes Comput. Sci."},{"key":"1_CR2","unstructured":"K.Ambos-Spies, Polynomial time degrees of NP-sets, in \"Trends in Theoretical Computer Science\", E.B\u00f6rger, Ed., Computer Science Press, 1987, 95\u2013142."},{"key":"1_CR3","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(87)90053-3","volume":"51","author":"K. Ambos-Spies","year":"1987","unstructured":"K. Ambos-Spies, H. Fleischhack and H. Huwig, Diagonalizations over polynomial time computable sets, Theor. Comput. Sci. 51 (1987) 177\u2013204.","journal-title":"Theor. Comput. Sci."},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"K.Ambos-Spies, H.Fleischhack and H.Huwig, Diagonalizations over polynomial time computable sets, Tech. Rep. 177 (1984), Dept. Comput. Sci., Universit\u00e4t Dortmund.","DOI":"10.1016\/0304-3975(87)90053-3"},{"key":"1_CR5","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/BFb0039601","volume":"247","author":"J. Balcazar","year":"1987","unstructured":"J. Balcazar, Self-reducibility, Proc. STACS 87, Lecture Notes Comput. Sci. 247 (1987) 136\u2013147, Springer-Verlag.","journal-title":"Proc. STACS 87, Lecture Notes Comput. Sci."},{"key":"1_CR6","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C.H. Bennett","year":"1981","unstructured":"C.H. Bennett and J. Gill, Relative to a random oracle A, PA\u2260NPA\u2260co-NPA with probability 1, SIAM J. Comput. 10 (1981) 96\u2013113.","journal-title":"SIAM J. Comput."},{"key":"1_CR7","unstructured":"H.Fleischhack, On diagonalizations over complexity classes, Tech. Rep. 210 (1985), Dept. Comput. Sci., Universit\u00e4t Dortmund."},{"key":"1_CR8","first-page":"341","volume":"233","author":"H. Fleischhack","year":"1986","unstructured":"H. Fleischhack, P-genericity and strong P-genericity, Proc. MFCS 1986, Lecture Notes Comput. Sci. 233 (1986) 341\u2013349, Springer-Verlag.","journal-title":"Proc. MFCS 1986, Lecture Notes Comput. Sci."},{"key":"1_CR9","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0019-9958(83)80058-8","volume":"58","author":"W. Gasarch","year":"1983","unstructured":"W. Gasarch and S. Homer, Relativizations comparing NP and exponential time, Inform. Control 58 (1983) 88\u2013100.","journal-title":"Inform. Control"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"S.Homer and T.J.Long, Honest polynomial degrees and P=?NP, Theor. Comput. Sci. (to appear).","DOI":"10.1016\/0304-3975(87)90036-3"},{"key":"1_CR11","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0304-3975(83)90003-8","volume":"24","author":"S. Homer","year":"1983","unstructured":"S. Homer and W. Maass, Oracle dependent properties of the lattice of NP-sets, Theor. Comput. Sci. 24 (1983) 279\u2013289.","journal-title":"Theor. Comput. Sci."},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"M.Lerman, Degrees of Unsolvability, Springer-Verlag, 1983.","DOI":"10.1007\/978-3-662-21755-9"},{"key":"1_CR13","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(82)90114-1","volume":"18","author":"U. Sch\u00f6ning","year":"1982","unstructured":"U. Sch\u00f6ning, A uniform aproach to obtain diagonal sets in complexity classes, Theor. Comput. Sci 18 (1982) 95\u2013103.","journal-title":"Theor. Comput. Sci"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"R.I.Soare, Recursively enumerable sets and degrees, Springer-Verlag, 1987.","DOI":"10.1007\/978-3-662-02460-7"}],"container-title":["Lecture Notes in Computer Science","CSL '87"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50241-6_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:17:40Z","timestamp":1605647860000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50241-6_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540502418","9783540459606"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-50241-6_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}