Space Complexity in Propositional Calculus
From MaRDI portal
Recommendations
Cited in
(58)- 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
- Efficient rational proofs for space bounded computations
- 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
- Reversible pebble games and the relation between tree-like and general resolution space
- Nullstellensatz size-degree trade-offs from reversible pebbling
- 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
- scientific article; zbMATH DE number 6482141 (Why is no real title available?)
- On minimal unsatisfiability and time-space trade-offs for k-DNF resolution
- Space complexity in propositional calculus
- The relation between polynomial calculus, Sherali-Adams, and sum-of-squares proofs
- Bounded-Resource Reasoning as (Strong or Classical) Planning
- Special issue in memory of Misha Alekhnovich. Foreword
- An Upper Bound on the Space Complexity of Random Formulae in Resolution
- scientific article; zbMATH DE number 2081098 (Why is no real title available?)
- Proof Complexity Meets Algebra
- Efficient reduction of nondeterministic automata with application to language inclusion testing
- scientific article; zbMATH DE number 7029312 (Why is no real title available?)
- Cumulative space in black-white pebbling and resolution
- Nullstellensatz size-degree trade-offs from reversible pebbling
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- scientific article; zbMATH DE number 7561756 (Why is no real title available?)
- 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
- Computer Science Logic
- The Complexity of Propositional Proofs
- 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
- Algebraic proofs over noncommutative formulas
- The depth of resolution proofs
- 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
- Polynomial calculus space and resolution width
- Towards an understanding of polynomial calculus: new separations and lower bounds
- Proving unsatisfiability with hitting formulas
- Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
- A generalized method for proving polynomial calculus degree lower bounds
- Resolution over linear equations: combinatorial games for tree-like size and space
- Resolution over linear equations and multilinear proofs
- A simplified way of proving trade-off results for 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)
