Matched Formulas and Backdoor Sets1
Stefan Szeider · Journal on Satisfiability Boolean Modeling and Computation · 2008
We demonstrate hardness results for the detection of small backdoor sets with respect to base classes M r of CNF formulas with maximum deficiency ⩽ r (M 0 is the class of matched formulas). One of the results applies also to a wide range of base clas