Algebra Seminar talk
2016-06-10
Michael Pinsker
The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
Abstract:
We prove that an $\omega$-categorical core structure primitively
positively interprets all finite structures with parameters if and
only if some stabilizer of its polymorphism clone has a homomorphism
to the clone of projections, and that this happens if and only if its
polymorphism clone does not contain operations $\alpha$, $\beta$, $s$
satisfying the identity $\alpha s(x,y,x,z,y,z) \approx \beta
s(y,x,z,x,z,y)$.
This establishes an algebraic criterion equivalent to the conjectured borderline between P and NP-complete CSPs over reducts of finitely bounded homogenous structures, and accomplishes one of the steps of a proposed strategy for reducing the infinite domain CSP dichotomy conjecture to the finite case.
Our theorem is also of independent mathematical interest, characterizing a topological property of any $\omega$-categorical core structure (the existence of a continuous homomorphism of a stabilizer of its polymorphism clone to the projections) in purely algebraic terms (the failure of an identity as above).