一句话：证明 No-Rainbow Problem 是 NP 难的，并推翻 SCSP 与带常量 CSP 复杂度等价的猜想。
本文研究满射约束满足问题（SCSP）：判定在给定约束下是否存在包含域中所有元素的满射赋值。论文证明其中最著名的 No-Rainbow Problem 是 NP 难。此外，作者通过反例否定了一个猜想：同一约束语言 Γ 上的 SCSP 与带常量的 CSP 在多项式时间归约下具有相同计算复杂度。该反例还表明，SCSP 的复杂度不能仅由约束语言的多态（polymorphisms）刻画。
The Surjective Constraint Satisfaction Problem (SCSP) is the problem of deciding whether there exists a surjective assignment to a set of variables subject to some specified constraints, where a surjective assignment is an assignment containing all elements of the domain. In this paper we show that the most famous SCSP, called No-Rainbow Problem, is NP-Hard. Additionally, we disprove the conjecture saying that the SCSP over a constraint language Γ and the CSP over the same language with constants have the same computational complexity up to poly-time reductions. Our counter-example also shows that the complexity of the SCSP cannot be described in terms of polymorphisms of the constraint language.