satisfiability problem

Computing Dictionary

satisfiability problem definition

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].

The Free On-line Dictionary of Computing, © Denis Howe 2010
Cite This Source
Previous Definition: satisfactory
Next Definition: satisfiable
More from
Synonyms and Antonyms for satisfiability problem
More from
Search for articles containing satisfiability problem Word FAQs presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Copyright © 2014, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature