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)