The Polynomial Hierarchy and $ω$-categorical CSPs
This result provides a complete characterization of the complexity of ω-categorical CSPs within the Polynomial Hierarchy, which is of interest to researchers in computational complexity and constraint satisfaction.
The authors prove that for every level of the Polynomial Hierarchy, there exist ω-categorical Constraint Satisfaction Problems that are complete for that level, extending a 2008 result. They achieve this by leveraging a recent construction from MSO sentences and developing a new tool for generating such sentences.
In 2008, Bodirsky and Grohe showed that for every $Π_n^{\mathrm{P}}$-level of the Polynomial Hierarchy (PH) there are $ω$-categorical Constraint Satisfaction Problems (CSPs) complete for this level. We show that, in fact, there are $ω$-categorical CSPs complete for any level of the PH. To this end, we use a recent result of Bodirsky, Knäuer, and Rudolph for constructing $ω$-categorical CSPs from sentences of Monadic Second-Order logic (MSO) with certain preservation properties. As a secondary contribution, we develop a new tool for producing MSO sentences satisfying said preservation properties.