Space Complexity in Propositional Calculus
From MaRDI portal
Publication:3149864
Recommendations
Cited in
(52)- On the complexity of resolution with bounded conjunctions
- A combinatorial characterization of treelike resolution space
- Proof Complexity Meets Algebra
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- scientific article; zbMATH DE number 7561756 (Why is no real title available?)
- Proof complexity and the binary encoding of combinatorial principles
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- scientific article; zbMATH DE number 2081098 (Why is no real title available?)
- The Complexity of Propositional Proofs
- Space proof complexity for random 3-CNFs
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- Verifying time, memory and communication bounds in systems of reasoning agents
- Efficient reduction of nondeterministic automata with application to language inclusion testing
- A simplified way of proving trade-off results for resolution
- Special issue in memory of Misha Alekhnovich. Foreword
- On semantic cutting planes with very small coefficients
- An Introduction to Lower Bounds on Resolution Proof Systems
- Space complexity in propositional calculus
- Cumulative space in black-white pebbling and resolution
- A note about k-DNF resolution
- A tutorial on time and space bounds in tree-like resolution
- The treewidth of proofs
- Trade-offs between time and memory in a tighter model of CDCL SAT solvers
- 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
- Resolution over linear equations modulo two
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- From small space to small width in resolution
- The relation between polynomial calculus, Sherali-Adams, and sum-of-squares proofs
- On minimal unsatisfiability and time-space trade-offs for \(k\)-DNF resolution
- A combinatorial characterization of resolution width
- Nullstellensatz size-degree trade-offs from reversible pebbling
- Space Complexity in Polynomial Calculus
- Another look at degree lower bounds for polynomial calculus
- Efficient rational proofs for space bounded computations
- Algebraic proofs over noncommutative formulas
- The depth of resolution proofs
- scientific article; zbMATH DE number 6482141 (Why is no real title available?)
- Supercritical space-width trade-offs for resolution
- Bounded-Resource Reasoning as (Strong or Classical) Planning
- Computer Science Logic
- Resolution over linear equations and multilinear proofs
- Narrow proofs may be maximally long
- Practical algebraic calculus and Nullstellensatz with the checkers Pacheck and Pastèque and Nuss-Checker
- 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
- Cliques enumeration and tree-like resolution proofs
- scientific article; zbMATH DE number 7029312 (Why is no real title available?)
- 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)
