Komplexität der Berechnung des lexikographisch minimalen Elements der Umlaufbahn

Wie stark ist es angesichts starker Generatoren für eine Gruppe die auf Bitstrings der Länge und ein Element wirkt , das lexikographisch minimale Element von zu berechnen ? Umlaufbahn von in ? $(G \leq S_n, *)$ $n$ $s \in \{0, 1\}^n$ $G.s$ $s$ $G$

permutations gr.group-theory complexity Samuel Schlesinger
quelle

Offensichtlich ist der String-Isomorphismus im Sinne von Babai auf dieses Problem reduzierbar, da wir bei gegebenen Strings und der Gruppe einfach ihre minimalen Umlaufbahnrepräsentanten wie oben finden und sie direkt vergleichen können, aber es ist nicht klar, dass dies einfach ist, wenn der String-Isomorphismus einfach ist einfach zu sein folgt. Ich werde sehen, ob Babais Papier zeigt, wie das geht.

x, y

$x, y$

G

$G$

Samuel Schlesinger

Babais Artikel geht nicht auf diese Frage ein; auf P. 11 er sagt ausdrücklich, dass sich das Papier nicht mit der Frage normaler Formen befasst. Das heißt nicht, dass die Techniken nicht nützlich sein könnten, um eine normale Form zu finden, nur dass dies ein nicht trivialer Beitrag wäre.

Joshua Grochow

Vielen Dank @JoshuaGrochow Ich bin mir nicht sicher, ob ich den Hintergrund habe, um diese Techniken anzuwenden, aber ich werde sehen, was ich tun kann. Es ist angemessen schwierig, auch wenn es quasipolynomisch ist, dass es für mich nicht mehr so nützlich ist, wie ich es verwenden wollte.

Samuel Schlesinger

Wenn Sie an konkreten Lösungen für dieses Problem interessiert sind, empfehle ich Ihnen, einen Blick auf die Veröffentlichungen von T. Junttila zu werfen (die ich in meiner Antwort zitiere), insbesondere auf seine Doktorarbeit und seine Arbeit über Graphisomorphismus und Symmetrien im Allgemeinen.

Boson

Komplexität der Berechnung des lexikographisch minimalen Elements der Umlaufbahn

Antworten: