A note about \(k\)-DNF resolution
From MaRDI portal
Publication:1641156
DOI10.1016/j.ipl.2018.04.014zbMath1479.03026OpenAlexW2801113289WikidataQ61732569 ScholiaQ61732569MaRDI QIDQ1641156
Publication date: 15 June 2018
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2018.04.014
Related Items (2)
Approximate counting and NP search problems ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- On the power of clause-learning SAT solvers as resolution engines
- Near optimal seperation of tree-like and general resolution
- The intractability of resolution
- Optimality of size-width tradeoffs for resolution
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Space bounds for resolution
- Short resolution proofs for a sequence of tricky formulas
- A characterization of tree-like resolution size
- A combinatorial characterization of resolution width
- On the weak pigeonhole principle
- Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers
- Pebble Games, Proof Complexity, and Time-Space Trade-offs
- FRAGMENTS OF APPROXIMATE COUNTING
- Optimality of size-degree tradeoffs for polynomial calculus
- The Ordering Principle in a Fragment of Approximate Counting
- From small space to small width in resolution
- Space Complexity in Propositional Calculus
- Expander graphs and their applications
- The Pebbling Problem is Complete in Polynomial Space
- The relative efficiency of propositional proof systems
- Lower bounds to the size of constant-depth propositional proofs
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Short proofs are narrow—resolution made simple
- GRASP: a search algorithm for propositional satisfiability
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- A Machine-Oriented Logic Based on the Resolution Principle
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
This page was built for publication: A note about \(k\)-DNF resolution
