Scribd
Upload
19 views1 page

Understanding the SAT Problem

The SAT (boolean SATisfiability problem) is a problem used in complexity theory to determine if there is an assignment of true/false values to variables in a Boolean expression E that makes E true. A Boolean expression contains variables, negation, conjunction, and parentheses, and the satisfiability problem was proven to be NP-complete, meaning it belongs to a class of problems that are hard to solve.

Uploaded by

Rima Mkh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
19 views1 page

Understanding the SAT Problem

The SAT (boolean SATisfiability problem) is a problem used in complexity theory to determine if there is an assignment of true/false values to variables in a Boolean expression E that makes E true. A Boolean expression contains variables, negation, conjunction, and parentheses, and the satisfiability problem was proven to be NP-complete, meaning it belongs to a class of problems that are hard to solve.

Uploaded by

Rima Mkh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

SAT (boolean SATisfiability problem)

satisfiability problem
[Link]
(redirected from Boolean satisfiability problem)
Also found in: Acronyms, Wikipedia.

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].
This article is provided by FOLDOC - Free Online Dictionary of Computing ([Link])

You might also like