All or nothing: toward a promise problem dichotomy for constraint problems

Lucy Ham, Marcel Jackson

A finite constraint language $\mathcal{R}$ is a finite set of relations over some finite domain $A$. We show that intractability of the constraint satisfaction problem $\operatorna…