The Polynomial Hierarchy and $\omega$-categorical CSPs

Santiago Guzmán Pro, Jakub Rydval

In 2008, Bodirsky and Grohe showed that for every ${\Pi }_n^{\mathrm{P}}$-level of the Polynomial Hierarchy (PH) there are $\omega$-categorical Constraint Satisfaction Problems (CSPs) comple…