<p>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].</p>

<p>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.</p>

<p>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].</p>

<p>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. </p>

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

<p>[1] Andreas Blass and Yuri Gurevich. <a href="http://dx.doi.org/10.1137/0213042">Equivalence relations, invariants, and normal forms</a>. SIAM J. Comput. 13:4 (1984), 24-42.</p>

<p>[2] László Babai and Eugene M. Luks. <a href="http://dx.doi.org/10.1145/800061.808746">Canonical labelings of graphs</a>. STOC 1983, 171-183.</p>

<p>[3] Lance Fortnow and Joshua A. Grochow. <a href="http://dx.doi.org/10.1016/j.ic.2011.01.006">Complexity classes of equivalence problems revisited</a>. Inform. and Comput. 209:4 (2011), 748-763. Also available as <a href="http://arxiv.org/abs/0907.4775v2">arXiv:0907.4775v2</a>.</p>

CC BY-SA 3.0
2015-12-07T18:54:15.613Z
Does GI in poly time imply $PEq=CF$ in your paper? What would imply such a result (any complete problems) and what would separate?
Turbo
CC BY-SA 3.0
2015-12-07T20:19:46.250Z
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](http://www.cs.bu.edu/techreports/2011-028-poly-kernel-reductions.ps.Z) showed CEq-complete problems for C higher up in PH, but left open the question of the existence of PEq-complete problem.
Joshua Grochow
CC BY-SA 3.0
2015-12-07T20:52:06.317Z
would it be possible that existence of a complete problem in PEq implies PH collapses to some level?
Turbo
CC BY-SA 3.0
2015-12-07T22:55:42.187Z
@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.
Joshua Grochow
CC BY-SA 3.0
2011-12-10T17:56:30.860Z
2011-12-10T17:56:30.860Z
Joshua Grochow
<p>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$?</p>

<p>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.</p>

<p>The above description is perhaps too general, and as noted by <a href="https://cstheory.stackexchange.com/users/24/sid">sid</a>, 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?</p>

CC BY-SA 3.0
2011-12-08T10:18:17.907Z
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
CC BY-SA 3.0
2011-12-08T10:46:12.220Z
@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.
HaskellElephant
CC BY-SA 3.0
2011-12-08T12:14:16.880Z
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).
Peter Shor 
CC BY-SA 3.0
2011-12-08T12:45:33.603Z
@PeterShor, yes, in fact for my purpose, any canonical form will do.
HaskellElephant
CC BY-SA 3.0
2011-12-08T13:14:11.893Z
If $G$ and $X$ are presented as value oracles, this requires enumerating $G$.
David Harris
CC BY-SA 3.0
2011-12-10T20:01:46.817Z
@HaskellElephant: if you're interested in practical algorithms, maybe you can use techniques from Brendan McKay's program nauty (http://cs.anu.edu.au/~bdm/nauty/), which is widely cited as the best current graph isomorphism solver in practice, though it is known to have exponential worst-case complexity.
Joshua Grochow
CC BY-SA 3.0
2011-12-12T12:06:39.563Z
Define "Given a group G..."!  What, precisely, are we "given"? An explicit multiplication table?  A multiplication oracle?  A generator-relator presentation?  A matrix representation?  May/must the group be finite?  Discrete?
Jeffε
CC BY-SA 3.0
2011-12-12T14:07:25.453Z
@JɛﬀE , the specific case that I am interested is the second description I give, the first description is just a more general case, any encoding that is interesting is fine. And yes, I am only interested in finite groups.
HaskellElephant
<ds.algorithms><gr.group-theory>
What is the most efficient algorithm for deciding if an element is the least in its orbit?
HaskellElephant
# What is the most efficient algorithm for deciding if an element is the least in its orbit?

(Asked by: username_0 on 2011-12-08)

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](https://cstheory.stackexchange.com/users/24/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?

**Tags:** ds.algorithms, gr.group-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: 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).  
> **username_0**: @PeterShor, yes, in fact for my purpose, any canonical form will do.  
> **username_3**: If $G$ and $X$ are presented as value oracles, this requires enumerating $G$.  
> **username_4**: @username_0: if you're interested in practical algorithms, maybe you can use techniques from Brendan McKay's program nauty (http://cs.anu.edu.au/~bdm/nauty/), which is widely cited as the best current graph isomorphism solver in practice, though it is known to have exponential worst-case complexity.  
> **username_5**: Define "Given a group G..."!  What, precisely, are we "given"? An explicit multiplication table?  A multiplication oracle?  A generator-relator presentation?  A matrix representation?  May/must the group be finite?  Discrete?  
> **username_0**: @JɛﬀE , the specific case that I am interested is the second description I give, the first description is just a more general case, any encoding that is interesting is fine. And yes, I am only interested in finite groups.  

---

## 1 answers

### Answer by username_4 on 2011-12-10. Score: 9 | Accepted answer

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](http://dx.doi.org/10.1137/0213042). SIAM J. Comput. 13:4 (1984), 24-42.

[2] László Babai and Eugene M. Luks. [Canonical labelings of graphs](http://dx.doi.org/10.1145/800061.808746). STOC 1983, 171-183.

[3] Lance Fortnow and Joshua A. Grochow. [Complexity classes of equivalence problems revisited](http://dx.doi.org/10.1016/j.ic.2011.01.006). Inform. and Comput. 209:4 (2011), 748-763. Also available as [arXiv:0907.4775v2](http://arxiv.org/abs/0907.4775v2).

> **Comments:**
> **username_6**: Does GI in poly time imply $PEq=CF$ in your paper? What would imply such a result (any complete problems) and what would separate?  
> **username_4**: 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](http://www.cs.bu.edu/techreports/2011-028-poly-kernel-reductions.ps.Z) showed CEq-complete problems for C higher up in PH, but left open the question of the existence of PEq-complete problem.  
> **username_6**: would it be possible that existence of a complete problem in PEq implies PH collapses to some level?  
> **username_4**: @username_6: 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.  

---

