Source : Free On-Line Dictionary of Computing

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)