On the Complexity of Breaking Symmetry
This work addresses a fundamental issue in constraint satisfaction and combinatorial optimization, showing that incremental improvements in ordering methods do not overcome the inherent intractability of symmetry breaking for large symmetry groups.
The paper tackles the problem of breaking symmetry in computational problems by proving that alternative total orderings, such as Gray code or Snake-Lex, do not reduce the computational complexity compared to the lex-leader method, establishing that breaking symmetry remains intractable in general.
We can break symmetry by eliminating solutions within a symmetry class that are not least in the lexicographical ordering. This is often referred to as the lex-leader method. Unfortunately, as symmetry groups can be large, the lexleader method is not tractable in general. We prove that using other total orderings besides the usual lexicographical ordering will not reduce the computational complexity of breaking symmetry in general. It follows that breaking symmetry with other orderings like the Gray code ordering or the Snake-Lex ordering is intractable in general.