{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:51Z","timestamp":1725663651857},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540522829"},{"type":"electronic","value":"9783540469452"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52282-4_29","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:28:58Z","timestamp":1330187338000},"page":"24-36","source":"Crossref","is-referenced-by-count":2,"title":["Minimal pairs and complete problems"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Ambos-Spies","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steven","family":"Homer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert I.","family":"Soare","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,6]]},"reference":[{"key":"3_CR1","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, Minimal pairs for polynomial time reducibilities, in Computation Theory and Logic, E. B\u00f6rger ed., Lecture Notes in Computer Science, 270, (1987), 1\u201314.","journal-title":"Lecture Notes in Computer Science"},{"key":"3_CR2","unstructured":"K. Ambos-Spies, Polynomial time degrees of NP sets, in Current Trends in Theoretical Computer Science, E. B\u00f6rger ed., Computer Science Press, 1987."},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"958","DOI":"10.1137\/0215067","volume":"15","author":"K. Ambos-Spies","year":"1986","unstructured":"K. Ambos-Spies, An inhomogeneity in the polynomial time degrees, SIAM J. Comput. 15 (1986) 958\u2013963.","journal-title":"SIAM J. Comput."},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill and R. Solovay, Relativizations of the P=?NP questions, SIAM J. Comput. 4 (1975), 431\u2013442.","journal-title":"SIAM J. Comput."},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0022-0000(81)90021-0","volume":"22","author":"P. Chew","year":"1981","unstructured":"P. Chew and M. Machtey, A note on structure and looking back applied to the relative complexity of computable functions, J. Computer System Sci. 22 (1981), 53\u201359.","journal-title":"J. Computer System Sci."},{"key":"3_CR6","unstructured":"R. Downey, Nondiamond theorems for polynomial time reducibility (to appear)."},{"key":"3_CR7","unstructured":"H. Heller, Relativized polynomial hierarchy extending two levels, Thesis, Technische Universit\u00e4t Munich, (1980)."},{"key":"3_CR8","doi-asserted-by":"publisher","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. Comp. Science 24 (1983), 279\u2013289.","journal-title":"Theor. Comp. Science"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner, On the structure of polynomial time reducibility, JACM 22 (1975), 155\u2013171.","journal-title":"JACM"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0304-3975(81)90069-4","volume":"15","author":"L. H. Landweber","year":"1981","unstructured":"L. H. Landweber, R. J. Lipton and E.L. Robertson, On the structure of sets in NP and other complexity classes, Theor. Comp. Sci. 15 (1981), 103\u2013123.","journal-title":"Theor. Comp. Sci."},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0304-3975(76)90007-4","volume":"2","author":"M. Machtey","year":"1976","unstructured":"M. Machtey, Minimal pairs of polynomial degrees with subexponential complexity, Theor. Comp. Sci. 2 (1976), 73\u201376.","journal-title":"Theor. Comp. Sci."},{"key":"3_CR12","doi-asserted-by":"publisher","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 approach to obtain diagonal sets in complexity classes, Theor. Comp. Sci. 18 (1982), 95\u2013103.","journal-title":"Theor. Comp. Sci."},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0304-3975(84)90124-5","volume":"31","author":"U. Sch\u00f6ning","year":"1984","unstructured":"U. Sch\u00f6ning, Minimal pairs for P, Theor. Comp. Sci. 31 (1984), 41\u201348.","journal-title":"Theor. Comp. Sci."}],"container-title":["Lecture Notes in Computer Science","STACS 90"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52282-4_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:07:24Z","timestamp":1619557644000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52282-4_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540522829","9783540469452"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-52282-4_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}