An invitation to the promise constraint satisfaction problem

Andrei Krokhin, Jakub Opršal

The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. Afte…