Breaking Value Symmetry

Simple item page
dc.creatorWalsh, Toby
dc.date2009-03-06
dc.date.accessioned2026-07-07T12:49:35Z
dc.date.available2026-07-07T12:49:35Z
dc.descriptionOne common type of symmetry is when values are symmetric. For example, if we are assigning colours (values) to nodes (variables) in a graph colouring problem then we can uniformly interchange the colours throughout a colouring. For a problem with value symmetries, all symmetric solutions can be eliminated in polynomial time. However, as we show here, both static and dynamic methods to deal with symmetry have computational limitations. With static methods, pruning all symmetric values is NP-hard in general. With dynamic methods, we can take exponential time on problems which static methods solve without search.
dc.descriptionPrinciples and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings. Lecture Notes in Computer Science 4741 Springer 2007, ISBN 978-3-540-74969-
dc.identifierhttps://arxiv.org/abs/0903.1146
dc.identifierhttp://arxiv.org/abs/0903.1146
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/222456
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.subjectI.2.4
dc.titleBreaking Value Symmetry
dc.typetext

Files

Collections

arXiv