<p>This problem is $FP^{NP}$-complete, as shown <a href="https://users.ics.aalto.fi/tjunttil/publications/orbit.ps" rel="noreferrer">here</a>.</p>

<p>It means that the lexicographical leader of the orbit is built in deterministic polynomial time with access to a $NP$-oracle.</p>

CC BY-SA 3.0
2017-03-13T18:20:40.217Z
2017-03-13T18:20:40.217Z
Boson
<p>This problem is NP-hard.</p>

<p>Although it may be possible to find some canonical form for string isomorphism, say, in quasi-poly time, without upsetting our current guesses as to how the complexity world looks, finding the <em>lexicographically least</em> isomorphic string is NP-hard. This is precisely the content of Proposition 3.1 <a href="https://doi.org/10.1145/800061.808746" rel="noreferrer">here</a>. In fact, they show it remains NP-hard even when $G$ is an elementary abelian 2-group (=every nontrivial element of $G$ has order 2).</p>

CC BY-SA 3.0
2017-03-13T16:11:12.017Z
2017-03-13T16:11:12.017Z
Joshua Grochow
<p>Given strong generators for a group $(G \leq S_n, *)$ acting on bitstrings of length $n$ and an element $s \in \{0, 1\}^n$, how hard is it to compute the lexicographically minimal element of $G.s$, the orbit of $s$ in $G$? </p>

CC BY-SA 3.0
2017-03-12T20:30:28.840Z
Clearly string isomorphism in the sense of Babai is reducible to this problem, as given $x, y$ strings and group $G$ we can simply find their minimal orbit representatives as above and directly compare them, but its not clear that if string isomorphism is easy then this being easy follows. I'm going to see if Babai's paper indicates how to do this.
Samuel Schlesinger
CC BY-SA 3.0
2017-03-12T21:01:37.353Z
Babai's paper does not address this question; on p. 11 he explicitly says they paper doesn't deal with the question of normal forms. That's not to say the techniques couldn't be useful for finding a normal form, just that doing so would be a non-trivial contribution.
Joshua Grochow
CC BY-SA 3.0
2017-03-12T21:06:32.360Z
Thank you @JoshuaGrochow I'm not sure if I have the background to use these techniques but I'll see what I can do. It's suitably hard even if it is quasipolynomial that it's no longer useful for me in the way I wanted to use it.
Samuel Schlesinger
CC BY-SA 3.0
2017-03-13T18:25:43.130Z
If you are interested in concrete solutions to this problem, I recommend that you take a look at the publications of T. Junttila (whom I cite in my answer), especially his PhD thesis and his work on graph isomorphism and symmetries in general.
Boson
<permutations><gr.group-theory><complexity>
Complexity of Computing Lexicographically Minimal Element of Orbit
Samuel Schlesinger
# Complexity of Computing Lexicographically Minimal Element of Orbit

(Asked by: username_0 on 2017-03-12)

Given strong generators for a group $(G \leq S\_n, \*)$ acting on bitstrings of length $n$ and an element $s \in \{0, 1\}^n$, how hard is it to compute the lexicographically minimal element of $G.s$, the orbit of $s$ in $G$?

**Tags:** permutations, gr.group-theory, complexity
> **Comments:**
> **username_0**: Clearly string isomorphism in the sense of Babai is reducible to this problem, as given $x, y$ strings and group $G$ we can simply find their minimal orbit representatives as above and directly compare them, but its not clear that if string isomorphism is easy then this being easy follows. I'm going to see if Babai's paper indicates how to do this.  
> **username_1**: Babai's paper does not address this question; on p. 11 he explicitly says they paper doesn't deal with the question of normal forms. That's not to say the techniques couldn't be useful for finding a normal form, just that doing so would be a non-trivial contribution.  
> **username_0**: Thank you @JoshuaGrochow I'm not sure if I have the background to use these techniques but I'll see what I can do. It's suitably hard even if it is quasipolynomial that it's no longer useful for me in the way I wanted to use it.  
> **username_2**: If you are interested in concrete solutions to this problem, I recommend that you take a look at the publications of T. Junttila (whom I cite in my answer), especially his PhD thesis and his work on graph isomorphism and symmetries in general.  

---

## 2 answers

### Answer by username_2 on 2017-03-13. Score: 5 | Accepted answer

This problem is $FP^{NP}$-complete, as shown [here](https://users.ics.aalto.fi/tjunttil/publications/orbit.ps).

It means that the lexicographical leader of the orbit is built in deterministic polynomial time with access to a $NP$-oracle.


---

### Answer by username_1 on 2017-03-13. Score: 5

This problem is NP-hard.

Although it may be possible to find some canonical form for string isomorphism, say, in quasi-poly time, without upsetting our current guesses as to how the complexity world looks, finding the *lexicographically least* isomorphic string is NP-hard. This is precisely the content of Proposition 3.1 [here](https://doi.org/10.1145/800061.808746). In fact, they show it remains NP-hard even when $G$ is an elementary abelian 2-group (=every nontrivial element of $G$ has order 2).


---

