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].
| < Previous Terms | Terms Containing satisfiability problem | Next Terms > |
| SASL-YACC SAS System SATAN Sather Sather-K | NP-complete satisfiability problem | Saturday-night special SAVE save say sb |
