Representación formal de anillos en cálculos.

Al leer un documento sobre el uso de métodos algebraicos para detectar algunos subgrafos inducidos, parece que el ideal de borde es una herramienta importante que conecta el álgebra conmutativa y la teoría de grafos. Como no estoy familiarizado con los cálculos de objetos algebraicos, ¿hay alguna buena referencia o libro sobre este tema? Particularidad en la representación de un anillo R en una máquina de Turing, y la complejidad de decidir las propiedades básicas en R (por ejemplo, la altura de un ideal principal en R.)

Sus preguntas están relacionadas con un campo (sin juego de palabras) llamado "Álgebra de computadora". Yo mismo estaba buscando encuestas exhaustivas cuando estaba trabajando en métodos algebraicos para calcular varias métricas de centralidad gráfica. No pude encontrar buenas encuestas, pero este libro fue parcialmente útil. Los trabajos de investigación sobre este "tema" están dispersos por todas partes y, a menudo, no se clasifican explícitamente como "álgebra informática". La lectura de documentos algorítmicos sobre isomorfismo, factorización (enteros / polinomios) y algoritmos de gráficos basados ​​en la multiplicación de matrices podría brindarle más información.

A mi mejor saber:

1. Si lee acerca de los límites inferiores en algún modelo computacional algebraico, entonces la suposición habitual es que las operaciones de anillo o campo son de costo constante , es decir, se dan como primitivas. Esta es la suposición hecha en una de las principales fuentes sobre el tema: Burgisser, Clausen, Shokrollahi- Teoría de la complejidad algebraica (Springer, 1997). (Y esto es lo que modelan los circuitos algebraicos, por ejemplo).

2. Cuando se habla de límites superiores , para preguntas estándar en complejidad algebraica, como cuando se estudian los procedimientos de prueba de identidad polinómica, la suposición estándar es que las operaciones de anillo o campo se pueden calcular en polytime. Esto significa que uno trabaja sobre los enteros, o sobre los números racionales, y es fácil encontrar un esquema de codificación que permita cálculos tan eficientes de las operaciones básicas.

3. Para otros propósitos que conozco, en relación con los modelos algebraicos, la forma de representar el anillo o el campo es una pregunta real y, a veces, no hay una manera eficiente de hacerlo, e incluso puede haber preguntas de indecidibilidad. Las referencias que conozco que cubren este tipo de preguntas son el libro que Shiva Kintali dio, y también: Álgebra algorítmica , Bhubaneswar Mishra, Springer 1993: el Capítulo 3 trata sobre las formas de representar ciertos anillos.

Otros libros de interés podrían ser: Zur Gathen y Jurgen Gerhard, Modern Computer Algebra , Cambridge, 1999. Y posiblemente Victor Shoup, A Computational Introduction to Number Theory and Algebra , (Disponible en línea).

También puede tener suerte con las palabras clave 'álgebra conmutativa computacional' y 'geometría algebraica computacional'. Pruebe CLO como punto de partida y observe J. Computación simbólica, y sistemas como Macaulay2 y Singular y los documentos que los mencionan. El gran martillo es Gr \ "obner bases, cuyo cálculo resolverá muchos problemas algebraicos, pero es el peor de los casos doblemente exponencial en general.