Complejidad de la computación Elemento lexicográfico mínimo de órbita

Dada generadores fuertes para un grupo que actúa sobre bitstrings de longitud y un elemento , lo difícil que es para calcular el elemento lexicográficamente mínima de , la órbita de en ? $(G \leq S_n, *)$ $n$ $s \in \{0, 1\}^n$ $G.s$ $s$ $G$

permutations gr.group-theory complexity Samuel Schlesinger
fuente

Claramente, el isomorfismo de cuerdas en el sentido de Babai es reducible a este problema, dado que las cadenas

y el grupo

simplemente podemos encontrar sus representantes mínimos de órbita como arriba y compararlos directamente, pero no está claro que si el isomorfismo de cuerdas es fácil, entonces esto Ser fácil sigue. Voy a ver si el artículo de Babai indica cómo hacer esto.

x, y

$x, y$

G

$G$

Samuel Schlesinger el

El artículo de Babai no aborda esta pregunta; en P. 11 él dice explícitamente que el documento no trata la cuestión de las formas normales. Eso no quiere decir que las técnicas no puedan ser útiles para encontrar una forma normal, solo que hacerlo sería una contribución no trivial.

Joshua Grochow

Gracias @JoshuaGrochow No estoy seguro de tener los antecedentes para usar estas técnicas, pero veré qué puedo hacer. Es adecuadamente difícil, incluso si es cuasipolinomial, que ya no es útil para mí en la forma en que quería usarlo.

Samuel Schlesinger el

Si está interesado en soluciones concretas a este problema, le recomiendo que eche un vistazo a las publicaciones de T. Junttila (a quien cito en mi respuesta), especialmente su tesis doctoral y su trabajo sobre isomorfismo gráfico y simetrías en general.

Boson

Complejidad de la computación Elemento lexicográfico mínimo de órbita

Respuestas: