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)