# On the Complexity of Breaking Symmetry

arXiv: https://arxiv.org/abs/2005.08954 · HTML: https://mlsanity.com/paper/2005.08954/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2020.

## Built on by (most cited first, 1 of 1)

- [The Complexity of Symmetry Breaking Beyond Lex-Leader](https://mlsanity.com/paper/2407.04419/) (2024)

## Abstract (arXiv)

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.