Borel CSP complexity dichotomy conjecture
Borel CSP complexity dichotomy conjecture
Let be a finite relational structure, and let denote the set of codes for Borel structures admitting Borel homomorphisms into . The projective pointclasses and classify the complexity of such sets.
Borel CSP dichotomy conjecture. For every , the set is either in or is -complete.
The source says that this dichotomy follows assuming -determinacy, but whether it holds in ZFC is open. It is intended as a descriptive-set-theoretic analogue of the finite CSP dichotomy.
Sources & referencesView supporting material
Primary source
Riley Thornton, “An algebraic approach to Borel CSPs”, arXiv:2203.16712 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.