论文标题
代数的全球小工具，用于溢出约束满意度
Algebraic Global Gadgetry for Surjective Constraint Satisfaction
论文作者
论文摘要
有限关系结构B上的约束满意度问题（CSP）是决定，考虑到对b的关系的一系列约束，是否对满足所有约束的变量有分配；滤波的CSP是一个变体，其中一个人决定存在于B宇宙中的过滤式分配的过滤性分配。 我们提出了一个代数框架，以证明溢流性CSP的硬度结果；本质上，该框架计算全局小工具，该框架允许人们将经典CSP的减少为圆形CSP。我们展示了如何在此框架中推导过多的CSP的许多硬度结果，包括断开连接的剪切问题的硬度，无rainbow 3色问题的硬度以及所有已知棘手的2个元素结构上的过多的CSP（在这种情况下）。因此，我们的框架使我们能够统一这些硬度结果，并揭示它们之间的共同结构。我们认为，与原始问题相比，我们对断开的切割问题的硬度证明更为简洁。在我们看来，该框架还使非常透明的方式可以将经典的CSP降低为CSPS。
The constraint satisfaction problem (CSP) on a finite relational structure B is to decide, given a set of constraints on variables where the relations come from B, whether or not there is a assignment to the variables satisfying all of the constraints; the surjective CSP is the variant where one decides the existence of a surjective satisfying assignment onto the universe of B. We present an algebraic framework for proving hardness results on surjective CSPs; essentially, this framework computes global gadgetry that permits one to present a reduction from a classical CSP to a surjective CSP. We show how to derive a number of hardness results for surjective CSP in this framework, including the hardness of the disconnected cut problem, of the no-rainbow 3-coloring problem, and of the surjective CSP on all 2-element structures known to be intractable (in this setting). Our framework thus allows us to unify these hardness results, and reveal common structure among them; we believe that our hardness proof for the disconnected cut problem is more succinct than the original. In our view, the framework also makes very transparent a way in which classical CSPs can be reduced to surjective CSPs.
