{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T05:26:50Z","timestamp":1743053210102,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319587400"},{"type":"electronic","value":"9783319587417"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-58741-7_34","type":"book-chapter","created":{"date-parts":[[2017,5,11]],"date-time":"2017-05-11T12:59:28Z","timestamp":1494507568000},"page":"364-374","source":"Crossref","is-referenced-by-count":0,"title":["Total Nondeterministic Turing Machines and a p-optimal Proof System for SAT"],"prefix":"10.1007","author":[{"given":"Zenon","family":"Sadowski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,12]]},"reference":[{"key":"34_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-79235-9","volume-title":"Structural Complexity I","author":"J Balcazar","year":"1995","unstructured":"Balcazar, J., D\u00edaz, J., Gabarr\u00f3, J.: Structural Complexity I. Springer, Heidelberg (1995)"},{"key":"34_CR2","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.tcs.2007.02.005","volume":"377","author":"O Beyersdorff","year":"2007","unstructured":"Beyersdorff, O.: Classes of representable disjoint NP-pairs. Theoret. Comput. Sci. 377, 93\u2013109 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"34_CR3","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/s00224-007-9023-8","volume":"43","author":"O Beyersdorff","year":"2008","unstructured":"Beyersdorff, O.: Tuples of disjoint NP-sets. Theory Comput. Syst. 43(2), 118\u2013135 (2008)","journal-title":"Theory Comput. Syst."},{"key":"34_CR4","doi-asserted-by":"crossref","first-page":"3839","DOI":"10.1016\/j.tcs.2009.05.021","volume":"410","author":"O Beyersdorff","year":"2009","unstructured":"Beyersdorff, O., K\u00f6bler, J., Messner, J.: Nondeterministic functions and the existence of optimal proof systems. Theoret. Comput. Sci. 410, 3839\u20133855 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"34_CR5","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1002\/malq.201010021","volume":"57","author":"O Beyersdorff","year":"2011","unstructured":"Beyersdorff, O., Sadowski, Z.: Do there exist complete sets for promise classes? Math. Logic Q. 57(6), 535\u2013550 (2011)","journal-title":"Math. Logic Q."},{"key":"34_CR6","doi-asserted-by":"crossref","unstructured":"Cook, S.: The complexity of theorem proving procedures. In: Proceedings of the 3rd ACM Symposium on Theory of Computing, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"key":"34_CR7","doi-asserted-by":"crossref","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S Cook","year":"1979","unstructured":"Cook, S., Reckhow, R.: The relative efficiency of propositional proof systems. J. Symbolic Logic 44, 36\u201350 (1979)","journal-title":"J. Symbolic Logic"},{"key":"34_CR8","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/S0890-5401(03)00119-6","volume":"186","author":"S Fenner","year":"2003","unstructured":"Fenner, S., Fortnow, L., Naik, A., Rogers, J.: Inverting onto functions. Inf. Comput. 186, 90\u2013103 (2003)","journal-title":"Inf. Comput."},{"key":"34_CR9","doi-asserted-by":"crossref","unstructured":"K\u00f6bler, J., Messner, J.: Complete problems for promise classes by optimal proof systems for test sets. In: Proceedings of the 13th IEEE Conference on Computational Complexity CCC 1998, pp. 132\u2013140 (1998)","DOI":"10.1109\/CCC.1998.694599"},{"issue":"1","key":"34_CR10","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/S0890-5401(03)00058-0","volume":"184","author":"J K\u00f6bler","year":"2003","unstructured":"K\u00f6bler, J., Messner, J., Tor\u00e1n, J.: Optimal proof systems imply complete sets for promise classes. Inf. Comput. 184(1), 71\u201392 (2003)","journal-title":"Inf. Comput."},{"key":"34_CR11","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.2307\/2274765","volume":"54","author":"J Kraj\u00ed\u010dek","year":"1989","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P.: Propositional proof systems, the consistency of first order theories and the complexity of computations. J. Symbolic Logic 54, 1063\u20131079 (1989)","journal-title":"J. Symbolic Logic"},{"key":"34_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/3-540-49116-3_51","volume-title":"STACS 99","author":"J Messner","year":"1999","unstructured":"Messner, J.: On optimal algorithms and optimal proof systems. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 541\u2013550. Springer, Heidelberg (1999). doi: 10.1007\/3-540-49116-3_51"},{"key":"34_CR13","unstructured":"Pudl\u00e1k, P.: Incompleteness in the finite domain. The Czech Academy of Science, Institute of Mathematics, Preprint No. 5\u20132016, Praha (2016)"},{"key":"34_CR14","doi-asserted-by":"crossref","unstructured":"Razborov, A.: On provably disjoint NP-pairs. Technical report 94\u2013006, ECCC (1994)","DOI":"10.7146\/brics.v1i36.21607"},{"key":"34_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/BFb0036203","volume-title":"Fundamentals of Computation Theory","author":"Z Sadowski","year":"1997","unstructured":"Sadowski, Z.: On an optimal quantified propositional proof system and a complete language for NP $$\\cap $$ co-NP. In: Chlebus, B.S., Czaja, L. (eds.) FCT 1997. LNCS, vol. 1279, pp. 423\u2013428. Springer, Heidelberg (1997). doi: 10.1007\/BFb0036203"}],"container-title":["Lecture Notes in Computer Science","Unveiling Dynamics and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-58741-7_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T08:49:22Z","timestamp":1569314962000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-58741-7_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319587400","9783319587417"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-58741-7_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}