Hay finitely grupos generados por cuya palabra problema es solucionable, pero no rápidamente? Sería genial tener ejemplos concretos, pero la existencia de resultados también sería útil.
Todos los grupos que conozco con solucionable palabra problema (lineal grupos, hiperbólico grupos, rama grupos) tienen un bajo grado del polinomio tiempo algoritmo para resolver el problema. Estoy buscando algo entre esos grupos y los que con el irresoluble problema de palabras.
Hay un muy buen artículo reciente "a través de Algoritmos complejos residual grupos finitos" por O. Kharlampovich, A. Myasnikov, y M. Sapir sobre esta cuestión - que contiene también muchas referencias a los resultados anteriores sobre la complejidad Dehn funciones y la complejidad de la palabra problema en casos específicos.
Teorema (Kharlampovich, Myasnikov, Sapir) Deje $f(n)$ ser una función recursiva. Entonces existe un residual finito finitely presentado solucionable grupo G tal que para cualquier finito presentación de $⟨X;R⟩$ de % de $G$ el tiempo de complejidad, tanto de los "sí" y "no" a las partes de la palabra problema son al menos tan alto como $f(n)$.
El documento también contiene ejemplos.
He aquí una receta para producir f.p. grupos con solucionable palabra problema, al menos tan duro como la pertenencia problema en cualquier conjunto $A$ de los enteros positivos.
Considerar el grupo $$\Gamma_A=\langle t,x\mid [t^nxt^{-n},x]=1, \forall n\in A\rangle.$$
A continuación, para $n>0$, $[t^nxt^{-n},x]=1$ en $\Gamma_A$ fib $n\in A$. En particular, ($\#$) el algoritmo para el problema de palabras en $\Gamma_A$ con la complejidad de la $f(n)$ (supremum de detener el tiempo para las entradas en el $n$-ball) resuelve los miembros problema en $A$ con detener el tiempo $\le f(4n+4)$.
El grupo $\Gamma_A$ ha solucionable palabra problema iff $A$ es recursiva. Así que para finitely generado grupo que se ha hecho con ningún requisito previo (por supuesto, esto se reduce a la cuestión de la complejidad de los miembros problema en recursiva de los subconjuntos de los números enteros, pero esto ya no es teoría de grupos).
Ahora una adaptación de Higman la incrustación por el teorema de Clapham (C. R. J. Clapham. Una incrustación teorema de finitely grupos generados", Proc. Londres. De matemáticas. Soc. (3), 17, 1967, 419-430.) los rendimientos que cada f.g. grupo con solucionable palabra problema incrusta en un finitely presentado el grupo con solucionable palabra problema. Si integramos $\Gamma_A$ en un finitely presentó el grupo de $\Lambda$ y requieren que el $t,x$ están entre una generación de subconjunto, entonces ($\#$) también se sostiene en $\Lambda$.
El caso de residual finito finitely presentan grupos es mucho más difícil y es dirigida por el Kharlampovich-Myasnikov-Sapir papel que se hace referencia en Andreas Thom la respuesta.
Un posible ejemplo es dado por Cremona grupos, como en este papel por Serge Cantat (sospecho que Yves Cornuiller comentar...)
Sé que no pedimos, pero el más natural de ejemplo, para mi el dinero de un countably generado grupo sería el colimit de la alternancia de los grupos de $A(2^k)$, unido a lo largo de las inclusiones $A(2^k) \to A(2^{k+1})$ dado por $\sigma \mapsto ((x, b) \mapsto (\sigma x, b))$. Usted puede pensar que este grupo de permutaciones de infinito bitstrings que arreglar cofinitely número de bits.
El grupo electrógeno es dado por tomar cualquier familia de reversible universal puertas y permitiendo a cada uno para actuar en cualquier tamaño apropiado subconjunto de la infinidad de bits. Aquí, decidir la palabra problema se reduce a decidir si el circuito representado por una palabra dada es la identidad, que es coNP completa.
EDIT: resulta que este ejemplo puede ser exprimido en un finitely generado grupo. Consulte este documento para un grupo que es finitely generado con coNP completar problema de palabras, obtenida por la construcción de una Thompson-como el grupo que contiene palabras que actúan como circuitos.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
