follow Dictionary.com

Submit your word to be a Word of the Day!

satisfiability problem

satisfiability problem in Technology


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)

The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source

Word of the Day

Word Value for satisfiability

0
0
Scrabble Words With Friends

Nearby words for satisfiability problem