On the Complexity of Breaking Symmetry
  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.
