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].
(1994-11-11)

The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Explore Dictionary.com
Previous Definition: satisfactory
Next Definition: satisfiable
More from Thesaurus.com
Synonyms and Antonyms for satisfiability problem
More from Reference.com
Search for articles containing satisfiability problem
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

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