{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T10:04:30Z","timestamp":1648980270145},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,4,22]],"date-time":"2010-04-22T00:00:00Z","timestamp":1271894400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2011,10]]},"DOI":"10.1007\/s10878-010-9327-5","type":"journal-article","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T11:46:29Z","timestamp":1271850389000},"page":"482-493","source":"Crossref","is-referenced-by-count":0,"title":["Separating NE from some nonuniform nondeterministic complexity classes"],"prefix":"10.1007","volume":"22","author":[{"given":"Bin","family":"Fu","sequence":"first","affiliation":[]},{"given":"Angsheng","family":"Li","sequence":"additional","affiliation":[]},{"given":"Liyu","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,4,22]]},"reference":[{"issue":"2","key":"9327_CR1","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L Berman","year":"1977","unstructured":"Berman L, Hartmanis J (1977) On isomorphisms and density of NP and other complete sets. SIAM J Comput 6(2):305\u2013322","journal-title":"SIAM J Comput"},{"key":"9327_CR2","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/3-540-58201-0_74","volume-title":"ICALP 1994","author":"H Buhrman","year":"1994","unstructured":"Buhrman H, Torenvliet L (1994) On the cutting edge of relativization: the resource bounded injury method. In: ICALP 1994. Lecture notes in computer science, vol\u00a0820. Springer, Berlin, pp 263\u2013273"},{"key":"9327_CR3","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BF02679445","volume":"30","author":"H-J Burtschick","year":"1997","unstructured":"Burtschick H-J, Lindner W (1997) On sets Turing reducible to p-selective sets. Theory Comput Syst 30:135\u2013143","journal-title":"Theory Comput Syst"},{"issue":"2","key":"9327_CR4","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jcss.1998.1615","volume":"58","author":"J Cai","year":"1999","unstructured":"Cai J, Sivakumar D (1999) Sparse hard sets for P: resolution of a conjecture of Hartmanis. J\u00a0Comput Syst Sci 58(2):280\u2013296","journal-title":"J\u00a0Comput Syst Sci"},{"issue":"4","key":"9327_CR5","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0022-0000(73)80028-5","volume":"7","author":"S Cook","year":"1973","unstructured":"Cook S (1973) A hierarchy for nondeterministic time complexity. J Comput Syst Sci 7(4):343\u2013353","journal-title":"J Comput Syst Sci"},{"issue":"2","key":"9327_CR6","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF01202282","volume":"26","author":"B Fu","year":"1993","unstructured":"Fu B (1993) On lower bounds of the closeness between complexity classes. Math Syst Theory 26(2):187\u2013202","journal-title":"Math Syst Theory"},{"issue":"5","key":"9327_CR7","doi-asserted-by":"crossref","first-page":"1082","DOI":"10.1137\/S0097539792237188","volume":"24","author":"B Fu","year":"1995","unstructured":"Fu B (1995) With quasilinear queries EXP is not polynomial time Turing reducible to sparse sets. SIAM J Comput 24(5):1082\u20131090","journal-title":"SIAM J Comput"},{"key":"9327_CR8","unstructured":"Fu B, Li H, Zhong Y (1992) Some properties of exponential time complexity classes. In: Proceedings 7th IEEE annual conference on structure in complexity theory, pp\u00a050\u201357"},{"issue":"4","key":"9327_CR9","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0221044","volume":"21","author":"K Ganesan","year":"1992","unstructured":"Ganesan K, Homer S (1992) Complete problems and strong polynomial reducibilities. SIAM J Comput 21(4):733\u2013742","journal-title":"SIAM J Comput"},{"key":"9327_CR10","volume-title":"The complexity theory companion. Texts in theoretical computer science\u2014an EATCS series","author":"L Hemaspaandra","year":"2002","unstructured":"Hemaspaandra L, Ogihara M (2002) The complexity theory companion. Texts in theoretical computer science\u2014an EATCS series. Springer, Berlin"},{"key":"9327_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-05080-4","volume-title":"Theory of semi-feasible algorithms","author":"L Hemaspaandra","year":"2003","unstructured":"Hemaspaandra L, Torenvliet L (2003) Theory of semi-feasible algorithms. Springer, Berlin"},{"key":"9327_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3544-4","volume-title":"Computability and complexity theory. Texts in computer science","author":"S Homer","year":"2001","unstructured":"Homer S, Selman A (2001) Computability and complexity theory. Texts in computer science. Springer, New York"},{"key":"9327_CR13","doi-asserted-by":"crossref","unstructured":"Karp R, Lipton R (1980) Some connections between nonuniform and uniform complexity classes. In: Proceedings of the twelfth annual ACM symposium on theory of computing, pp\u00a0302\u2013309","DOI":"10.1145\/800141.804678"},{"issue":"2","key":"9327_CR14","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S Mahaney","year":"1982","unstructured":"Mahaney S (1982) Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis. J\u00a0Comput Syst Sci 25(2):130\u2013143","journal-title":"J\u00a0Comput Syst Sci"},{"key":"9327_CR15","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0304-3975(95)00078-X","volume":"158","author":"S Mocas","year":"1996","unstructured":"Mocas S (1996) Separating classes in the exponential-time hierarchy from classes in PH. Theor Comput Sci 158:221\u2013231","journal-title":"Theor Comput Sci"},{"key":"9327_CR16","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1016\/j.jcss.2004.03.003","volume":"69","author":"M Ogihara","year":"2004","unstructured":"Ogihara M, Tantau T (2004) On the reducibility of sets inside NP to sets with low information content. J\u00a0Comput Syst Sci 69:499\u2013524","journal-title":"J\u00a0Comput Syst Sci"},{"key":"9327_CR17","unstructured":"Ogiwara M (1991) On P-closeness of polynomial-time hard sets. Unpublished manuscript"},{"issue":"3","key":"9327_CR18","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M Ogiwara","year":"1991","unstructured":"Ogiwara M, Watanabe O (1991) On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM J Comput 20(3):471\u2013483","journal-title":"SIAM J Comput"},{"key":"9327_CR19","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A Selman","year":"1979","unstructured":"Selman A (1979) P-selective sets, tally languages and the behavior of polynomial time reducibilities on NP. Math Syst Theory 13:55\u201365","journal-title":"Math Syst Theory"},{"issue":"3","key":"9327_CR20","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0212027","volume":"12","author":"Y Yesha","year":"1983","unstructured":"Yesha Y (1983) On certain polynomial-time truth-table reducibilities of complete sets to sparse sets. SIAM J Comput 12(3):411\u2013425","journal-title":"SIAM J Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-010-9327-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-010-9327-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-010-9327-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:23:14Z","timestamp":1559262194000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-010-9327-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,22]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["9327"],"URL":"https:\/\/doi.org\/10.1007\/s10878-010-9327-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,22]]}}}