论文标题
无林弓问题和溢流性约束满意度问题
No-Rainbow Problem and the Surjective Constraint Satisfaction Problem
论文作者
论文摘要
汇总约束满意度问题（SCSP）是确定是否存在符合某些指定约束的一组变量的分配分配的问题，在该变量中，汇总分配是包含域的所有元素的分配。在本文中，我们表明，最著名的SCSP（无rainbow问题）是NP-HARD。此外，我们反驳了猜想，即用约束语言上的SCSP $γ$和与常数相同的语言上的CSP具有相同的计算复杂性，直到降低poly时。我们的反示例还表明，无法用约束语言的多态性来描述SCSP的复杂性。
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.
