Space Complexity in Propositional Calculus
From MaRDI portal
Publication:3149864
DOI10.1137/S0097539700366735zbMATH Open1004.03047MaRDI QIDQ3149864FDOQ3149864
Authors: Michael Alekhnovich, Eli Ben-Sasson, A. Wigderson, Alexander Razborov 
Publication date: 29 September 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
Classical propositional logic (03B05) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (52)
- Proof complexity and the binary encoding of combinatorial principles
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Practical algebraic calculus and Nullstellensatz with the checkers Pacheck and Pastèque and Nuss-Checker
- On the complexity of resolution with bounded conjunctions
- Proof Complexity Meets Algebra
- A combinatorial characterization of treelike resolution space
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- Title not available (Why is that?)
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- Title not available (Why is that?)
- The Complexity of Propositional Proofs
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- Space proof complexity for random 3-CNFs
- Efficient reduction of nondeterministic automata with application to language inclusion testing
- Verifying time, memory and communication bounds in systems of reasoning agents
- On semantic cutting planes with very small coefficients
- A simplified way of proving trade-off results for resolution
- Special issue in memory of Misha Alekhnovich. Foreword
- An Introduction to Lower Bounds on Resolution Proof Systems
- Space complexity in propositional calculus
- Cumulative space in black-white pebbling and resolution
- A tutorial on time and space bounds in tree-like resolution
- A note about \(k\)-DNF resolution
- Trade-offs between time and memory in a tighter model of CDCL SAT solvers
- The treewidth of proofs
- Total space in resolution
- Reversible pebble games and the relation between tree-like and general resolution space
- Nullstellensatz size-degree trade-offs from reversible pebbling
- From small space to small width in resolution
- Resolution over linear equations modulo two
- The relation between polynomial calculus, Sherali-Adams, and sum-of-squares proofs
- On minimal unsatisfiability and time-space trade-offs for \(k\)-DNF resolution
- Nullstellensatz size-degree trade-offs from reversible pebbling
- A combinatorial characterization of resolution width
- Space Complexity in Polynomial Calculus
- Another look at degree lower bounds for polynomial calculus
- Efficient rational proofs for space bounded computations
- Supercritical space-width trade-offs for resolution
- Algebraic proofs over noncommutative formulas
- The depth of resolution proofs
- Title not available (Why is that?)
- Computer Science Logic
- Bounded-Resource Reasoning as (Strong or Classical) Planning
- Narrow proofs may be maximally long
- Resolution over linear equations and multilinear proofs
- On space and depth in resolution
- Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
- A framework for space complexity in algebraic proof systems
- Title not available (Why is that?)
- Cliques enumeration and tree-like resolution proofs
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- An Upper Bound on the Space Complexity of Random Formulae in Resolution
This page was built for publication: Space Complexity in Propositional Calculus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3149864)
