Editing Boolean satisfiability problem (section)

{{short description|Problem of determining if a Boolean formula could be made true}}
{{Redirect|3SAT|the Central European television network|3sat}}

In [[logic]] and [[computer science]], the '''Boolean satisfiability problem''' (sometimes called '''propositional satisfiability problem''' and abbreviated '''SATISFIABILITY''', '''SAT''' or '''B-SAT''') asks whether there exists an [[Interpretation (logic)|interpretation]] that [[Satisfiability|satisfies]] a given [[Boolean logic|Boolean]] [[Formula (mathematical logic)|formula]]. In other words, it asks whether the formula's variables can be consistently replaced by the values TRUE or FALSE to make the formula evaluate to TRUE. If this is the case, the formula is called ''satisfiable'', else ''unsatisfiable''. For example, the formula "''a'' AND NOT ''b''" is satisfiable because one can find the values ''a'' = TRUE and ''b'' = FALSE, which make (''a'' AND NOT ''b'') = TRUE. In contrast, "''a'' AND NOT ''a''" is unsatisfiable.

SAT is the first problem that was proven to be [[NP-complete]]—this is the [[Cook–Levin theorem]]. This means that all problems in the complexity class [[NP (complexity)|NP]], which includes a wide range of natural decision and optimization problems, are at most as difficult to solve as SAT. There is no known algorithm that efficiently solves each SAT problem (where "efficiently" informally means "deterministically in polynomial time"), and it is generally believed that no such algorithm exists, but this belief has not been proven mathematically, and resolving the question of whether SAT has a [[polynomial-time]] algorithm is equivalent to the [[P versus NP problem]], which is a famous open problem in the theory of computing.

Nevertheless, as of 2007, heuristic SAT-algorithms are able to solve problem instances involving tens of thousands of variables and <!---"clauses" hasn't been introduced here:--->formulas consisting of millions of symbols,<ref name="Codish.Ohrimenko.Stuckey.2007"/> which is sufficient for many practical SAT problems from, e.g., [[artificial intelligence]], [[circuit design]],<ref>{{Cite book|last1=Hong|first1=Ted|last2=Li|first2=Yanjing|last3=Park|first3=Sung-Boem|last4=Mui|first4=Diana|last5=Lin|first5=David|last6=Kaleq|first6=Ziyad Abdel|last7=Hakim|first7=Nagib|last8=Naeimi|first8=Helia|last9=Gardner|first9=Donald S.|last10=Mitra|first10=Subhasish|title=2010 IEEE International Test Conference |chapter=QED: Quick Error Detection tests for effective post-silicon validation |date=November 2010|pages=1–10|doi=10.1109/TEST.2010.5699215|isbn=978-1-4244-7206-2|s2cid=7909084}}</ref> and [[automatic theorem proving]].