ComputingComputer ScienceMathematicsAlgorithmsOptimizationTheory Of ComputationAlgorithmic ComplexityComplexity TheoryComputational ComplexityGraph AlgorithmsProof ComplexitySpace ComplexityBoolean Formula SizeComplexity MeasuresComplexity Of SatisfiabilityFormula ComplexityHeuristicsProof Size Lower BoundsSpace Complexity Of Boolean FormulasSpace Complexity Of Proofs
We investigate tradeoffs of various important complexity measures such as size, space and width. We show examples of CNF formulas that have optimal proofs with respect to any one of these parameters, but optimizing one parameter must cost an increase in the other. These results, the first of their kind, have implications on the efficiency (or rather, inefficiency) of some commonly used SAT solving heuristics.Our proof relies on a novel and somewhat surprising connection of the variable space of a proof, to the black white pebbling measure of an underlying graph.
33
A machine program for theorem-proving
Martin Davis, George Logemann, Donald Loveland · Communications of the ACM · 1962 · 3.2K citations · Full text
A Computing Procedure for Quantification Theory
Martin Davis, Hilary Putnam · Journal of the ACM · 1960 · 2.6K citations · Full text
The intractability of resolution
Armin Haken · Theoretical Computer Science · 1985 · 829 citations
The relative efficiency of propositional proof systems
Stephen Cook, Robert A. Reckhow · Journal of Symbolic Logic · 1979 · 827 citations