Editing Boolean satisfiability problem (section)

==Extensions of SAT==
An extension that has gained significant popularity since 2003 is '''[[satisfiability modulo theories]]''' ('''SMT''') that can enrich CNF formulas with linear constraints, arrays, all-different constraints, [[uninterpreted function]]s,<ref name="Bryant.German.Velev.1999">R. E. Bryant, S. M. German, and M. N. Velev, [http://portal.acm.org/citation.cfm?id=709275 Microprocessor Verification Using Efficient Decision Procedures for a Logic of Equality with Uninterpreted Functions], in Analytic Tableaux and Related Methods, pp.&nbsp;1–13, 1999.</ref> etc. Such extensions typically remain NP-complete, but very efficient solvers are now available that can handle many such kinds of constraints.

The satisfiability problem becomes more difficult if both "for all" ([[∀]]) and "there exists" ([[∃]]) [[Quantifier (logic)|quantifier]]s are allowed to bind the Boolean variables. An example of such an expression would be {{math|size=100%|∀''x'' ∀''y'' ∃''z'' (''x'' ∨ ''y'' ∨ ''z'') ∧ (¬''x'' ∨ ¬''y'' ∨ ¬''z'')}}; it is valid, since for all values of ''x'' and ''y'', an appropriate value of ''z'' can be found, viz. ''z''=TRUE if both ''x'' and ''y'' are FALSE, and ''z''=FALSE else. SAT itself (tacitly) uses only ∃ quantifiers. If only ∀ quantifiers are allowed instead, the so-called '''[[Tautology (logic)|tautology]] problem''' is obtained, which is [[co-NP-complete]]. If any number of both quantifiers are allowed, the problem is called the '''[[quantified Boolean formula problem]]''' ('''QBF'''), which can be shown to be [[PSPACE-complete]]. It is widely believed that PSPACE-complete problems are strictly harder than any problem in NP, although this has not yet been proved. Using highly parallel ''[[P system]]s'', QBF-SAT problems can be solved in linear time.<ref>{{Cite journal | last1 = Alhazov | first1 = Artiom | last2 = Martín-Vide | first2 = Carlos | last3 = Pan | first3 = Linqiang | title = Solving a PSPACE-Complete Problem by Recognizing P Systems with Restricted Active Membranes |  url=https://www.researchgate.net/publication/220444503 | journal = Fundamenta Informaticae | volume = 58 | pages = 67–77 | year = 2003 }} Here: Sect.3, Thm.3.1</ref>

Ordinary SAT asks if there is at least one variable assignment that makes the formula true. A variety of variants deal with the number of such assignments:
* '''MAJ-SAT''' asks if at least half of all assignments make the formula TRUE. It is known to be complete for [[PP (complexity)|PP]], a probabilistic class. Surprisingly, '''MAJ-kSAT''' is demonstrated to be in P for every finite integer k.<ref>{{Cite book |title=MAJORITY-3SAT (and Related Problems) in Polynomial Time |url=https://ieeexplore.ieee.org/document/9719756 |archive-url=http://web.archive.org/web/20241005152907/https://ieeexplore.ieee.org/document/9719756/ |archive-date=2024-10-05 |access-date=2024-12-25 |date=2022 |doi=10.1109/FOCS52979.2021.00103 |arxiv=2107.02748 |language=en-US |last1=Akmal |first1=Shyan |last2=Williams |first2=Ryan |pages=1033–1043 |isbn=978-1-6654-2055-6 }}</ref>
* '''[[Sharp-SAT|#SAT]]''', the problem of counting how many variable assignments satisfy a formula, is a counting problem, not a decision problem, and is [[Sharp-P-complete|#P-complete]].
* '''UNIQUE SAT'''<ref>{{Cite journal|last1=Blass|first1=Andreas|last2=Gurevich|first2=Yuri|date=1982-10-01|title=On the unique satisfiability problem|journal=Information and Control|volume=55|issue=1|pages=80–88|doi=10.1016/S0019-9958(82)90439-9|issn=0019-9958|doi-access=free|hdl=2027.42/23842|hdl-access=free}}</ref> is the problem of determining whether a formula has exactly one assignment. It is complete for [[US (complexity)|US]],<ref>{{Cite web|url=https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#US|title=Complexity Zoo:U - Complexity Zoo|website=complexityzoo.uwaterloo.ca|access-date=2019-12-05|archive-date=2019-07-09|archive-url=https://web.archive.org/web/20190709142353/https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#US|url-status=dead}}</ref> the [[complexity class]] describing problems solvable by a non-deterministic polynomial time [[Turing machine]] that accepts when there is exactly one nondeterministic accepting path and rejects otherwise.
*'''UNAMBIGUOUS-SAT''' is the name given to the satisfiability problem when the input is [[Promise problem|restricted]] to formulas having at most one satisfying assignment. The problem is also called '''USAT'''.<ref>{{Cite book |chapter-url=https://www.springer.com/gp/book/9781846282973 |chapter=Supplementary Lecture F: Unique Satisfiability |title=Theory of Computation |last=Kozen |first=Dexter C. |date=2006 |publisher=Springer  |isbn=9781846282973 |series=Texts in Computer Science |page=180 |language=en}}</ref> A solving algorithm for UNAMBIGUOUS-SAT is allowed to exhibit any behavior, including endless looping, on a formula having several satisfying assignments. Although this problem seems easier, Valiant and Vazirani have [[Valiant–Vazirani theorem|shown]]<ref>{{Cite journal | last1 = Valiant | first1 = L. | last2 = Vazirani | first2 = V.| doi = 10.1016/0304-3975(86)90135-0 | title = NP is as easy as detecting unique solutions | url = http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf| journal = Theoretical Computer Science | volume = 47 | pages = 85–93 | year = 1986 | doi-access = free }}</ref> that if there is a practical (i.e. [[Bounded-error probabilistic polynomial|randomized polynomial-time]]) algorithm to solve it, then all problems in [[NP (complexity class)|NP]] can be solved just as easily.
* '''MAX-SAT''', the [[maximum satisfiability problem]], is an [[FNP (complexity)|FNP]] generalization of SAT. It asks for the maximum number of clauses which can be satisfied by any assignment. It has efficient [[approximation algorithm]]s, but is NP-hard to solve exactly. Worse still, it is [[APX]]-complete, meaning there is no [[polynomial-time approximation scheme]] (PTAS) for this problem unless P=NP.
*'''WMSAT''' is the problem of finding an assignment of minimum weight that satisfy a monotone Boolean formula (i.e. a formula without any negation). Weights of propositional variables are given in the input of the problem. The weight of an assignment is the sum of weights of true variables. That problem is NP-complete (see Th. 1 of <ref>{{Cite book|last1=Buldas|first1=Ahto|last2=Lenin|first2=Aleksandr|last3=Willemson|first3=Jan|last4=Charnamord|first4=Anton|title=Advances in Information and Computer Security |chapter=Simple Infeasibility Certificates for Attack Trees |date=2017|editor-last=Obana|editor-first=Satoshi|editor2-last=Chida|editor2-first=Koji|volume=10418|series=Lecture Notes in Computer Science|language=en|publisher=Springer International Publishing|pages=39–55|doi=10.1007/978-3-319-64200-0_3|isbn=9783319642000}}</ref>).

Other generalizations include satisfiability for [[first-order predicate calculus|first]]- and [[second-order logic]], [[constraint satisfaction problem]]s, [[0-1 integer programming]].