Constraint Symmetry and Solution Symmetry

David Cohen, Peter Jeavons, Christopher Jefferson, Karen E. Petrie, Barbara M. Smith

Symmetry in constraint satisfaction problems (CSPs) has been considered in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or as an operation preserving the constraints. To reflect these two views, we define solution symmetry and constraint symmetry. We discuss how these concepts are related and show that some CSP instances have many more solution symmetries than constraint symmetries.

Subjects: 15.2 Constraint Satisfaction; 9.3 Mathematical Foundations

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.