DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2010 · 10 citations · 14 references
ComputingComputer ScienceMathematicsAlgorithmsKnowledge RepresentationTheory Of ComputationAlgorithmic ComplexityComputational ComplexityStructural ComplexityComplexity Of SatisfiabilityFormula ComplexityUnsatisfiabilityUpper Bound Computation
We call a CNF formula {\em linear} if any two clauses have at most one variable in common. We show that there exist unsatisfiable linear $k$-CNF formulas with at most $4k^24^k$ clauses, and on the other hand, any linear $k$-CNF formula with at most $\frac{4^k}{8e^2k^2}$ clauses is satisfiable. The upper bound uses probabilistic means, and we have no explicit construction coming even close to it. One reason for this is that unsatisfiable linear formulas exhibit a more complex structure than general (non-linear) formulas: First, any treelike resolution refutation of any unsatisfiable linear $k$-CNF formula has size at least $2^{2^{\frac{k}{2}-1}}$. This implies that small unsatisfiable linear $k$-CNF formulas are hard instances for Davis-Putnam style splitting algorithms. Second, if we require that the formula $F$ have a {\em strict} resolution tree, i.e. every clause of $F$ is used only once in the resolution tree, then we need at least $a^{a^{\iddots^a}}$ clauses, where $a \approx 2$ and the height of this tower is roughly $k$.
14
A machine program for theorem-proving
Martin Davis, George Logemann, Donald Loveland · Communications of the ACM · 1962 · 3.2K citations · Full text
Short proofs are narrow—resolution made simple
Eli Ben‐Sasson, Avi Wigderson · Journal of the ACM · 2001 · 430 citations
A simplified NP-complete satisfiability problem
Craig A. Tovey · Discrete Applied Mathematics · 1984 · 382 citations
The Complexity of Propositional Proofs
Alasdair Urquhart · Bulletin of Symbolic Logic · 1995 · 225 citations
Lopsided Lovász Local Lemma and Latin transversals
P. Erdös, Joel Spencer · Discrete Applied Mathematics · 1991 · 155 citations