{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:40Z","timestamp":1750694740861},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,10,17]],"date-time":"2017-10-17T00:00:00Z","timestamp":1508198400000},"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":["comput. complex."],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s00037-017-0163-1","type":"journal-article","created":{"date-parts":[[2017,10,17]],"date-time":"2017-10-17T10:41:21Z","timestamp":1508236881000},"page":"511-559","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On Space and Depth in Resolution"],"prefix":"10.1007","volume":"27","author":[{"given":"Alexander","family":"Razborov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,10,17]]},"reference":[{"issue":"4","key":"163_CR1","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1137\/S0097539700366735","volume":"31","author":"M. Alekhnovich","year":"2002","unstructured":"Alekhnovich M., Ben-Sasson E., Razborov A., Wigderson A. (2002) Space complexity in propositional calculus. SIAM Journal on Computing 31(4): 1184\u20131211","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"163_CR2","doi-asserted-by":"crossref","first-page":"1347","DOI":"10.1137\/06066850X","volume":"38","author":"M. Alekhnovich","year":"2008","unstructured":"Alekhnovich M., Razborov A. (2008) Resolution is not automatizable unless $${W[P]}$$ W [ P ] is tractable. SIAM Journal on Computing 38(4): 1347\u20131363","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"163_CR3","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/j.jcss.2007.06.025","volume":"74","author":"A. Atserias","year":"2008","unstructured":"Atserias A., Dalmau V. (2008) A combinatorial characterization of resolution width. Journal of Computer and System Sciences 74(3): 323\u2013334","journal-title":"Journal of Computer and System Sciences"},{"key":"163_CR4","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/S0195-6698(05)80029-0","volume":"13","author":"L. Babai","year":"1992","unstructured":"Babai L., Seress A. (1992) On the Diameter of Permutation Groups. European Journal of Combinatorics 13: 231\u2013243","journal-title":"European Journal of Combinatorics"},{"key":"163_CR5","unstructured":"B. Barak & D. Steurer (2014). Sum-of-squares proofs and the quest toward optimal algorithms. In Proceedings of International Congress of Mathematicians (ICM), volume IV, 509\u2013533."},{"key":"163_CR6","doi-asserted-by":"crossref","unstructured":"C. Beck, J. Nordstr\u00f6m & B. Tang (2013). Some trade-off results for polynomial calculus: extended abstract. In Proceedings of the 45th ACM Symposium on the Theory of Computing, 813\u2013822.","DOI":"10.1145\/2488608.2488711"},{"issue":"6","key":"163_CR7","doi-asserted-by":"crossref","first-page":"2511","DOI":"10.1137\/080723880","volume":"38","author":"E. Ben-Sasson","year":"2009","unstructured":"Ben-Sasson E. (2009) Size-space tradeoffs for resolution. SIAM Journal on Computing 38(6): 2511\u20132525","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"163_CR8","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1145\/375827.375835","volume":"48","author":"E. Ben-Sasson","year":"2001","unstructured":"Ben-Sasson E., Wigderson A. (2001) Short Proofs are Narrow - Resolution made Simple. Journal of the ACM 48(2): 149\u2013169","journal-title":"Journal of the ACM"},{"key":"163_CR9","doi-asserted-by":"crossref","unstructured":"C. Berkholz & J. Nordstr\u00f6m (2016a). Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. In Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science, 267\u2013276.","DOI":"10.1145\/2933575.2934560"},{"key":"163_CR10","unstructured":"C. Berkholz & J. Nordstr\u00f6m (2016b). Supercritical Space-Width Trade-offs for Resolution. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming, 57:1\u201357:14."},{"key":"163_CR11","unstructured":"A. Blake (1937). Canonical expressions in Boolean algebra. Ph.D. thesis, University of Chicago."},{"key":"163_CR12","unstructured":"I. Bonacina (2016). Total space in Resolution is at least width squared. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming, 56:1\u201356:13."},{"issue":"1","key":"163_CR13","doi-asserted-by":"crossref","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"Cook S.A., Reckhow A.R. (1979) The relative efficiency of propositional proof systems. Journal of Symbolic Logic 44(1): 36\u201350","journal-title":"Journal of Symbolic Logic"},{"issue":"1","key":"163_CR14","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1006\/inco.2001.2921","volume":"171","author":"J.L. Esteban","year":"2001","unstructured":"Esteban J.L., Tor\u00e1n J. (2001) Space bounds for resolution. Information and Computation 171(1): 84\u201397","journal-title":"Information and Computation"},{"key":"163_CR15","doi-asserted-by":"crossref","unstructured":"Y. Filmus, M. Lauria, M. Mik\u0161a, J. Nordstr\u00f6m & M. Vinyals (2015). From Small Space to Small Width in Resolution. ACM Transactions on Computational Logic 16(4), article 28.","DOI":"10.1145\/2746339"},{"key":"163_CR16","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1016\/S0304-3975(00)00157-2","volume":"259","author":"D. Grigoriev","year":"2001","unstructured":"Grigoriev D. (2001) Linear lower bounds on degrees of Postivestellensatz calculus proofs for the parity. Theoretical Computer Science 259: 613\u2013622","journal-title":"Theoretical Computer Science"},{"key":"163_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-9(3:15)2013","volume":"9","author":"J. Nordstr\u00f6m","year":"2013","unstructured":"Nordstr\u00f6m J. (2013) Pebble Games, Proof Complexity and Time-Space Trade-Offs. Logical Methods in Computer Science 9: 1\u201363","journal-title":"Logical Methods in Computer Science"},{"key":"163_CR18","doi-asserted-by":"crossref","unstructured":"A. Razborov (2016). A New Kind of Tradeoffs in Propositional Proof Complexity. Journal of the ACM 62(3), article 16.","DOI":"10.1145\/2858790"},{"key":"163_CR19","unstructured":"A. Razborov (2017). On the Width of Semi-Algebraic Proofs and Algorithms. Mathematics of Operation Research http:\/\/pubsonline.informs.org\/doi\/abs\/10.1287\/moor.2016.0840 ."},{"issue":"1","key":"163_CR20","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/321250.321253","volume":"12","author":"J.A. Robinson","year":"1965","unstructured":"Robinson J.A. (1965) A machine-oriented logic based on the resolution principle. Journal of the ACM 12(1): 23\u201341","journal-title":"Journal of the ACM"},{"key":"163_CR21","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s11225-011-9356-9","volume":"99","author":"A. Urquhart","year":"2011","unstructured":"Urquhart A. (2011) The Depth of Resolution Proofs. Studia Logica 99: 349\u2013364","journal-title":"Studia Logica"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-017-0163-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0163-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0163-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T20:05:39Z","timestamp":1570219539000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-017-0163-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,17]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["163"],"URL":"https:\/\/doi.org\/10.1007\/s00037-017-0163-1","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,17]]}}}