{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:46:57Z","timestamp":1725472017459},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540359043"},{"type":"electronic","value":"9783540359050"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_41","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T06:46:45Z","timestamp":1151477205000},"page":"465-476","source":"Crossref","is-referenced-by-count":6,"title":["Comparing Reductions to NP-Complete Sets"],"prefix":"10.1007","author":[{"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"41_CR1","doi-asserted-by":"crossref","unstructured":"Adleman, L., Manders, K.: Reducibility, randomness, and intractability. In: Proceedings of the 9th ACM Symposium on Theory of Computing, pp. 151\u2013163 (1977)","DOI":"10.1145\/800105.803405"},{"key":"41_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s00037-001-8191-1","volume":"10","author":"A. Agrawal","year":"2001","unstructured":"Agrawal, A., Allender, E., Impagliazzo, R., Pitassi, T., Rudich, S.: Reducing the complexity of reductions. Computational Complexity\u00a010, 117\u2013138 (2001)","journal-title":"Computational Complexity"},{"key":"41_CR3","doi-asserted-by":"crossref","unstructured":"Agrawal, M.: Pseudo-random generators and structure of complete degrees. In: 17th Annual IEEE Conference on Computational Complexity, pp. 139\u2013145 (2002)","DOI":"10.1109\/CCC.2002.1004349"},{"issue":"2","key":"41_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1006\/jcss.1998.1583","volume":"57","author":"M. Agrawal","year":"1998","unstructured":"Agrawal, M., Allender, E., Rudich, S.: Reductions in circuit complexity: An isomorphism theorem and a gap theorem. Journal of Computer and System Sciences\u00a057(2), 127\u2013143 (1998)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"41_CR5","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jcss.1999.1674","volume":"61","author":"K. Ambos-Spies","year":"2000","unstructured":"Ambos-Spies, K., Bentzien, L.: Separating NP-completeness notions under strong hypotheses. Journal of Computer and System Sciences\u00a061(3), 335\u2013361 (2000)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1\u20132","key":"41_CR6","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. Theoretical Computer Science\u00a0172(1\u20132), 195\u2013207 (1997)","journal-title":"Theoretical Computer Science"},{"key":"41_CR7","unstructured":"Berman, L.: Polynomial Reducibilities and Complete Sets. PhD thesis, Cornell University (1977)"},{"issue":"2","key":"41_CR8","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L., Hartmanis, J.: On isomorphism and density of NP and other complete sets. SIAM Journal on Computing\u00a06(2), 305\u2013322 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"41_CR9","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/BF02090397","volume":"24","author":"H. Buhrman","year":"1991","unstructured":"Buhrman, H., Homer, S., Torenvliet, L.: Completeness notions for nondeterministic complexity classes. Mathematical Systems Theory\u00a024, 179\u2013200 (1991)","journal-title":"Mathematical Systems Theory"},{"issue":"3","key":"41_CR10","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1137\/S0097539797317123","volume":"31","author":"H. Buhrman","year":"2002","unstructured":"Buhrman, H., Longpr\u00e9, L.: Compressibility and resource bounded measure. SIAM Journal on Computing\u00a031(3), 876\u2013886 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"41_CR11","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1109\/SCT.1994.315811","volume-title":"Proceedings of the Ninth Annual Structure in Complexity Theory Conference","author":"H. Buhrman","year":"1994","unstructured":"Buhrman, H., Torenvliet, L.: On the structure of complete sets. In: Proceedings of the Ninth Annual Structure in Complexity Theory Conference, pp. 118\u2013133. IEEE Computer Society Press, Los Alamitos (1994)"},{"key":"41_CR12","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Torenvliet, L.: Complete sets and structure in subrecursive classes. In: Logic Colloquium 1996. Lecture Notes in Logic, vol.\u00a012, pp. 45\u201378. Association for Symbolic Logic (1998)","DOI":"10.1007\/978-3-662-22110-5_2"},{"key":"41_CR13","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/0022-0000(89)90017-2","volume":"39","author":"M.J. Chung","year":"1989","unstructured":"Chung, M.J., Ravikumar, B.: Strong nondeterministic Turing reduction\u2014a technique for proving intractability. Journal of Computer and System Sciences\u00a039, 2\u201320 (1989)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"41_CR14","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/S0890-5401(03)00119-6","volume":"186","author":"S. Fenner","year":"2003","unstructured":"Fenner, S., Fortnow, L., Naik, A., Rogers, J.: Inverting onto functions. Information and Computation\u00a0186(1), 90\u2013103 (2003)","journal-title":"Information and Computation"},{"key":"41_CR15","doi-asserted-by":"crossref","unstructured":"Ganesan, K., Homer, S.: Complete problems and srong polynomial reducibilities. SIAM Journal on Computing\u00a021(4) (1991)","DOI":"10.1137\/0221044"},{"issue":"11","key":"41_CR16","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/s002360050109","volume":"34","author":"L. Hemaspaandra","year":"1997","unstructured":"Hemaspaandra, L., Rothe, J., Wechsung, G.: Easy sets and hard certificate schemes. Acta Informatica\u00a034(11), 859\u2013879 (1997)","journal-title":"Acta Informatica"},{"key":"41_CR17","first-page":"336","volume-title":"Proceedings of the 24th Conference on Foundations of Software Technology and Theoretical Computer Science","author":"J.M. Hitchcock","year":"2004","unstructured":"Hitchcock, J.M., Pavan, A.: Hardness hypotheses, derandomization, and circuit complexity. In: Proceedings of the 24th Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 336\u2013347. Springer, Heidelberg (2004)"},{"key":"41_CR18","doi-asserted-by":"crossref","unstructured":"Hitchcock, J.M., Pavan, A., Vinodchandran, N.V.: Partial bi-immunity, scaled dimension, and NP-completeness. In: Theory of Computing Systems (to appear)","DOI":"10.1007\/s00224-007-9000-2"},{"key":"41_CR19","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/978-1-4612-1872-2_6","volume-title":"Complexity Theory Retrospective II","author":"S. Homer","year":"1997","unstructured":"Homer, S.: Structural properties of complete sets for exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp. 135\u2013153. Springer, Heidelberg (1997)"},{"key":"41_CR20","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0304-3975(81)90007-4","volume":"14","author":"T.J. Long","year":"1981","unstructured":"Long, T.J.: On \u03b3-reducibility versus polynomial time many-one reducibility. Theoretical Computer Science\u00a014, 91\u2013101 (1981)","journal-title":"Theoretical Computer Science"},{"key":"41_CR21","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J.H. Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences\u00a044, 220\u2013258 (1992)","journal-title":"Journal of Computer and System Sciences"},{"key":"41_CR22","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/978-1-4612-1872-2_10","volume-title":"Complexity Theory Retrospective II","author":"J.H. Lutz","year":"1997","unstructured":"Lutz, J.H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp. 225\u2013254. Springer, Heidelberg (1997)"},{"key":"41_CR23","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(95)00189-1","volume":"164","author":"J.H. Lutz","year":"1996","unstructured":"Lutz, J.H., Mayordomo, E.: Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theoretical Computer Science\u00a0164, 141\u2013163 (1996)","journal-title":"Theoretical Computer Science"},{"key":"41_CR24","unstructured":"Lutz, J.H., Mayordomo, E.: Twelve problems in resource-bounded measure. Bulletin of the European Association for Theoretical Computer Science\u00a068, 64\u201380 (1999): Also in Current Trends in Theoretical Computer Science: Entering the 21st Century, pp. 83\u2013101, World Scientific Publishing (2001)"},{"issue":"2","key":"41_CR25","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/882116.882125","volume":"34","author":"A. Pavan","year":"2003","unstructured":"Pavan, A.: Comparison of reductions and completeness notions. SIGACT News\u00a034(2), 27\u201341 (2003)","journal-title":"SIGACT News"},{"issue":"3","key":"41_CR26","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1137\/S0097539701387039","volume":"31","author":"A. Pavan","year":"2002","unstructured":"Pavan, A., Selman, A.: Separation of NP-completeness notions. SIAM Journal on Computing\u00a031(3), 906\u2013918 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"41_CR27","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.ic.2003.05.001","volume":"188","author":"A. Pavan","year":"2004","unstructured":"Pavan, A., Selman, A.: Bi-immunity separates strong NP-completeness notions. Information and Computation\u00a0188, 116\u2013126 (2004)","journal-title":"Information and Computation"},{"issue":"1","key":"41_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(96)00189-5","volume":"61","author":"Y. Wang","year":"1997","unstructured":"Wang, Y.: NP-hard sets are superterse unless NP is small. Information Processing Letters\u00a061(1), 1\u20136 (1997)","journal-title":"Information Processing Letters"},{"key":"41_CR29","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. Theoretical Computer Science\u00a054, 249\u2013265 (1987)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:19:50Z","timestamp":1619493590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/11786986_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}