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)
Nearby terms:
SATAN « Sather « Sather-K « satisfiability
problem » Saturday-night special » SAVE » save
|
