{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,7]],"date-time":"2024-12-07T05:15:19Z","timestamp":1733548519400,"version":"3.30.1"},"reference-count":23,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2000,6,1]],"date-time":"2000-06-01T00:00:00Z","timestamp":959817600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4794,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2000,6]]},"DOI":"10.1016\/s0304-3975(99)00234-0","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T02:46:25Z","timestamp":1027651585000},"page":"257-269","source":"Crossref","is-referenced-by-count":5,"title":["Resolution of Hartmanis\u2019 conjecture for NL-hard sparse sets"],"prefix":"10.1016","volume":"240","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[]},{"given":"D.","family":"Sivakumar","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(99)00234-0_BIB1","doi-asserted-by":"crossref","unstructured":"L. Berman, J. Hartmanis, On isomorphisms and density of NP and other complete sets, SIAM J. Comput. 6 (1977) 305\u2013321. A preliminary version appeared in STOC 1976.","DOI":"10.1137\/0206023"},{"key":"10.1016\/S0304-3975(99)00234-0_BIB2","doi-asserted-by":"crossref","unstructured":"J. Cai, A. Naik, D. Sivakumar, On the existence of hard sparse sets under weak reductions, Proc. 13th Annual Symp. on Theoretical Aspects of Computer Science (STACS), 1996, pp. 307\u2013318.","DOI":"10.1007\/3-540-60922-9_26"},{"key":"10.1016\/S0304-3975(99)00234-0_BIB3","series-title":"Complexity Theory Retrospective II","article-title":"Sparse sets versus complexity classes","author":"Cai","year":"1997"},{"key":"10.1016\/S0304-3975(99)00234-0_BIB4","doi-asserted-by":"crossref","unstructured":"J. Cai, D. Sivakumar, The resolution of a Hartmanis conjecture, Proc. 36th Annual IEEE Symp. on Foundations of Computer Science, 1995, pp. 362\u2013373. To appear in the FOCS\u201995 special issue of the Journal of Computer and System Sciences.","DOI":"10.1109\/SFCS.1995.492492"},{"key":"10.1016\/S0304-3975(99)00234-0_BIB5","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0213028","article-title":"Constant-depth reducibility","volume":"13","author":"Chandra","year":"1984","journal-title":"SIAM J. Comput."},{"issue":"5","key":"10.1016\/S0304-3975(99)00234-0_BIB6","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1137\/0218066","article-title":"Very fast parallel polynomial arithmetic","volume":"18","author":"Eberly","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(99)00234-0_BIB7","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","article-title":"Parity, circuits, and the polynomial-time hierarchy","volume":"17","author":"Furst","year":"1984","journal-title":"Math. Systems Theory"},{"issue":"3","key":"10.1016\/S0304-3975(99)00234-0_BIB8","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0304-3975(78)90018-X","article-title":"On log-tape isomorphisms of complete sets","volume":"7","author":"Hartmanis","year":"1978","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(99)00234-0_BIB9","doi-asserted-by":"crossref","unstructured":"L. Hemachandra, M. Ogiwara, O. Watanabe, How hard are sparse sets?, Proc. 7th Annual IEEE Conf. on Structure in Complexity Theory, 1992, pp. 222\u2013238.","DOI":"10.1109\/SCT.1992.215396"},{"issue":"4","key":"10.1016\/S0304-3975(99)00234-0_BIB10","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","article-title":"Languages that capture complexity classes","volume":"16","author":"Immerman","year":"1987","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(99)00234-0_BIB11","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","article-title":"Nondeterministic space is closed under complementation","volume":"17","author":"Immerman","year":"1988","journal-title":"SIAM J. Comput."},{"issue":"3\/4","key":"10.1016\/S0304-3975(99)00234-0_BIB12","first-page":"191","article-title":"Turing machines that take advice","volume":"28","author":"Karp","year":"1982","journal-title":"L'enseignement Math."},{"issue":"2","key":"10.1016\/S0304-3975(99)00234-0_BIB13","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","article-title":"Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis","volume":"25","author":"Mahaney","year":"1982","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(99)00234-0_BIB14","doi-asserted-by":"crossref","unstructured":"D. Van Melkebeek, Reducing P to a sparse set using a constant number of queries collapses P to L Proc. 11th IEEE Conf. on Computational Complexity, 1996, pp. 88\u201396.","DOI":"10.1109\/CCC.1996.507672"},{"key":"10.1016\/S0304-3975(99)00234-0_BIB15","doi-asserted-by":"crossref","unstructured":"M. Ogihara, Sparse hard sets for P yield space-efficient algorithms, Proc. 36th Annual IEEE Sympo. on Foundations of Computer Science, 1995, pp. 354\u2013361.","DOI":"10.1109\/SFCS.1995.492491"},{"key":"10.1016\/S0304-3975(99)00234-0_BIB16","unstructured":"M. Ogiwara, O. Watanabe, On polynomial-time bounded truth-table reducibility of NP sets to sparse sets, SIAM J. Comput. 20(3) (1991) 471\u2013483. A preliminary version appeared in STOC 1990."},{"key":"10.1016\/S0304-3975(99)00234-0_BIB17","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0020-0190(91)90084-U","article-title":"Inverting a Vandermonde matrix in minimum parallel time","volume":"38","author":"Preparata","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(99)00234-0_BIB18","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1016\/S0022-0000(73)80031-5","article-title":"Maze recognizing automata and nondeterministic tape complexity","volume":"7","author":"Savitch","year":"1973","journal-title":"J. Comput. System Sci."},{"year":"1987","series-title":"Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets","author":"Soare","key":"10.1016\/S0304-3975(99)00234-0_BIB19"},{"key":"10.1016\/S0304-3975(99)00234-0_BIB20","first-page":"96","article-title":"The method of forcing for nondeterministic automata","volume":"33","author":"Szelepcs\u00e9nyi","year":"1987","journal-title":"Bulle. EATCS"},{"year":"1991","series-title":"Introduction to Coding Theory","author":"van Lint","key":"10.1016\/S0304-3975(99)00234-0_BIB21"},{"issue":"3","key":"10.1016\/S0304-3975(99)00234-0_BIB22","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/141914.141921","article-title":"How reductions to sparse sets collapse the polynomial-time hierarchy: a primer (Part I)","volume":"23","author":"Young","year":"1992","journal-title":"SIGACT News"},{"issue":"4","key":"10.1016\/S0304-3975(99)00234-0_BIB23","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/148080.148084","article-title":"How reductions to sparse sets collapse the polynomial-time hierarchy: a primer (Part II)","volume":"23","author":"Young","year":"1992","journal-title":"SIGACT News"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599002340?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599002340?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T17:11:46Z","timestamp":1733505106000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397599002340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,6]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,6]]}},"alternative-id":["S0304397599002340"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(99)00234-0","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2000,6]]}}}