{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:32Z","timestamp":1760202572003,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414131"},{"type":"electronic","value":"9783540444503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44450-5_29","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T08:26:08Z","timestamp":1187252768000},"page":"361-372","source":"Crossref","is-referenced-by-count":4,"title":["Is the Standard Proof System for SAT P-Optimal?"],"prefix":"10.1007","author":[{"given":"Johannes","family":"K\u00f6bler","sequence":"first","affiliation":[]},{"given":"Jochen","family":"Messner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,11,24]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Jos\u00e9 Luis Balc\u00e1zar, Josep D\u00edaz, and Joaquim Gabarr\u00f3. Structural Complexity I. Springer-Verlag, 2nd edition, 1995.","DOI":"10.1007\/978-3-642-79235-9"},{"issue":"3","key":"29_CR2","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1137\/0213030","volume":"13","author":"R. V. Book","year":"1984","unstructured":"Ronald V. Book, Timothy J. Long, and Alan L. Selman. Quantitative relativizations of complexity classes. SIAM Journal on Computing, 13(3):461\u2013487, 1984.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"29_CR3","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S. A. Cook","year":"1979","unstructured":"Stephen A. Cook and Robert A. Reckhow. The relative efficiency of propositional proof systems. The Journal of Symbolic Logic, 44(1):36\u201350, 1979.","journal-title":"The Journal of Symbolic Logic"},{"issue":"5","key":"29_CR4","doi-asserted-by":"publisher","first-page":"1759","DOI":"10.1137\/S0097539796304220","volume":"28","author":"P. Crescenzi","year":"1999","unstructured":"Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, and Luca Trevisan. Structure in approximation classes. SIAM Journal on Computing, 28(5):1759\u20131782, 1999.","journal-title":"SIAM Journal on Computing"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, and John D. Rogers. Invertingonto functions. In Proceedings of the 11th Conference on Computational Complexity, pages 213\u2013222. IEEE, 1996.","DOI":"10.1109\/CCC.1996.507683"},{"key":"29_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/3-540-58325-4_204","volume-title":"Separability and one-way functions","author":"L. Fortnow","year":"1994","unstructured":"Lance Fortnow and John D. Rogers. Separability and one-way functions. In Proceedings of the 5th International Symposium on Algorithms and Computation, LNCS #834, pages 396\u2013404. Springer-Verlag, 1994."},{"issue":"2","key":"29_CR7","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"Joachim Grollmann and Alan L. Selman. Complexity measures for public-key cryptosystems. SIAM Journal on Computing, 17(2):309\u2013335, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"29_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/3-540-58325-4_166","volume-title":"Computingsolu tions uniquely collapses the polynomial hierarchy","author":"L. A. Hemaspaandra","year":"1994","unstructured":"Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, and Alan L. Selman. Computingsolu tions uniquely collapses the polynomial hierarchy. In Proceedings of the 5th International Symposium on Algorithms and Computation, LNCS #834, pages 56\u201364. Springer-Verlag, 1994."},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Russel Impagliazzo and Moni Naor. Decision trees and downward closures (extended abstract). In Proceedings of the Third Conference on Structure in Complexity Theory, pages 29\u201338. IEEE, 1988.","DOI":"10.1109\/SCT.1988.5260"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(85)90085-4","volume":"37","author":"K.-I. Ko","year":"1985","unstructured":"Ker-I Ko. On some natural complete operators. Theoretical Computer Science, 37:1\u201330, 1985.","journal-title":"Theoretical Computer Science"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Johannes K\u00f6bler and Jochen Messner. Complete problems for promise classes by optimal proof systems for test sets. In Proceedings of the 13th Conference on Computational Complexity, pages 132\u2013140. IEEE, 1998.","DOI":"10.1109\/CCC.1998.694599"},{"issue":"3","key":"29_CR12","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.2307\/2274765","volume":"54","author":"J. Kraj\u00ed\u010dek","year":"1989","unstructured":"Jan Kraj\u00ed\u010dek and Pavel Pudl\u00e1k. Propositional proof systems, the consistency of first order theories and the complexity of computations. The Journal of Symbolic Logic, 54(3):1063\u20131079, 1989.","journal-title":"The Journal of Symbolic Logic"},{"key":"29_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/3-540-60178-3_86","volume-title":"Logic and Computational Complexity","author":"J. Kraj\u00ed\u010dek","year":"1995","unstructured":"Jan Kraj\u00ed\u010dek and Pavel Pudl\u00e1k. Some consequences of cryptographical conjectures for S 1 2 and EF. In D. Leivant, editor, Logic and Computational Complexity, LNCS #960, pages 210\u2013220. Springer-Verlag, 1995."},{"key":"29_CR14","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0304-3975(81)90007-4","volume":"14","author":"T. J. Long","year":"1981","unstructured":"Timothy J. Long. On \u03b3-reducibility versus polynomial time many-one reducibility. Theoretical Computer Science, 14:91\u2013101, 1981.","journal-title":"Theoretical Computer Science"},{"key":"29_CR15","series-title":"Lect Notes Comput Sci","volume-title":"On optimal algorithms and optimal proof system","author":"J. Messner","year":"1999","unstructured":"Jochen Messner. On optimal algorithms and optimal proof system. In Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, LNCS#1563. Springer-Verlag, 1999."},{"key":"29_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/BFb0028583","volume-title":"Optimal proof systems for propositional logic and complete sets","author":"J. Messner","year":"1998","unstructured":"Jochen Messner and Jacobo Tor\u00e1n. Optimal proof systems for propositional logic and complete sets. In Proceedings of the 15th Symposium on Theoretical Aspects of Computer Science, LNCS #1373, pages 477\u2013487. Springer-Verlag, 1998."},{"key":"29_CR17","unstructured":"Christos H. Papadimitriou. Computatational Complexity. Addison-Wesley, 1994."},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"Alexander A. Razborov. On provably disjoint NP-pairs. Technical Report RS-94-36, Basic Research in Computer Science Center, Aarhus, 1994.","DOI":"10.7146\/brics.v1i36.21607"},{"key":"29_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BFb0036203","volume-title":"On an optimal quantified propositional proof system and a complete language for NP \u2229 co-NP","author":"Z. Sadowski","year":"1997","unstructured":"Zenon Sadowski. On an optimal quantified propositional proof system and a complete language for NP \u2229 co-NP. In Proceedings of the 11th International Symposium on Fundamentals of Computing Theory, LNCS #1279, pages 423\u2013428. Springer-Verlag, 1997."},{"key":"29_CR20","series-title":"Lect Notes Comput Sci","volume-title":"On an optimal deterministic algorithm for SAT","author":"Z. Sadowski","year":"1999","unstructured":"Zenon Sadowski. On an optimal deterministic algorithm for SAT. In Proceedings of the 12th Annual Conference of the European Association for Computer Science Logic, CSL\u2019 98, LNCS #1584, pages 179-187. Springer-Verlag, 1999."},{"key":"29_CR21","series-title":"Lect Notes Comput Sci","volume-title":"Complexity and Structure","author":"U. Sch\u00f6ning","year":"1985","unstructured":"Uwe Sch\u00f6ning. Complexity and Structure, LNCS #211. Springer-Verlag, 1985."},{"key":"29_CR22","unstructured":"Uwe Sch\u00f6ningan and Jacobo Tor\u00e1n. A note on the size of craigin terpolants, 1996. Unpublished manuscript."},{"issue":"2","key":"29_CR23","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/S0022-0000(05)80009-1","volume":"48","author":"A. L. Selman","year":"1994","unstructured":"Alan L. Selman. A taxonomy of complexity classes of functions. Journal of Computer and System Sciences, 48(2):357\u2013381, 1994.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"29_CR24","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. G. Valiant","year":"1976","unstructured":"Leslie G. Valiant. Relative complexity of checkingan and evaluating. Information Processing Letters, 5(1):20\u201323, 1976.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44450-5_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T11:30:09Z","timestamp":1737372609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44450-5_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540414131","9783540444503"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-44450-5_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}