{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:29Z","timestamp":1725663689604},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_160","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:20:05Z","timestamp":1330262405000},"page":"427-438","source":"Crossref","is-referenced-by-count":3,"title":["On sets bounded truth-table reducible to P-selective sets"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Thierauf","sequence":"first","affiliation":[]},{"given":"Seinosuke","family":"Toda","sequence":"additional","affiliation":[]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"V. Arvind, Y. Han, L. Hemachandra, J. K\u00f6bler, A. Lozano, M. Mundhenk, M. Ogiwara, U. Sch\u00f6ning, R. Silvestri, and T. Thierauf. Reductions to sets of low information content. Recent Developments in Complexity Theory. Cambridge University Press, 1993. (Also available as Technical Report TR-417, University of Rochester, Department of Computer Science, Rochester, NY, April 1992).","DOI":"10.1007\/3-540-55719-9_72"},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"E. Allender. The complexity of sparse sets in P, In Proceedings 1st Structure in Complexity Theory Conference, 1\u201311, IEEE Computer Society, 1986.","DOI":"10.1007\/3-540-16486-3_85"},{"key":"34_CR3","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. EATCS Monographs on Theoretical Computer Science, Springer-Verlag (1988).","DOI":"10.1007\/978-3-642-97062-7"},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity II. EATCS Monographs on Theoretical Computer Science, Springer-Verlag (1991).","DOI":"10.1007\/978-3-642-75357-2"},{"key":"34_CR5","unstructured":"R. Beigel. NP-hard sets are P-superterse unless R = NP. Technical Report 88-04, Department of Computer Science, The John Hopkins University, 1988."},{"key":"34_CR6","unstructured":"T. Corman, C. Leiserson, and R. Rivest. Introduction to Algorithms. The MIT Press, McGraw-Hill Book Company, 1990."},{"key":"34_CR7","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/S0019-9958(84)80053-4","volume":"61","author":"S. Evan","year":"1984","unstructured":"S. Evan, A. Selman, and Y. Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61:114\u2013133, 1984.","journal-title":"Information and Control"},{"key":"34_CR8","doi-asserted-by":"crossref","unstructured":"L. Hemachandra, A. Hoene, M. Ogiwara, A. Selman, T. Thierauf, and J. Wang. Selectivity. In Proceedings of the 5th International Conference on Computing and Information, 1993.","DOI":"10.1109\/ICCI.1993.315404"},{"key":"34_CR9","doi-asserted-by":"crossref","unstructured":"L. Hemachandra, M. Ogiwara, and O. Watanabe. How hard are sparse sets? In Proc. 7th Structure in Complexity Theory Conference, IEEE 222\u2013238, 1992.","DOI":"10.1109\/SCT.1992.215396"},{"key":"34_CR10","doi-asserted-by":"crossref","unstructured":"B. Jenner and J. Tor\u00e1n. Computing functions with parallel queries to NP. In Proc. 8th Structure in Complexity Theory Conference, IEEE 280\u2013291, 1993.","DOI":"10.1109\/SCT.1993.336519"},{"issue":"2","key":"34_CR11","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1090\/S0002-9947-1968-0220595-7","volume":"131","author":"C. Jockusch","year":"1968","unstructured":"C. Jockusch. Semirecursive sets and positive reducibility. Transactions of the AMS, 131(2):420\u2013436, 1968.","journal-title":"Transactions of the AMS"},{"key":"34_CR12","first-page":"191","volume":"28","author":"R. Karp","year":"1982","unstructured":"R. Karp, R. Lipton. Turing machines that take advice. L'Enseignement Math\u00e9matique, 28:191\u2013209, 1982.","journal-title":"L'Enseignement Math\u00e9matique"},{"key":"34_CR13","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(83)90013-2","volume":"26","author":"K. Ko","year":"1983","unstructured":"K. Ko. On self-reducibility and weak P-selectivity. Journal of Computer and System Sciences, 26:209\u2013221, 1983.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"34_CR14","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. Ladner","year":"1975","unstructured":"R. Ladner, N. Lynch, and A. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1(2):103\u2013124, 1975.","journal-title":"Theoretical Computer Science"},{"key":"34_CR15","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S. Mahaney","year":"1982","unstructured":"S. Mahaney. Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. Journal of Computer and System Sciences 25:130\u2013143, 1982.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"34_CR16","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M. Ogiwara","year":"1991","unstructured":"M. Ogiwara and O. Watanabe. On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing, 20(3):471\u2013483, 1991.","journal-title":"SIAM Journal on Computing"},{"key":"34_CR17","unstructured":"S. Saluja. Relativized limitations of the left set technique and closure classes of sparse sets. Manuscript."},{"key":"34_CR18","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning. The power of counting. In Complexity Theory Retrospective (A. Selman Ed.), Springer-Verlag (1990), 204\u2013223.","DOI":"10.1007\/978-1-4612-4478-3_9"},{"key":"34_CR19","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A. Selman","year":"1979","unstructured":"A. Selman. P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. Mathematical Systems Theory, 13:55\u201365, 1979.","journal-title":"Mathematical Systems Theory"},{"key":"34_CR20","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/S0019-9958(82)80084-3","volume":"52","author":"A. Selman","year":"1982","unstructured":"A. Selman. Analogues of semirecursive sets and effective reducibilities to the study of NP complexity. Information and Control, 52:36\u201351, 1982.","journal-title":"Information and Control"},{"key":"34_CR21","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(82)90039-1","volume":"19","author":"A. Selman","year":"1982","unstructured":"A. Selman. Reductions on NP and P-selective sets. Theoretical Computer Science, 19:287\u2013304, 1982.","journal-title":"Theoretical Computer Science"},{"key":"34_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"L. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science 3:1\u201322, 1977.","journal-title":"Theoretical Computer Science"},{"key":"34_CR23","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BF02090391","volume":"24","author":"S. Toda","year":"1991","unstructured":"S. Toda. On polynomial-time truth-table reducibilities of intractable sets to P-selective sets. Mathematical Systems Theory, 24:69\u201382, 1991.","journal-title":"Mathematical Systems Theory"},{"key":"34_CR24","unstructured":"J. Tor\u00e1n. Personal Communication."},{"issue":"1","key":"34_CR25","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"L. Valiant. Relative complexity of checking and evaluating. Information Processing Letters, 5(1):20\u201323, 1976.","journal-title":"Information Processing Letters"},{"key":"34_CR26","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L. Valiant","year":"1986","unstructured":"L. Valiant and V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science 47:85\u201393, 1986.","journal-title":"Theoretical Computer Science"},{"key":"34_CR27","unstructured":"O. Watanabe. Unpublished note."}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_160.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:13:59Z","timestamp":1605647639000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_160"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_160","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}