# The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems

arXiv: https://arxiv.org/abs/1602.04353 · HTML: https://mlsanity.com/paper/1602.04353/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2016.

## Built on by (most cited first, 1 of 1)

- [Computational Short Cuts in Infinite Domain Constraint Satisfaction](https://mlsanity.com/paper/2211.10144/) (2022)

## Abstract (arXiv)

We prove that an ω-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 α, β, s satisfying the identity α s(x,y,x,z,y,z) ≈ β 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 ω-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).