The power of polymorphisms: the triangle of universal algebra, model theory, and theoretical computer science - Part 1
ABSTRACT. I am going to survey tight connections between universal algebra, model theory, and theoretical computer science (specifically, constraint satisfaction) established in the past 25 years, and try to provide the audience with an intuition for them. At the center of this tutorial will be the notion of a polymorphism.
A polymorphism of a relational structure A is a multivariate function on the structure leaving all relations of A invariant. It is a generalization of an endomorphism, which is a unary function under which A is invariant, or of an automorphism, which is a unary function under which A is (strongly) invariant.
Similarly to the automorphism group or the endomorphism monoid of A, the set of all polymorphisms of A, called the polymorphism clone Pol(A) of A, provides us with structural information about A, in particular which other structures A can define, interpret, or construct (in a certain precise way). Since the polymorphism clone Pol(A) consists of multivariate functions on the same domain A, it can be viewed as an algebra, just like the set of automorphisms can be viewed as a group. Therefore, algebraic methods can be used to investigate the polymorphism clone Pol(A), and hence derive information about the original structure A. This is the link between model theory and universal algebra.
Every relational structure A defines a computational problem, the Constraint Satisfaction Problem CSP(A), where given a list of variables and atomic statements (called constraints) about these variables in the language of A one has to find a solution, i.e., a map from the variables into A such that all atomic statements are satisfied. This kind of computational problem is extremely general: every computational problem is polynomial-time (Turing) equivalent to CSP(A) for a suitable structure A. Since the polymorphisms of A leave the set of solutions of any instance of CSP(A) invariant, they are central in the study of the computational complexity of CSP(A): in fact, the computational complexity of CSP(A), certain model-theoretic properties of A, and the algebraic structure of the polymorphism clone Pol(A) are tightly connected, with nontrivial implications holding in all directions of this triangle.
The power of polymorphisms: the triangle of universal algebra, model theory, and theoretical computer science - Part 2
ABSTRACT. I am going to survey tight connections between universal algebra, model theory, and theoretical computer science (specifically, constraint satisfaction) established in the past 25 years, and try to provide the audience with an intuition for them. At the center of this tutorial will be the notion of a polymorphism.
A polymorphism of a relational structure A is a multivariate function on the structure leaving all relations of A invariant. It is a generalization of an endomorphism, which is a unary function under which A is invariant, or of an automorphism, which is a unary function under which A is (strongly) invariant.
Similarly to the automorphism group or the endomorphism monoid of A, the set of all polymorphisms of A, called the polymorphism clone Pol(A) of A, provides us with structural information about A, in particular which other structures A can define, interpret, or construct (in a certain precise way). Since the polymorphism clone Pol(A) consists of multivariate functions on the same domain A, it can be viewed as an algebra, just like the set of automorphisms can be viewed as a group. Therefore, algebraic methods can be used to investigate the polymorphism clone Pol(A), and hence derive information about the original structure A. This is the link between model theory and universal algebra.
Every relational structure A defines a computational problem, the Constraint Satisfaction Problem CSP(A), where given a list of variables and atomic statements (called constraints) about these variables in the language of A one has to find a solution, i.e., a map from the variables into A such that all atomic statements are satisfied. This kind of computational problem is extremely general: every computational problem is polynomial-time (Turing) equivalent to CSP(A) for a suitable structure A. Since the polymorphisms of A leave the set of solutions of any instance of CSP(A) invariant, they are central in the study of the computational complexity of CSP(A): in fact, the computational complexity of CSP(A), certain model-theoretic properties of A, and the algebraic structure of the polymorphism clone Pol(A) are tightly connected, with nontrivial implications holding in all directions of this triangle.
