Complexity of Computing Lexicographically Minimal Element of Orbit 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$?
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. 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).