Constraint Satisfaction Problem (CSP) is the problem of deciding whether there exists an assignment to a set of variables subject to some specified constraints. Surjective Constraint Satisfaction Problem (SCSP) is the variant of CSP where we require the solution to be surjective, that is all values from the domain appear in the solution. Unlike the CSP, where the complexity was classified for all constraint languages, the complexity of the SCSP remains unknown even for very simple constraint languages. One of the most pop- ular constraint languages with unknown complexity consists of the relation \(\{(a,b,c) \mid \{a,b,c\} \neq \{0,1,2\}\}\) on a three-element domain \(\{0,1,2\}\), and the corresponding problem is called No-Rainbow Problem.
In the talk we prove that No-Rainbow Problem is NP-hard. Additionally, we show that the complexity of the SCSP cannot be described in terms of polymorphisms and disprove a widely-believed conjecture describing the complexity of the SCSP for all constraint languages.