论文标题
约束满意度问题的敏感实例
Sensitive instances of the Constraint Satisfaction Problem
论文作者
论文摘要
我们研究了修改约束满意度问题（CSP）实例的约束关系的影响，并使用固定的模板，对实例解决方案集。更确切地说，我们研究敏感的实例：CSP的实例称为敏感，如果从任何约束关系中取出任何元组会使实例的某些解决方案无效。同等地，一个人可能要求其任何一个约束的每个元组扩展到实例的解决方案。 显然，任何非平凡的模板都具有不敏感的实例。因此，我们遵循Feder和Vardi（Sicomp 1999）提出的方向（在严格宽度的背景下），并要求只有局部一致性检查算法产生的实例才敏感。在CSP的代数方法的语言中，我们表明，有限的dempotent代数$ \ mathbf {a} $具有$ k+2 $可变接近一致术语操作，并且仅当在运行$（k，k，k，k，k+1）$的情况下，在$ \ mathbf iS的实例上均具有$（k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，k，1）的一致性。 我们的结果的一个版本，没有势力，但具有多种代数的灵敏度条件，解决了G. Bergman提出的关于代数的预测系统提出的问题，这些问题是由代数有限产物的某些子代数产生的。 我们的结果适用于无限（尽管在$ \ mathbf {a} $ idempotent）代数中也具有，并且与Feder和Vardi提出的严格宽度$ K $条件表现出令人惊讶的相似性。这两种情况都可以表征近乎一致的操作，但操作的敏锐度却不同。
We investigate the impact of modifying the constraining relations of a Constraint Satisfaction Problem (CSP) instance, with a fixed template, on the set of solutions of the instance. More precisely we investigate sensitive instances: an instance of the CSP is called sensitive, if removing any tuple from any constraining relation invalidates some solution of the instance. Equivalently, one could require that every tuple from any one of its constraints extends to a solution of the instance. Clearly, any non-trivial template has instances which are not sensitive. Therefore we follow the direction proposed (in the context of strict width) by Feder and Vardi (SICOMP 1999) and require that only the instances produced by a local consistency checking algorithm are sensitive. In the language of the algebraic approach to the CSP we show that a finite idempotent algebra $\mathbf{A}$ has a $k+2$ variable near unanimity term operation if and only if any instance that results from running the $(k, k+1)$-consistency algorithm on an instance over $\mathbf{A}^2$ is sensitive. A version of our result, without idempotency but with the sensitivity condition holding in a variety of algebras, settles a question posed by G. Bergman about systems of projections of algebras that arise from some subalgebra of a finite product of algebras. Our results hold for infinite (albeit in the case of $\mathbf{A}$ idempotent) algebras as well and exhibit a surprising similarity to the strict width $k$ condition proposed by Feder and Vardi. Both conditions can be characterized by the existence of a near unanimity operation, but the arities of the operations differ by 1.
