2016/02/13 by Libor Barto, Barto, Libor, Michael Pinsker +1 · 2 citations
Computer Science · Mathematics · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #cs.CC #cs.LO #math.LO
paper · pdf · doi:10.48550/arxiv.1602.04353
15 pages
arxiv created 2016/02/13 · arxiv updated 2016/02/16
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).