Hay problemas de cálculo en los grupos que son más difíciles de P?

Question

Hay varios bien conocidos clases de los grupos para los que la palabra problema, conjugacy etc. son resolubles en tiempo polinomio (hiperbólica, automático).

A continuación, hay varias clases de grupos como de forma asincrónica automática de los grupos para los que se sabe que existe un algoritmo de tiempo exponencial para resolver el problema (y si puede ser mejorado a un polinomio es abierto y conjeturó que yo soy consciente).

Va varios pasos más allá, existe un algoritmo para resolver el problema en uno de los grupos de relator en el tiempo no limitada por cualquier finito de la torre de exponenciales (y de nuevo está abierto y la conjetura de si esto se puede mejorar a-P).

Por el otro, existen algoritmos para resolver problemas de palabras en grupos patológicos como la Baumslag-Gersten grupo:

$$G_{(1,2)} = \langle a, b | a^{a^b}= a^2 \rangle$$

en el polinomio de tiempo. Así que aunque en general los algoritmos pueden ser muy malo, se desconoce si hay grupo de algoritmos específicos para cada grupo en una clase determinada que resolver el problema rápidamente.

Así que mi pregunta es, ¿hay alguno de los grupos en que se conoce que la palabra problema (o cualquier otro problema computacional) es al menos exponencial, pero todavía solucionable? Tal vez exp-completa? ¿Cuáles son los enfoques para probar tal cosa?

Answer 1

Una referencia anterior para los grupos con esta propiedad es

J. Avenhaus y K. Madlener. Subrekursive Komplexität der Gruppen. I. Gruppen mit vorgeschriebenen Komplexität. Acta Infomat., 9 (1): 87-104, 1977/78.

Existe una jerarquía de las funciones recursivas conocido como el (difícil de pronunciar) Grzegorczyk Jerarquía de $E_0 \subset E_1 \subset E_2 \subset \cdots$, donde de (aproximadamente) $E_1$ contiene el linealmente acotados funciones, $E_2$ exponencialmente delimitadas las funciones y $E_3$ aquellas funciones que están delimitadas por iterada exponenciales.

El anterior documento describe las construcciones de finitely presentado los grupos de $G_n$ para $n \ge 3$, en el que la resolución de la palabra problema tiene tiempo de complejidad limitada por una función de $E_n$ , pero no por cualquier función en $E_{n-1}$,

Answer 2

Como Andreas dice (en su respuesta y su comentario), existe son grupos cuya palabra problema es indecidible y uno de forma similar podría configurar un grupo que codifica la detención problema de una clase de máquinas de Turing donde esta es decidable pero difícil. Sin embargo, uno debe ser cuidadoso en la codificación. En

Isoperimétrico y Isodiamétricos Funciones de los Grupos, Mark V. Sapir, Jean-Camille Birget y Eliyahu Rips Anales de las Matemáticas Segundo De La Serie, Vol. 156, Nº 2 (Sep., 2002), pp 345-466

y

Mark V. Sapir, Jean-Camille Birget y Eliyahu Rips Isoperimétrico funciones de los grupos y la complejidad del cálculo de la palabra problema. Ann. de Matemáticas. (2) 156 (2002), no. 2, 467-518.

grupos con NP completo de la palabra problema se construyen y otros resultados similares. Véase, en particular, Corolario 1.1 de la primera de papel enumerados anteriormente.

Para añadir más información, Corolario 1.1 dice:

Existe una finitely presentó con el grupo de NP-completo de la palabra problema. Por otra parte, para cada idioma $L\subseteq A^*$ para algunos alfabeto finito $A$ existe un finitely presentó el grupo de $G$ tal que los no deterministas complejidad de $G$ es exponencialmente equivalente a la de los no deterministas complejidad de $L$.

Así, por ejemplo, si $L$ es una EXP-tiempo completo el problema, entonces el problema de $G$ es en NEXP en tiempo y no en NP (por lo tanto no P). Por supuesto, usted puede reemplazar la EXP por su momento favorito de la complejidad de la clase estrictamente por encima de NP.

Answer 3

Hay finitely presentan grupos cuya palabra problema es indecidible. Véase, por ejemplo, https://en.wikipedia.org/wiki/Word_problem_for_groups .

Answer 4

Problema clásico que se cree no estar en P es el número de factoring, que puede ser el reparto de la computación en la descomposición de un grupo cíclico en los más sencillos.

Varios problemas en la permutación de grupos son conocidos por ser tan duro como el gráfico de isomorfismo, por lo tanto no se consideran en P, demasiado.

Hay también NP-hard problemas conocidos para la permutación de grupos, véase, por ejemplo, https://www.sciencedirect.com/science/article/pii/S0012365X09001289

Answer 5

Mientras la mayoría de las respuestas han mencionado computacional de los problemas relacionados con la finitely presentado (pero, en general infinito) grupos, hay muchos problemas en teoría de grupos finitos que son conjetura o conocido para ser NP-completo. Como ejemplo, tenemos el siguiente resultado de A. Lubiw, "Algunos NP-completos, problemas similares a los del gráfico de isomorfismo", SIAM J. Comp. 10(1981) 11-21.

El problema de determinar si $G$ tiene un punto fijo gratuito elemento es NP-completo, incluso para la primaria abelian $2$-grupos.

El clásico problema de determinar el número de subgrupos de un grupo de orden $n$ es también, como lo que puedo decir, conjeturó a ser muy difícil, pero yo no soy consciente de que cualquier declaración concluyente en cualquier dirección.

Volviendo al mundo de finitely presentado los grupos, el subconjunto suma el problema se define como sigue. Dado $g_1, \dots, g_k, g \in G$, decidir si $$ g = g_1^{\varepsilon_1} \cdots g_k^{\varepsilon_k}$$ for some $\varepsilon_1, \dots \varepsilon_k \en \{ 0, 1\}$. This problem is known to be NP-complete for a vast range of different classes of groups, including, but not limited to, free metabelian non-abelian groups of finite rank, and the wreath product of two finitely generated infinite abelian groups. It is also known to be NP-complete in some particular cases, such as for $BS(1, 2)$ and Thompson's group $F$. En hiperbólico grupos, sin embargo, el problema es la P de tiempo decidable, por lo que el problema es ciertamente interesante.

El subconjunto suma problema y muchos otros problemas relacionados, por finitely presentado los grupos que se estudian en detalle en A. Miasnikov, A. Nikolaev, A. Ushakov, "Mochila de Problemas en Grupos", de Matemáticas. de Comp. 84(2013).