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)
Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Complexity of proofs (03F20)
Related Items (44)
From Small Space to Small Width in Resolution ⋮ Narrow Proofs May Be Maximally Long ⋮ On space and depth in resolution ⋮ On the complexity of resolution with bounded conjunctions ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ Unnamed Item ⋮ A note about \(k\)-DNF resolution ⋮ Space Complexity in Polynomial Calculus ⋮ Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ Special issue in memory of Misha Alekhnovich. Foreword ⋮ Cliques enumeration and tree-like resolution proofs ⋮ Algebraic proofs over noncommutative formulas ⋮ The depth of resolution proofs ⋮ Proof Complexity Meets Algebra ⋮ An Introduction to Lower Bounds on Resolution Proof Systems ⋮ On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution ⋮ Resolution over linear equations and multilinear proofs ⋮ On semantic cutting planes with very small coefficients ⋮ A combinatorial characterization of resolution width ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ The treewidth of proofs ⋮ Space proof complexity for random 3-CNFs ⋮ An Upper Bound on the Space Complexity of Random Formulae in Resolution ⋮ A simplified way of proving trade-off results for resolution ⋮ Unnamed Item ⋮ The Complexity of Propositional Proofs ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ Reversible pebble games and the relation between tree-like and general resolution space ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Supercritical Space-Width Trade-offs for Resolution ⋮ A combinatorial characterization of treelike resolution space ⋮ 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 ⋮ Bounded-Resource Reasoning as (Strong or Classical) Planning ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ Total Space in Resolution ⋮ Verifying time, memory and communication bounds in systems of reasoning agents ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Another look at degree lower bounds for polynomial calculus ⋮ Resolution over linear equations modulo two
This page was built for publication: Space Complexity in Propositional Calculus
