A note about \(k\)-DNF resolution
type: Item
instance of: scholarly article
title: A note about \(k\)-DNF resolution
zbMATH Open document ID: 1479.03026
author: Massimo Lauria
published in: Information Processing Letters
publication date: 2018-06-15T00:00:00Z
Mathematics Subject Classification ID: 03F20
zbMATH DE Number: 6889956
zbMATH Keywords: theory of computation
zbMATH Keywords: proof complexity
zbMATH Keywords: \(k\)-DNF
zbMATH Keywords: resolution
describes a project that uses: Chaff
MaRDI profile type: Publication
full work available at URL: j.ipl.2018.04.014
OpenAlex ID: W2801113289
Wikidata QID: Q61732569
cites work: Space Complexity in Propositional Calculus
cites work: A combinatorial characterization of resolution width
cites work: Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
cites work: The Ordering Principle in a Fragment of Approximate Counting
cites work: Near optimal seperation of tree-like and general resolution
cites work: Short proofs are narrow—resolution made simple
cites work: A characterization of tree-like resolution size
cites work: Q5769706
cites work: Optimality of size-width tradeoffs for resolution
cites work: Fragments of approximate counting
cites work: The relative efficiency of propositional proof systems
cites work: A machine program for theorem-proving
cites work: A Computing Procedure for Quantification Theory
cites work: Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers
cites work: Space bounds for resolution
cites work: From small space to small width in resolution
cites work: Optimality of size-degree tradeoffs for polynomial calculus
cites work: The Pebbling Problem is Complete in Polynomial Space
cites work: The intractability of resolution
cites work: Expander graphs and their applications
cites work: On the weak pigeonhole principle
cites work: Lower bounds to the size of constant-depth propositional proofs
cites work: Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
cites work: GRASP: a search algorithm for propositional satisfiability
cites work: Pebble games, proof complexity, and time-space trade-offs
cites work: Q4185781
cites work: On the power of clause-learning SAT solvers as resolution engines
cites work: Entropy waves, the zig-zag graph product, and new constant-degree expanders
cites work: A Machine-Oriented Logic Based on the Resolution Principle
cites work: A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
cites work: Short resolution proofs for a sequence of tricky formulas
DOI: 10.1016/J.IPL.2018.04.014
description: scientific article; zbMATH DE number 6889956