Complexité du calcul élément lexicographiquement minimal d'orbite

Étant donné des générateurs puissants pour un groupe agissant sur des chaînes de bits de longueur et un élément , combien est-il difficile de calculer l'élément lexicographiquement minimal de , le orbite de en ? $(G \leq S_n, *)$ $n$ $s \in \{0, 1\}^n$ $G.s$ $s$ $G$

permutations gr.group-theory complexity Samuel Schlesinger
la source

Il est clair que l'isomorphisme de chaînes au sens de Babai est réductible à ce problème, étant donné les chaînes et le groupe nous pouvons simplement trouver leurs représentants en orbite minimale comme ci-dessus et les comparer directement, mais il n'est pas clair que si l'isomorphisme de chaînes est facile, alors ceci être facile suit. Je vais voir si le document de Babai indique comment procéder.

x, y

$x, y$

G

$G$

Samuel Schlesinger

Le document de Babai n'aborde pas cette question; dans. 11 il dit explicitement que le papier ne traite pas de la question des formes normales. Cela ne veut pas dire que les techniques ne pourraient pas être utiles pour trouver une forme normale, mais que le faire serait une contribution non triviale.

Joshua Grochow

Merci @JoshuaGrochow Je ne sais pas si j'ai les antécédents pour utiliser ces techniques mais je vais voir ce que je peux faire. C'est assez difficile, même s'il est quasi-polynomial qu'il ne m'est plus utile de la façon dont je voulais l'utiliser.

Samuel Schlesinger

Si vous êtes intéressé par des solutions concrètes à ce problème, je vous recommande de jeter un œil aux publications de T. Junttila (que je cite dans ma réponse), en particulier sa thèse de doctorat et ses travaux sur l'isomorphisme graphique et les symétries en général.

Boson

Complexité du calcul élément lexicographiquement minimal d'orbite

Réponses: