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$?
$\begingroup$
$\endgroup$
4
asked Mar 12, 2017 at 18:46
-
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 SchlesingerMar 12, 2017 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 GrochowMar 12, 2017 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 SchlesingerMar 12, 2017 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$– BosonMar 13, 2017 at 18:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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).
answered Mar 13, 2017 at 16:11