Satisfiability

In mathematics, a formula of propositional logic is said to be satisfiable if truth-values can be assigned to its free variables in a way that makes the formula true. The class of satisfiable formulas of propositional logic is NP-complete, as is that of its variant 3-satisfiability[?].

(There is also such a thing as satisfiability of formulas of first-order and second-order logic.)

Compare with: decision problem

External links

• http://www.intellektik.informatik.tu-darmstadt.de/SATLIB/
• http://www.satlive.org/index.jsp