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