Encyclopedia > Satisfiability problem

Article Content

Satisfiability

Redirected from Satisfiability problem

In mathematics, a formula of propositional logic is said to be satisfiable if truth-values can be assigned to its free variables in a way that makes the formula true. The class of satisfiable formulas of propositional logic is NP-complete, as is that of its variant 3-satisfiability[?].

(There is also such a thing as satisfiability of formulas of first-order and second-order logic.)

Compare with: decision problem

External links

http://www.intellektik.informatik.tu-darmstadt.de/SATLIB/
http://www.satlive.org/index.jsp

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia

Search over one million articles, find something about almost anything!

Featured Article

Northampton, Suffolk County, New York

... (22.6/mi²). The racial makeup of the town is 46.37% White, 44.23% African American, 0.85% Native American, 0.85% Asian, 0.00% Pacific Islander, 2.35% from othe ...