{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:12Z","timestamp":1725488532498},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_34","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T12:03:24Z","timestamp":1186056204000},"page":"407-418","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Optimal Proof Systems and Sparse Sets"],"prefix":"10.1007","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[]},{"given":"Steve","family":"Fenner","sequence":"additional","affiliation":[]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[]},{"given":"Dieter","family":"van Melkebeek","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"issue":"3","key":"34_CR1","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1137\/0224044","volume":"24","author":"H. Buhrman","year":"1995","unstructured":"H. Buhrman, E. Hemaspaandra, and L. Longpr\u00e9. SPARSE reduces conjunctively to TALLY. SIAM Journal on Computing, 24(3):673\u2013681, 1995.","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"34_CR2","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1137\/0217056","volume":"17","author":"R. Book","year":"1988","unstructured":"R. Book and K. Ko. On sets truth-table reducible to sparse sets. SIAM Journal on Computing, 17(5):903\u2013919, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"34_CR3","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S. Cook","year":"1979","unstructured":"S. Cook and R. Reckhow. The relative effciency of propositional proof systems. Journal of Symbolic Logic, 44:36\u201350, 1979.","journal-title":"Journal of Symbolic Logic"},{"key":"34_CR4","first-page":"229","volume":"52","author":"L. Fortnow","year":"1994","unstructured":"L. Fortnow. The role of relativization in complexity theory. Bulletin of the European Association for Theoretical Computer Science, 52:229\u2013244, February 1994.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"34_CR5","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0304-3975(84)90111-7","volume":"34","author":"J. Hartmanis","year":"1984","unstructured":"J. Hartmanis and L. Hemachandra. Complexity classes without machines: On complete languages for UP. Theoretical Computer Science, 34:17\u201332, 1984.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"34_CR6","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1142\/S012905419300016X","volume":"4","author":"L. Hemaspaandra","year":"1993","unstructured":"L. Hemaspaandra, S. Jain, and N. Vereshchagin. Banishing robust turing completeness. International Journal of Foundations of Computer Science, 4(3):245\u2013265, 1993.","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"1\u20132","key":"34_CR7","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0304-3975(84)90111-7","volume":"34","author":"J. Hartmanis","year":"1984","unstructured":"J. Hartmanis and Y. Yesha. Computation times of NP sets of different densities. Theoretical Computer Science, 34(1\u20132):17\u201332, November 1984.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"34_CR8","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/0890-5401(89)90029-1","volume":"81","author":"K. Ko","year":"1989","unstructured":"K. Ko. Distinguishing conjunctive and disjunctive reducibilities by sparse sets. Information and Computation, 81(1):62\u201387, 1989.","journal-title":"Information and Computation"},{"key":"34_CR9","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.2307\/2274765","volume":"54","author":"J. Kraj\u00ed\u010dek","year":"1989","unstructured":"J. Kraj\u00ed\u010dek and P. Pudl\u00e1k. Propositional proof systems, the consistency of first order theories and the complexity of computations. Journal of Symbolic Logic, 54:1063\u20131079, 1989.","journal-title":"Journal of Symbolic Logic"},{"key":"34_CR10","first-page":"659","volume-title":"Proceedings of the 31st ACM Symposium on the Theory of Computing","author":"A. Klivans","year":"1999","unstructured":"A. Klivans and D. van Melkebeek. Graph nonisomorhism has subexponential size proofs unless the polynomial-time hierarchy collapses. In Proceedings of the 31st ACM Symposium on the Theory of Computing, pages 659\u2013667. ACM, New York, 1999."},{"key":"34_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"1997","unstructured":"M. Li and P. Vit\u00e1nyi. An Introduction to Kolmogorov Complexity and Its Applications. Graduate Texts in Computer Science. Springer, New York, second edition, 1997.","edition":"second edition"},{"key":"34_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/BFb0028583","volume-title":"Proceedings of the 15th Symposium on Theoretical Aspects of Computer Science","author":"J. Messner","year":"1998","unstructured":"J. Messner and J. Tor\u00e1n. Optimal proof systems for propositional logic and complete sets. In Proceedings of the 15th Symposium on Theoretical Aspects of Computer Science, volume 1373 of Lecture Notes in Computer Science, pages 477\u2013487. Springer, 1998."},{"key":"34_CR13","first-page":"215","volume-title":"Proceedings of the 8th IEEE Structure in Complexity Theory Conference","author":"S. Saluja","year":"1993","unstructured":"S. Saluja. Relativized limitations of left set technique and closure classes of sparse sets. In Proceedings of the 8th IEEE Structure in Complexity Theory Conference, pages 215\u2013223. IEEE, New York, 1993."},{"issue":"5","key":"34_CR14","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0020-0190(93)90102-F","volume":"46","author":"U. Sch\u00f6ning","year":"1993","unstructured":"U. Sch\u00f6ning. On random reductions from sparse sets to tally sets. Information Processing Letters, 46(5):239\u2013241, July 1993.","journal-title":"Information Processing Letters"},{"issue":"1","key":"34_CR15","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. Seiferas","year":"1978","unstructured":"J. Seiferas, M. Fischer, and A. Meyer. Separating nondeterministic time complexity classes. Journal of the ACM, 25(1):146\u2013167, 1978.","journal-title":"Journal of the ACM"},{"issue":"3","key":"34_CR16","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0304-3975(83)90015-4","volume":"26","author":"S. \u017d\u00e0k","year":"1983","unstructured":"S. \u017d\u00e0k. A Turing machine time hierarchy. Theoretical Computer Science, 26(3):327\u2013333, 1983.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T09:48:38Z","timestamp":1558259318000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_34","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"24 March 2000","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}