Complejidad computacional de los tamaños y el número de órbitas de un grupo que actúa sobre un conjunto

Question

Me interesa la relación entre la complejidad computacional de contar órbitas y contar elementos en órbitas para grupos que actúan sobre conjuntos. Más formalmente:

Supongamos que $X_n$ es una secuencia infinita de conjuntos finitos indexados por $n\in\mathbb{N}$ . Supongamos que $G$ es un grupo con un conjunto finito de generadores. Además, supongamos que una acción de grupo de $G$ se define en cada conjunto $X_n$ y que esta acción puede ser calculada eficientemente dado un elemento de $G$ y un elemento de $X$ .

Considere los dos problemas siguientes:

Problema 1 (contar órbitas): Entrada: $n$

Dado $n$ , decida el número de órbitas de $G$ actuando en $X_n$ es decir, calcular el tamaño $|X_n/G|=|\{\{g\cdot x:g\in G\}:x\in X_n\}|$ .

Problema 2 (tamaño de la órbita): Entrada: $x\in X_n$

Dado $x\in X_n$ , decida el número de elementos en la órbita de $G$ actuando sobre $X_n$ que contiene x, es decir, calcular el tamaño $|\{g\cdot x:g\in G\}|$ .

Hace $\#P$ -Cumplimiento de Problema 2 implica $\#P$ -Completitud/Dureza de Problema 1 ?

Tenga en cuenta que $\#P$ -Cumplimiento de Problema 2 implica que el tamaño de $X_n$ debe escalar superpolinomialmente con $n$ .

Nota: He preguntado algo similar pregunta en StackExchange/Matemáticas, sin embargo, después de dos semanas y sólo una respuesta no relacionada, pensé en hacer también la misma pregunta aquí.

Answer 1

Dado que las acciones de grupo en el conjunto pueden ser bastante salvajes (pocas restricciones en la compatibilidad) no soy demasiado consciente de cualquier relación o incluso la posibilidad de encontrar tal reltaion, sin embargo, si usted tiene algo como una acción libre o algo similar, esto debería ayudar considerablemente a hacer realmente sus problemas equivalentes (ya que por ejemplo para una acción libre todas las órbitas están en biyección). Espero que esto ayude.

Answer 2

Supongo que se le da un conjunto finito $X=\{x_1,\ldots,x_m\}$ y un conjunto finito de generadores para $G$ , digamos que $g_1, \ldots, g_n$ que son permutaciones de $X$ .

Entonces, para cada $i$ y $j$ imagina una arista dirigida desde $x_i$ a $g_j\cdot x_i$ . Esto construye un gráfico dirigido a partir de los datos. Las órbitas son los componentes conectados. El tamaño de este gráfico es cuadrático en términos de la entrada. Tanto la búsqueda de amplitud como la de profundidad proporcionan un algoritmo de tiempo lineal para encontrar estos componentes conectados. No estoy seguro de qué suposiciones necesita para empezar a acercarse a $\# P$ -completa. ¿Tienes en mente alguna formulación de este problema donde $X$ es infinito?