Editing Universal algebra (section)

=== Constraint satisfaction problem ===
{{Main|Constraint satisfaction problem}}

Universal algebra provides a natural language for the [[constraint satisfaction problem|constraint satisfaction problem (CSP)]]. CSP refers to an important class of computational problems where, given a relational algebra ''A'' and an existential [[sentence (mathematical logic)|sentence]] <math>\varphi</math> over this algebra, the question is to find out whether <math>\varphi</math> can be satisfied in ''A''. The algebra ''A'' is often fixed, so that CSP<sub>''A''</sub> refers to the problem whose instance is only the existential sentence <math>\varphi</math>.

It is proved that every computational problem can be formulated as CSP<sub>''A''</sub> for some algebra ''A''.<ref>{{Citation|last1=Bodirsky|first1=Manuel|last2=Grohe|first2=Martin|date=2008|title=Non-dichotomies in constraint satisfaction complexity|url=http://www.lix.polytechnique.fr/~bodirsky/publications/nodich.pdf}}</ref>

For example, the [[graph coloring|''n''-coloring]] problem can be stated as CSP of the algebra {{nowrap|({{mset|0, 1, ..., ''n''−1}}, ≠)}}, i.e. an algebra with ''n'' elements and a single relation, inequality.

The dichotomy conjecture (proved in April 2017) states that if ''A'' is a finite algebra, then CSP<sub>''A''</sub> is either [[P (complexity)|P]] or [[NP-completeness|NP-complete]].<ref>{{cite arXiv | last = Zhuk | first = Dmitriy | title = The Proof of CSP Dichotomy Conjecture | eprint = 1704.01914 | date = 2017 | class = cs.cc}}</ref>