An algebraic approach to Borel CSPs

2022/03/30 by Riley Thornton, Thornton, Riley
Mathematics · #03E15 (primary) 08A70 (secondary) #FOS: Mathematics #Logic (math.LO) #math.LO #msc:03E15 #msc:08A70

paper · pdf · doi:10.48550/arxiv.2203.16712

arxiv created 2022/03/30 · arxiv updated 2022/04/01

Abstract

We adapt tools from the algebraic approach to constraint satisfaction problems to answer descriptive set theoretic questions about Borel CSPs. We show that if a structure \mathcal D does not have a Taylor polymorphism, then the corresponding Borel CSP is \mathbfΣ¹₂-complete. In particular, by the CSP Dichotomy Theorem, if CSP(\mathcal D) is NP-complete, then the Borel version, csp_B(\mathcal D), is \mathbfΣ¹₂-complete (assuming P\not=NP). We also have partial converses, such as a descriptive analogue of the Hell--Ne\v set\v ril theorem characterizing \mathbfΣ¹₂-complete graph homomorphism problems. We show that the structures where every solvable Borel instance of their CSP has a Borel solution are exactly the width 1 structures. And, we prove a handful of results bounding the projective complexity of certain bounded width structures.

Related

• Proof complexity of CSP
• Asking the metaquestions in constraint tractability
• Proof complexity of universal algebra in a CSP dichotomy proof
• Complexity and polymorphisms for digraph constraint problems under some basic constructions
• A Proof of the CSP Dichotomy Conjecture