Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well-known problems can be cast as promise CSPs including approximate graph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, the tractability of promise CSPs can be tied to the structure of operations on the solution space called polymorphisms, though in the promise world these operations are much less constrained. Under the thesis that non-trivial polymorphisms govern tractability, promise CSPs therefore provide a fertile ground for the discovery of novel algorithms. In previous work, we classified Boolean promise CSPs when the constraint predicates are symmetric. In this work, we vastly generalize these algorithmic results. Specifically, we show that promise CSPs that admit a family of "regional-periodic" polymorphisms are in P, assuming that determining which region a point i 查看全文>>