Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
This work provides a theoretical foundation for understanding and comparing algorithmic hierarchies in CSPs, which is incremental but important for researchers in computational complexity and constraint programming.
The paper tackles the problem of characterizing the power of higher-level algorithms for constraint satisfaction problems (CSPs) by developing a unified framework based on polymorphism minions, and introduces a new SDP-like vector relaxation that solves specific CSPs like the dihedral group D4 and linear equations modulo p^2.
We develop a unified framework to characterize the power of higher-level algorithms for the constraint satisfaction problem (CSP), such as $k$-consistency, the Sherali-Adams LP hierarchy, and the affine IP hierarchy. As a result, solvability of a fixed-template CSP or, more generally, a Promise CSP by a given level is shown to depend only on the polymorphism minion of the template. Similarly, we obtain a minion-theoretic description of $k$-consistency reductions between Promise CSPs. We introduce a new hierarchy of SDP-like vector relaxations with vectors over $\mathbb Z_{p}$ in which orthogonality is imposed on $k$-tuples of vectors. Surprisingly, this relaxation turns out to be equivalent to the $k$-th level of the AIP-$\mathbb{Z}_p$ relaxation. We show that it solves the CSP of the dihedral group $\mathbf{D}_4$, the smallest CSP that fools the singleton BLP+AIP algorithm. Using this vector representation, we further show that the $p$-th level of the $\mathbb{Z}_p$ relaxation solves linear equations modulo $p^2$.