# What is the most efficient algorithm for deciding if an element is the least in its orbit?

Given a group $G$ acting on a set $X$ with a total order $\leq$ and an $x\in X$, what is the most efficient algorithm for deciding whether or not x is the least element in its orbit, in other words, deciding if $min(Gx) = x$?

My motivation comes from SMT solving where there has been some interest in automatically breaking symmetries. Adding symmetry breaking predicates often result in a large clause set therefore I am interested in the possibility of handling this as a lazy theory propagation.

The above description is perhaps too general, and as noted by sid, NP-hard. A possible simpler task is, given a group of permutations of strings of length $n$ encoded as a set of generators and a string $x$ of length $n$. What is the most efficient algorithm for deciding if that string is the lexicographically smallest in its orbit?

• I presume you're talking about finite sets X? I think deciding this is NP-hard. Let $X=\{c_1,\dots,c_n\}$ be a tour of a set of cities in the Traveling Salesman problem with $c_1 \rightarrow c_2 \dots$. Let the group $G$ be the symmetric group $S_n$. Then the orbit is all possible tours and proving that one of them is minimum is NP-hard.
– Opt
Dec 8, 2011 at 10:18
• @Sid, yes I am only interested in the case where X is finite, and I hadn't thought of it but it is certainly NP-hard. I guess there might still be a possibility of an efficient monte carlo algorithm. Dec 8, 2011 at 10:46
• Although if you use a different criterion for minimum, it's polynomial here: it's easy to find the lexicographically smallest tour (at least if you assume all the edges have different labels; otherwise, it's still NP-hard). Dec 8, 2011 at 12:14
• @PeterShor, yes, in fact for my purpose, any canonical form will do. Dec 8, 2011 at 12:45
• If $G$ and $X$ are presented as value oracles, this requires enumerating $G$. Dec 8, 2011 at 13:14

For general equivalence relations, not those arising from permutation group actions, even finding lexicographically least is still "too" general. Finding the lexicographically smallest element in an equivalence class can be $NP$-hard (in fact, $P^{NP}$-hard) - even if the relationship has a polynomial-time canonical form [1].

However, for permutation group orbit problems as you describe, deciding whether two points lie in the same orbit is not likely to be $NP$-hard: it is in $NP \cap coAM$, and hence not $NP$-hard unless the polynomial hierarchy collapses to the second level.

A canonical form for graph isomorphism is also a special case of the second problem you state. The best known canonical form for graph isomorphism runs in time $2^{\tilde{O}(\sqrt{n})}$ [2].

Since you said in the comments that any canonical form will do, you might also be interested in my paper with Lance Fortnow [3]: in its currently generality, I think your question is related to our results. We show that if every equivalence relation decidable in $P$ has a canonical form in $P$, then "bad" consequences result, such as $NP = UP = RP$, which in particular implies that the polynomial hierarchy collapses down to $BPP$. On the other hand, the equivalence relations you're interested in may not be in $P$, but this result suggests that even if it lies in a higher complexity class other hard problems may still stand in your way.

So I think if you want some better upper bounds you really need the problem to be more specific.

[1] Andreas Blass and Yuri Gurevich. Equivalence relations, invariants, and normal forms. SIAM J. Comput. 13:4 (1984), 24-42.

[2] László Babai and Eugene M. Luks. Canonical labelings of graphs. STOC 1983, 171-183.

[3] Lance Fortnow and Joshua A. Grochow. Complexity classes of equivalence problems revisited. Inform. and Comput. 209:4 (2011), 748-763. Also available as arXiv:0907.4775v2.

• Does GI in poly time imply $PEq=CF$ in your paper? What would imply such a result (any complete problems) and what would separate? Dec 7, 2015 at 18:54
• Not as far as I know. At best it would imply that any problem of combinatorial isomorphism is in Ker(FP); one issue is that a canonical form for a graph need not yield a canonical form for the structure you started with; the other issue is that combinatorial isomorphism isn't necessarily PEq-complete. We asked whether there were PEq-complete problems; Finkelstein and Hescott showed CEq-complete problems for C higher up in PH, but left open the question of the existence of PEq-complete problem. Dec 7, 2015 at 20:19
• would it be possible that existence of a complete problem in PEq implies PH collapses to some level? Dec 7, 2015 at 20:52
• @Turbo: Sure, though it seems a little unlikely to me. Do you know of any example where the existence of a complete problem for some class implies PH collapses? (Other than PH-complete problems.) I think it's likely that either (a) PEq-complete problems exist (and don't contradict major conjectures), we just haven't figured out how to construct them, or (b) there are oracles going both ways on the existence of PEq-complete problems. (b) seems more likely to me - by analogy with BPP - because PEq is essentially a semantic class. Dec 7, 2015 at 22:55