{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T21:28:34Z","timestamp":1761946114124,"version":"build-2065373602"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,7,4]],"date-time":"2007-07-04T00:00:00Z","timestamp":1183507200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,2]]},"DOI":"10.1007\/s00224-007-9000-2","type":"journal-article","created":{"date-parts":[[2007,7,3]],"date-time":"2007-07-03T16:29:47Z","timestamp":1183480187000},"page":"131-142","source":"Crossref","is-referenced-by-count":6,"title":["Partial Bi-immunity, Scaled Dimension, and NP-Completeness"],"prefix":"10.1007","volume":"42","author":[{"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,7,4]]},"reference":[{"issue":"3","key":"9000_CR1","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.: Separating NP-completeness under strong hypotheses. J. Comput. Syst. Sci. 61(3), 335\u2013361 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9000_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01699457","volume":"18","author":"J. Balc\u00e1zar","year":"1985","unstructured":"Balc\u00e1zar, J., Sch\u00f6ning, U.: Bi-immune sets for complexity classes. Math. Syst. Theory 18(1), 1\u201318 (1985)","journal-title":"Math. Syst. Theory"},{"key":"9000_CR3","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Torenvliet, L.: On the structure of complete sets. In: 9th IEEE Annual Conference on Structure in Complexity Theory, pp. 118\u2013133 (1994)","DOI":"10.1109\/SCT.1994.315811"},{"key":"9000_CR4","doi-asserted-by":"crossref","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. Math. Syst. Theory 24, 179\u2013200 (1991)","journal-title":"Math. Syst. Theory"},{"key":"9000_CR5","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd ACM Symposium on Theory of Computing, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"issue":"2","key":"9000_CR6","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"Grollmann, J., Selman, A.L.: Complexity measures for public-key cryptosystems. SIAM J. Comput. 17(2), 309\u2013355 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9000_CR7","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1016\/S0304-3975(01)00340-1","volume":"289","author":"J.M. Hitchcock","year":"2002","unstructured":"Hitchcock, J.M.: MAX3SAT is exponentially hard to approximate if NP has positive dimension. Theor. Comput. Sci. 289(1), 861\u2013869 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9000_CR8","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1137\/S0097539703426416","volume":"34","author":"J.M. Hitchcock","year":"2004","unstructured":"Hitchcock, J.M.: Small spans in scaled dimension. SIAM J. Comput. 34(1), 170\u2013194 (2004)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9000_CR9","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.jcss.2003.09.001","volume":"69","author":"J.M. Hitchcock","year":"2004","unstructured":"Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Scaled dimension and nonuniform complexity. J. Comput. Syst. Sci. 69(2), 97\u2013122 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"9000_CR10","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.\u00a0336\u2013347. Springer, New York (2004)"},{"key":"9000_CR11","doi-asserted-by":"crossref","unstructured":"Homer, S.: Structural properties of nondeterministic complete sets. In: Proceedings of the 5th Annual IEEE Annual Conference on Structure in Complexity Theory, pp. 3\u201310 (1990)","DOI":"10.1109\/SCT.1990.113949"},{"key":"9000_CR12","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 problems for exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp.\u00a0135\u2013153. Springer, New York (1997)"},{"issue":"2","key":"9000_CR13","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0304-3975(93)90126-E","volume":"115","author":"S. Homer","year":"1993","unstructured":"Homer, S., Kurtz, S., Royer, J.: On 1-truth-table-hard languages. Theor. Comput. Sci. 115(2), 383\u2013389 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"9000_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":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp.\u00a085\u2013104. Plenum, New York (1972)"},{"issue":"4","key":"9000_CR15","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1137\/0210061","volume":"10","author":"K. Ko","year":"1981","unstructured":"Ko, K., Moore, D.: Completeness, approximation and density. SIAM J. Comput. 10(4), 787\u2013796 (1981)","journal-title":"SIAM J. Comput."},{"key":"9000_CR16","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.: A comparison of polynomial time reducibilities. Theor. Comput. Sci. 1, 103\u2013123 (1975)","journal-title":"Theor. Comput. Sci."},{"key":"9000_CR17","first-page":"265","volume":"9","author":"L.A. Levin","year":"1973","unstructured":"Levin, L.A.: Universal sequential search problems. Probl. Inf. Transm. 9, 265\u2013266 (1973). English translation of original in Problemy Peredaci Informatsii","journal-title":"Probl. Inf. Transm."},{"key":"9000_CR18","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1016\/0022-0000(90)90026-H","volume":"41","author":"L. Longpr\u00e9","year":"1990","unstructured":"Longpr\u00e9, L., Young, P.: Cook reducibility is faster than Karp reducibility. J. Comput. Syst. Sci. 41, 389\u2013401 (1990)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"9000_CR19","doi-asserted-by":"crossref","first-page":"1236","DOI":"10.1137\/S0097539701417723","volume":"32","author":"J.H. Lutz","year":"2003","unstructured":"Lutz, J.H.: Dimension in complexity classes. SIAM J. Comput. 32(5), 1236\u20131259 (2003)","journal-title":"SIAM J. Comput."},{"key":"9000_CR20","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 164, 141\u2013163 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9000_CR21","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M. Ogiwara","year":"1991","unstructured":"Ogiwara, M., Watanabe, O.: On polynomial time bounded truth-table reducibility of NP sets to sparse sets. SIAM J. Comput. 20(3), 471\u2013483 (1991)","journal-title":"SIAM J. Comput."},{"key":"9000_CR22","unstructured":"Pavan, A.: Comparison of reductions and completeness notions. In: L. Hemaspaandra (ed.) SIGACT News. Complexity Theory Column 40. ACM Press (June 2003)"},{"issue":"1","key":"9000_CR23","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.: Bi-immunity separates strong NP-completeness notions. Inf. Comput. 188(1), 116\u2013126 (2004)","journal-title":"Inf. Comput."},{"key":"9000_CR24","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(82)90039-1","volume":"19","author":"A.L. Selman","year":"1982","unstructured":"Selman, A.L.: Reductions on NP and P-selective sets. Theor. Comput. Sci. 19, 287\u2013304 (1982)","journal-title":"Theor. Comput. Sci."},{"key":"9000_CR25","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 54, 249\u2013265 (1987)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9000-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9000-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9000-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T04:06:19Z","timestamp":1737173179000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9000-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,4]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["9000"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9000-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2007,7,4]]}}}