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)