2008 · 44 citations · 17 references
ComputingComputer ScienceAlgorithmsDiscrete MathematicsTheory Of ComputationAlgorithmic ComplexityComplexity TheoryComputational ComplexitySpace ComplexityStructural ComplexityApproximation ComplexityApproximation HardnessCircuit SatisfiabilityComplexity Of SatisfiabilityComplexity-theoretic HardnessHardnessLogarithmic Space ComplexitySpace Complexity Of Boolean Formulas
The search of a precise measure of what hardness of SAT instances means for state-of-the-art solvers is a relevant research question. Among others, the space complexity of treelike resolution (also called hardness), the minimal size of strong backdoors and of cycle-cutsets, and the treewidth can be used for this purpose. We propose the use of the tree-like space complexity as a solid candidate to be the best measure for solvers based on DPLL. To support this thesis we provide a comparison with the other mentioned measures. We also conduct an experimental investigation to show how the proposed measure characterizes the hardness of random and industrial instances.
17
Tree clustering for constraint networks
Rina Dechter, Judea Pearl · Artificial Intelligence · 1989 · 540 citations
Backdoors to typical case complexity
Ryan Williams, Carla P. Gomes, Bart Selman · 2003 · 316 citations