Quiero especificar qué significa dar un álgebra como entrada a un algoritmo y no encontré mucha literatura al respecto. Primero, quiero preguntar si puede recomendar un libro o documento que aborde el tema del análisis de complejidad de álgebras sobre campos y defina claramente el problema de decisión .
Después de investigar un poco, encontré algo y quiero compartirlo aquí y, además, preguntar si las definiciones tienen sentido y si cumplen con la literatura (si hay alguna):
Definición: Let sea un campo y ser conmutativo finito generado -algebra con aditivo de base . Ahora queremos capturar la estructura multiplicativa del álgebra y, por lo tanto, escribir cada producto de los elementos básicos como una combinación lineal de todos los elementos básicos: Los se denominan coeficientes de estructura . Tenemos eso directamente:
Ahora se puede definir el siguiente problema de decisión: Para especificar un isomorfismo es suficiente para escribir todos los como combinación lineal de los elementos de una base de .
¿Le parece extraño algo en esta definición o cree que se puede trabajar con él?
Motivación: Mi motivación detrás de esto es dar una definición muy clara del problema de decisión primero para conectarlo con otros problemas, es decir, el problema de decidir la equivalencia polinómica: Dados dos polinomios , decimos que es equivalente a si existe una transformación lineal invertible en las variables tales que . En otras palabras, dos polinomios son equivalentes si puede reemplazar cada variable por una combinación lineal de todas las variables para obtener el otro polinomio.
No estoy seguro de si esto ayuda como motivación, pero la conexión de estos problemas se establece construyendo álgebras conmutativas generadas finitamente a partir de los dos polinomios que son isomórficos si y solo si los polinomios son equivalentes. Para esto quería asegurarme de que el problema de decisión se define muy claramente.
Respuestas:
Esto parece ser consistente con la presentación en Equivalencia de -algebras y formas cúbicasF , Agrawal y Saxena (2006) .
fuente
La computabilidad sobre la estructura matemática es un área de investigación larga y bien establecida. Por ejemplo, ver:
Edward R. Griffor, " Manual de teoría de la computabilidad ", 1999
Leonidovich Ershov, " Manual de Matemáticas Recursivas: Álgebra Recursiva, Análisis y Combinatoria ", 1998
o google para:
fuente