satisfiability problem

1 definition found

satisfiability problem - Free On-line Dictionary of Computing (26 May 2007) :

  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)