The Complexity of Symmetry Breaking Beyond Lex-Leader
Symmetry breaking is a widely popular approach to enhance solvers in constraint programming, such as those for SAT or MIP. Symmetry breaking predicates (SBPs) typically impose an order on variables and single out the lexicographic leader (lex-leader) in each orbit of assignments. Although it is NP-hard to find complete lex-leader SBPs, incomplete lex-leader SBPs are widely used in practice. In this paper, we investigate the complexity of computing complete SBPs, lex-leader or otherwise, for SAT. Our main result proves a natural barrier for efficiently computing SBPs: efficient certification of graph non-isomorphism. Our results explain the difficulty of obtaining short SBPs for important CP problems, such as matrix-models with row-column symmetries and graph generation problems. Our results hold even when SBPs are allowed to introduce additional variables. We show polynomial upper bounds for breaking certain symmetry groups, namely automorphism groups of trees and wreath products of groups with efficient SBPs.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph GenerationSimilar Papers 제목 키워드 기반
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 larg…
Breaking Symmetry with Different Orderings
We can break symmetry by eliminating solutions within each symmetry class. For instance, the Lex-Leader method eliminates all but the smallest solution in the lexicographical ordering. Unfortunately, the Lex-Leader metho…
Spontaneous symmetry breaking and pattern formation of organoids
Recent 3D organ reconstitution studies show that a group of stem cells can establish a body axis and acquire different fates in a spatially organized manner. How such symmetry breaking happens in the absence of external …
On Broken Symmetry in Cognition
Cognition is not passive data accumulation but the active resolution of uncertainty through symmetry breaking. This paper argues that both cognitive evolution and development unfold via sequential symmetry-breaking trans…
SpecificityBeyond ICA: Identifiability by Symmetry Breaking
We prove the identifiability of deep generative models (DGMs) with piecewise-affine (PWA) decoders and Gaussian mixture model (GMM) priors, in a purely unsupervised setting. We introduce three algebraic contrast principl…