Feder–Vardi bounded-width conjecture for CSPs

A constraint satisfaction problem (CSP) is a computational problem of deciding whether a finite set of variables can be assigned values from a finite domain so that all specified constraints are satisfied. A CSP has the ability to count when it admits the obstruction described by Feder and Vardi using ternary and unary relations. Feder–Vardi bounded-width conjecture. Any CSP which cannot simulate a CSP with the ability to count does have bounded width. This conjecture was proved correct, as stated in the surrounding text; the result also holds when one only excludes simulation of affine CSPs.