from
The Free On-line Dictionary of Computing (8 July 2008)
satisfiability problem
A problem used as an example in {complexity theory}. It can
be stated thus:
Given a Boolean expression E, decide if there is some
assignment to the variables in E such that E is true.
A {Boolean} expression is composed of Boolean variables,
(logical) negation (NOT), (logical) {conjunction} (AND) and
parentheses for grouping. The satisfiability problem was the
first problem to be proved to be {NP-complete} (by Cook).
["Introduction to Automata Theory, Languages, and Computation"
by Hopcroft and Ullman, pub. Addison-Wesley].
(1994-11-11)