Vardi, and finally proven independently by Andrei Bulatov and Dmitriy Zhuk in 2017.

Other classes for which a complexity dichotomy has been confirmed are

* all first-order reducts of ,
* all first-order reducts of the countable random graph,
* all first-order reducts of the model companion of the class of all C-relations,
* all first-order reducts of the universal