Space Complexity in Propositional Calculus
From MaRDI portal
Publication:3149864
DOI10.1137/S0097539700366735zbMath1004.03047MaRDI QIDQ3149864
Avi Wigderson, Eli Ben-Sasson, Michael Alekhnovich, Alexander A. Razborov
Publication date: 29 September 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
upper bounds; lower bounds; resolution; polynomial calculus; proof complexity; space complexity; Frege systems
03B35: Mechanization of proofs and logical operations
03D15: Complexity of computation (including implicit computational complexity)
03B05: Classical propositional logic
03F20: Complexity of proofs
Related Items
An Upper Bound on the Space Complexity of Random Formulae in Resolution, Unnamed Item, Unnamed Item, Unnamed Item, Proof Complexity Meets Algebra, An Introduction to Lower Bounds on Resolution Proof Systems, Supercritical Space-Width Trade-offs for Resolution, From Small Space to Small Width in Resolution, Narrow Proofs May Be Maximally Long, The Complexity of Propositional Proofs, Special issue in memory of Misha Alekhnovich. Foreword, Algebraic proofs over noncommutative formulas, The depth of resolution proofs, Resolution over linear equations and multilinear proofs, A simplified way of proving trade-off results for resolution, A combinatorial characterization of treelike resolution space, Verifying time, memory and communication bounds in systems of reasoning agents, On space and depth in resolution, A note about \(k\)-DNF resolution, Cliques enumeration and tree-like resolution proofs, On semantic cutting planes with very small coefficients, On the complexity of resolution with bounded conjunctions, The treewidth of proofs, Space proof complexity for random 3-CNFs, Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution, Another look at degree lower bounds for polynomial calculus, Resolution over linear equations modulo two, A combinatorial characterization of resolution width, A Framework for Space Complexity in Algebraic Proof Systems, Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space, Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers, A Tutorial on Time and Space Bounds in Tree-Like Resolution, Total Space in Resolution, Space Complexity in Polynomial Calculus, On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution, Unnamed Item, Bounded-Resource Reasoning as (Strong or Classical) Planning
