论文标题
关于破坏对称性的复杂性
On the Complexity of Breaking Symmetry
论文作者
论文摘要
我们可以通过消除词典顺序中的对称类别中的解决方案来打破对称性。这通常称为Lex-Leader方法。不幸的是，由于对称组可能很大，因此lexleader方法通常是无法处理的。我们证明，除了通常的词典顺序外，使用其他总顺序不会降低打破对称性的计算复杂性。因此，一般而言，与其他订单（如灰色代码订购或蛇序列的订购）的打破对称性通常是棘手的。
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.
