{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:44:44Z","timestamp":1740109484009,"version":"3.37.3"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,7,18]],"date-time":"2017-07-18T00:00:00Z","timestamp":1500336000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2018,3]]},"DOI":"10.1007\/s00037-017-0157-z","type":"journal-article","created":{"date-parts":[[2017,7,18]],"date-time":"2017-07-18T05:45:37Z","timestamp":1500356737000},"page":"63-97","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Autoreducibility of NP-Complete Sets under Strong Hypotheses"],"prefix":"10.1007","volume":"27","author":[{"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadi","family":"Shafei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,18]]},"reference":[{"key":"157_CR1","unstructured":"K. Ambos-Spies (1983). P-mitotic sets. In Logic and Machines: Decision Problems and Complexity, Proceedings of the Symposium \u201dRekursive Kombinatorik\u201d held from May 23-28, 1983\u00a0at the Institut f\u00fcr Mathematische Logik und Grundlagenforschung der Universit\u00e4t M\u00fcnster\/Westfalen, 1\u201323."},{"issue":"3","key":"157_CR2","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jcss.1999.1674","volume":"61","author":"K. Ambos-Spies","year":"2000","unstructured":"Ambos-Spies K., Bentzien L. (2000) Separating NP-Completeness Notions Under Strong Hypotheses. Journal of Computer and System Sciences 61(3): 335\u2013361","journal-title":"Journal of Computer and System Sciences"},{"key":"157_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":"Ambos-Spies K., Fleischhack H., Huwig H. (1987) Diagonalizations over polynomial time computable sets. Theoretical Computer Science 51: 177\u2013204","journal-title":"Theoretical Computer Science"},{"key":"157_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01276436","volume":"2","author":"R. Beigel","year":"1992","unstructured":"Beigel R., Feigenbaum J. (1992) On being incoherent without being very hard. Computational Complexity 2: 1\u201317","journal-title":"Computational Complexity"},{"issue":"5","key":"157_CR5","doi-asserted-by":"crossref","first-page":"1497","DOI":"10.1137\/S0097539798334736","volume":"29","author":"H. Buhrman","year":"2000","unstructured":"Buhrman H., Fortnow L., van Melkebeek D., Torenvliet L. (2000) Separating complexity classes using autoreducibility. SIAM Journal on Computing 29(5): 1497\u20131520","journal-title":"SIAM Journal on Computing"},{"key":"157_CR6","doi-asserted-by":"crossref","unstructured":"H. Buhrman, B. Hescott, S. Homer & L. Torenvliet (2010). Non-Uniform Reductions. Theory of Computing Systems 47(2), 317\u2013341. URL \n                        http:\/\/www.cs.bu.edu\/techreports\/abstracts\/2008-007\n                        \n                    .","DOI":"10.1007\/s00224-008-9163-5"},{"key":"157_CR7","first-page":"41","volume":"85","author":"H. Buhrman","year":"2005","unstructured":"Buhrman H., Torenvliet L. (2005) A Post\u2019s Program for Complexity Theory. Bulletin of the EATCS 85: 41\u201351","journal-title":"Bulletin of the EATCS"},{"key":"157_CR8","doi-asserted-by":"crossref","unstructured":"C. Glasser, M. Ogihara, A. Pavan, A. L. Selman & L. Zhang (2007). Autoreducibility, mitoticity, and immunity. J. Comput. Syst. Sci. 73(5), 735\u2013754. URL \n                        http:\/\/dx.doi.org\/10.1016\/j.jcss.2006.10.020\n                        \n                    .","DOI":"10.1016\/j.jcss.2006.10.020"},{"key":"157_CR9","doi-asserted-by":"crossref","unstructured":"J. M. Hitchcock & A. Pavan (2007). Comparing Reductions to NP-Complete Sets. Information and Computation 205(5), 694\u2013706. URL \n                        http:\/\/www.cs.uwyo.edu\/~jhitchco\/papers\/crnpcs.shtml\n                        \n                    .","DOI":"10.1016\/j.ic.2006.10.005"},{"key":"157_CR10","doi-asserted-by":"crossref","unstructured":"J. M. Hitchcock & A. Pavan (2008). Hardness Hypotheses, Derandomization, and Circuit Complexity. Computational Complexity 17(1), 119\u2013146. URL \n                        http:\/\/www.cs.uwyo.edu\/~jhitchco\/papers\/hhdcc.shtml\n                        \n                    .","DOI":"10.1007\/s00037-008-0241-5"},{"issue":"2","key":"157_CR11","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. E. Ladner","year":"1975","unstructured":"Ladner R. E., Lynch N. A., Selman A. L. (1975) A comparison of polynomial-time reducibilities. Theoretical Computer Science 1(2): 103\u2013123","journal-title":"Theoretical Computer Science"},{"key":"157_CR12","doi-asserted-by":"crossref","unstructured":"J. H. Lutz & E. Mayordomo (1996). Cook versus Karp-Levin: Separating Completeness Notions If NP Is Not Small. Theoretical Computer Science 164(1\u20132), 141\u2013163.","DOI":"10.1016\/0304-3975(95)00189-1"},{"key":"157_CR13","unstructured":"D. T. Nguyen & A. L. Selman (2014). Non-autoreducible Sets for NEXP. In 31st International Symposium on Theoretical Aspects of Computer Science, 590\u2013601. URL \n                        http:\/\/dx.doi.org\/10.4230\/LIPIcs.STACS.2014.590\n                        \n                    ."},{"issue":"1","key":"157_CR14","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1016\/j.ic.2003.05.001","volume":"188","author":"A. Pavan","year":"2004","unstructured":"Pavan A., Selman A. L. (2004) Bi-immunity separates strong NP-completeness notions. Information and Computation 188(1): 116\u2013126","journal-title":"Information and Computation"},{"key":"157_CR15","unstructured":"B. Trakhtenbrot (1970). On autoreducibility. Dokl. Akad. Nauk SSSR 192(6), 1224\u20131227. Translation in Soviet Math. Dokl. 11(3): 814\u2013817, 1970."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-017-0157-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0157-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0157-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T06:29:15Z","timestamp":1519626555000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-017-0157-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,18]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["157"],"URL":"https:\/\/doi.org\/10.1007\/s00037-017-0157-z","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2017,7,18]]}}}