¿Cuál es el algoritmo más eficiente para decidir si un elemento es el menos en su órbita?

Dado un grupo actúa sobre un conjunto con un orden total y una , ¿cuál es el algoritmo más eficiente para decidir si x es el elemento mínimo en su órbita? En otras palabras, decidir si ? $G$ $X$ $\leq$ $x\in X$ $min(Gx) = x$

Mi motivación proviene de la resolución SMT donde ha habido algún interés en romper simetrías automáticamente. Agregar predicados de ruptura de simetría a menudo resulta en un conjunto de cláusulas grandes, por lo tanto, estoy interesado en la posibilidad de manejar esto como una propagación de teoría perezosa.

La descripción anterior es quizás demasiado general y, como lo señala sid , NP-hard. Una posible tarea más simple es, dado un grupo de permutaciones de cadenas de longitud codificadas como un conjunto de generadores y una cadena de longitud . ¿Cuál es el algoritmo más eficiente para decidir si esa cadena es la más lexicográfica en su órbita? $n$ $x$ $n$

ds.algorithms gr.group-theory HaskellElefante
fuente

Supongo que estás hablando de conjuntos finitos X? Creo que decidir esto es NP-hard. Sea

un recorrido por un conjunto de ciudades en el problema del Vendedor Viajero con

. Deje que el grupo

sea el grupo simétrico

. Entonces la órbita es todos los recorridos posibles y probar que uno de ellos es mínimo es NP-hard.

X = {c_{1}, \dots, c_{n}}

$X=\{c_1,\dots,c_n\}$

c_{1} \to c_{2} \dots

$c_1 \rightarrow c_2 \dots$

G

$G$

S_{n}

$S_n$

Optar el

@Sid, sí, solo estoy interesado en el caso en el que X es finito, y no lo había pensado, pero ciertamente es NP-hard. Supongo que aún podría existir la posibilidad de un algoritmo eficiente de Monte Carlo.

HaskellElephant

Aunque si utiliza un criterio diferente para el mínimo, aquí es polinomial: es fácil encontrar el recorrido lexicográficamente más pequeño (al menos si supone que todos los bordes tienen etiquetas diferentes; de lo contrario, sigue siendo NP-duro).

Peter Shor

@ PeterShor, sí, de hecho para mi propósito, cualquier forma canónica servirá.

HaskellElephant

se presentan como oráculos de valor, esto requiere la enumeración de

G

$G$

X

$X$

G

$G$

David Harris

Para las relaciones de equivalencia general, no las que surgen de las acciones del grupo de permutación, incluso encontrar lo menos lexicográficamente sigue siendo "demasiado" general. Encontrar el elemento lexicográficamente más pequeño en una clase de equivalencia puede ser -hard (de hecho, -hard), incluso si la relación tiene una forma canónica de tiempo polinomial [1]. $NP$ $P^{NP}$

Sin embargo, para los problemas de órbita del grupo de permutación como usted describe, decidir si dos puntos se encuentran en la misma órbita no es probable que sea duro: está en , y por lo tanto no duro a menos que el jerarquía polinómica se colapsa al segundo nivel. $NP$ $NP \cap coAM$ $NP$

Una forma canónica para el isomorfismo gráfico es también un caso especial del segundo problema que usted plantea. La forma canónica más conocida para el isomorfismo gráfico se ejecuta en el tiempo [2]. $2^{\tilde{O}(\sqrt{n})}$

Como usted dijo en los comentarios que cualquier forma canónica servirá, también podría estar interesado en mi artículo con Lance Fortnow [3]: en su generalidad actual, creo que su pregunta está relacionada con nuestros resultados. Se demuestra que si cada relación decidable equivalencia en tiene una forma canónica en , luego "malos" consecuencias como resultado, tal como , que, en particular, implica que la jerarquía polinomio colapsa a . Por otro lado, las relaciones de equivalencia que le interesan pueden no estar en $P$ $P$ $NP = UP = RP$ $BPP$ $P$ , pero este resultado sugiere que incluso si se encuentra en una clase de mayor complejidad, otros problemas difíciles aún pueden interponerse en su camino.

Así que creo que si quieres mejores límites superiores, realmente necesitas que el problema sea más específico.

[1] Andreas Blass y Yuri Gurevich. Relaciones de equivalencia, invariantes y formas normales . SIAM J. Comput. 13: 4 (1984), 24-42.

[2] László Babai y Eugene M. Luks. Etiquetado canónico de gráficos . STOC 1983, 171-183.

[3] Lance Fortnow y Joshua A. Grochow. Clases de complejidad de problemas de equivalencia revisitados . Informar. y Comput. 209: 4 (2011), 748-763. También disponible como arXiv: 0907.4775v2 .

Joshua Grochow
fuente

¿GI en tiempo poli implica

en tu trabajo? ¿Qué implicaría tal resultado (cualquier problema completo) y qué se separaría?

P E q = C F

$PEq=CF$

T ....

No tan lejos como sé. En el mejor de los casos, implicaría que cualquier problema de isomorfismo combinatorio está en Ker (FP); un problema es que una forma canónica para un gráfico no necesita producir una forma canónica para la estructura con la que comenzó; El otro problema es que el isomorfismo combinatorio no es necesariamente completo de PEq. Preguntamos si había problemas de PEq-complete; Finkelstein y Hescott mostraron problemas de CEq-complete para C más arriba en PH, pero dejaron abierta la cuestión de la existencia del problema de PEq-complete.

Joshua Grochow

¿Sería posible que la existencia de un problema completo en PEq implique colapsos de PH a algún nivel?

T ....

@Turbo: Claro, aunque me parece un poco improbable. ¿Conoces algún ejemplo en el que la existencia de un problema completo para alguna clase implique colapsos de PH? (Aparte de los problemas de PH completo.) Creo que es probable que (a) existan problemas de PEq completo (y no contradigan conjeturas importantes), simplemente no hemos descubierto cómo construirlos, o (b) allí son oráculos que van en ambos sentidos sobre la existencia de problemas completos de PEq. (b) me parece más probable, por analogía con BPP, porque PEq es esencialmente una clase semántica.

Joshua Grochow

¿Cuál es el algoritmo más eficiente para decidir si un elemento es el menos en su órbita?

Respuestas: