SIAM Journal on Computing · 1998 · 47 citations · 15 references
ComputingComputer ScienceMathematicsAlgorithmsLogicTheory Of ComputationBoolean AlgebraBoolean OperationsCircuit ComplexityLogic ProgrammingTruth ConditionsBoolean ExpressionsBoolean SatisfiabilityBoolean Satisfiability ProblemComplexity Of SatisfiabilityConjunctive Normal FormPolynomial Time ComplexityPolynomial-time AlgorithmsSatisfiability
We study the complexity of telling whether a set of bit-vectors represents the set of all satisfying truth assignments of a Boolean expression of a certain type. We show that the problem is coNP-complete when the expression is required to be in conjunctive normal form with three literals per clause (3CNF). We also prove a dichotomy theorem analogous to the classical one by Schaefer, stating that, unless P=NP, the problem can be solved in polynomial time if and only if the clauses allowed are all Horn, or all anti-Horn, or all 2CNF, or all equivalent to equations modulo two.
15
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
Raymond Reiter · Artificial Intelligence · 1980 · 3.9K citations
Circumscription—A form of non-monotonic reasoning
John McCarthy · Artificial Intelligence · 1980 · 2K citations
The complexity of satisfiability problems
Thomas J. Schaefer · 1978 · 1.8K citations · Full text