Symmetry Definitions for Constraint Satisfaction Problems
Symmetry Definitions for Constraint Satisfaction Problems
复制标题
约束满足问题的对称性定义
作者：
D. Cohen;P. Jeavons;Christopher Jefferson;K. Petrie;Barbara M. Smith
我们回顾了出现在文献中出现的约束满意度问题（CSP）的对称性的许多不同的定义，并表明可以以两种根本不同的方式定义对称性：作为保留CSP实例解决方案的操作，或者是作为CSP实例的解决方案。保留约束的操作。我们将其称为解决方案对称性和约束对称性。我们更精确地定义了约束对称性，它是与CSP实例相关的超图的自动形态，即微结构补体。我们表明，CSP实例的解决方案对称性也可以作为相关超图，K- ARY Nogood HyperGraph的自动形态获得，并给出示例以表明某些实例比约束对称性具有更多的解决方案对称性。最后，我们讨论了这些对称性不同概念的实际含义。
We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.