9
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Samuel Schlesinger Mar 12 '17 at 20:30
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow Mar 12 '17 at 21:01
  • $\begingroup$ 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. $\endgroup$ – Samuel Schlesinger Mar 12 '17 at 21:06
  • $\begingroup$ 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. $\endgroup$ – Boson Mar 13 '17 at 18:25
5
$\begingroup$

This problem is $FP^{NP}$-complete, as shown here.

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

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.