Symmetry Definitions for Constraint Satisfaction Problems

We review the many difierent deflnitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the liter- ature, and show that a symmetry can be deflned in two fundamentally difierent 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 deflne a constraint symmetry more precisely as an automorphism of a hypergraph associ- ated 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 difierent notions of symmetry. The issue of symmetry is now widely recognised as of fundamental importance in constraint satisfaction problems (CSPs). It seems self-evident that in order to deal with symmetry we should flrst agree what we mean by symmetry. Surpris- ingly, this appears not to be true: researchers in this area have deflned symmetry in fundamentally difierent ways, whilst often still identifying the same collection of symmetries in a given problem and dealing with them in the same way. In this paper, we flrst survey the various symmetry deflnitions that have ap- peared in the literature. We show that the existing deflnitions re∞ect two distinct views of symmetry: that symmetry is a property of the solutions, i.e. that any mapping that preserves the solutions is a symmetry; or that symmetry preserves the constraints, and therefore as a consequence also preserves the solutions. We propose two new deflnitions of solution symmetry and constraint symmetry to capture these two distinct views, and show that they are indeed difierent: al- though any constraint symmetry is also a solution symmetry, there can be many