Search in: Word
Vietnamese keyboard: Off
Virtual keyboard: Show
Computing (FOLDOC) dictionary
satisfiability problem
Jump to user comments
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).