Editing Universal algebra (section)

== Motivations and applications ==
{{Unreferenced section|date=April 2010}}

In addition to its unifying approach, universal algebra also gives deep theorems and important examples and counterexamples. It provides a useful framework for those who intend to start the study of new classes of algebras.
It can enable the use of methods invented for some particular classes of algebras to other classes of algebras, by recasting the methods in terms of universal algebra (if possible), and then interpreting these as applied to other classes. It has also provided conceptual clarification; as J.D.H. Smith puts it, ''"What looks messy and complicated in a particular framework may turn out to be simple and obvious in the proper general one."''

In particular, universal algebra can be applied to the study of [[monoid]]s, [[ring (algebra)|rings]], and [[lattice (order)|lattice]]s.  Before universal algebra came along, many theorems (most notably the [[isomorphism theorem]]s) were proved separately in all of these classes, but with universal algebra, they can be proven once and for all for every kind of algebraic system.

The 1956 paper by Higgins referenced below has been well followed up for its framework for a range of particular algebraic systems, while his 1963 paper is notable for its discussion of algebras with operations which are only partially defined, typical examples for this being categories and groupoids. This leads on to the subject of [[higher-dimensional algebra]] which can be defined as the study of algebraic theories with partial operations whose domains are defined under geometric conditions. Notable examples of these are various forms of higher-dimensional categories and groupoids.

=== 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>