Feder–Vardi dichotomy conjecture

Remarks

The conjecture is now a theorem: it follows from the CSP dichotomy theorem, proved independently by Andrei Bulatov and by Dmitriy Zhuk. It is not a consequence of general complexity theory. By Ladner's theorem, if $\mathrm{P} \ne \mathrm{NP}$ then NP contains problems that are neither in P nor NP-complete. Feder and Vardi studied a logically defined fragment of NP called monotone monadic SNP, defined by three syntactic restrictions. They showed that its problems are equivalent to fixed-template CSPs. They also showed that dropping any one of the three restrictions gives a class that contains, up to polynomial-time equivalence, every problem in NP. So, assuming $\mathrm{P} \ne \mathrm{NP}$, a dichotomy can only hold for the restricted class, and CSPs are its natural representatives. Before the proof, the conjecture was known for structures with a two-element domain (Schaefer), for undirected graphs (Hell and Nešetřil), and for three-element domains (Bulatov).