Hyper Dictionary

English Dictionary Computer Dictionary Video Dictionary Thesaurus Dream Dictionary Medical Dictionary


Search Dictionary:  

Meaning of SATISFIABILITY PROBLEM

 
Computing Dictionary
 
 Definition: 

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].

 

 

COPYRIGHT © 2000-2013 HYPERDICTIONARY.COM HOME | ABOUT HYPERDICTIONARY