Added to Favorites

Computing Dictionary

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)

Explore Dictionary.com

More from Thesaurus.com

Synonyms and Antonyms for satisfiability problem

More from Reference.com

Search for articles containing satisfiability problem

More from Dictionary.com Translator

Translate satisfiability problem into French

Translate satisfiability problem into German

Translate satisfiability problem into Italian

Dictionary.com Word FAQs

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

Nearby Words

Copyright © 2014 Dictionary.com, LLC. All rights reserved.