  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.
