Resumen - En la Complejidad del Problema de Skolem en Bajas Ordenes

En la Complejidad del Problema de Skolem en Bajas Ordenes

2025-07-15 12:04:28

{"Piotr Bacik","Joël Ouaknine","James Worrell"}

{cs.CC,cs.LO}

El Problema de Skolem pregunta si una secuencia de recurrencia lineal dada (LRS) tiene un término cero. Aunque el problema es indecidible en general, el artículo presenta un algoritmo aleatorio para una versión acotada del problema, determinando si existe un término cero dentro de un rango especificado. Este algoritmo se ejecuta en tiempo polinomial para LRS de orden hasta d, y como corolario, muestra que el Problema de Skolem sin restricciones para LRS de orden hasta 4 se encuentra en coRP (RAM certificado con tiempo polinomial). La clave del algoritmo radica en extender la LRS a una función analítica p-adica F, y utilizar el análisis p-adico para encontrar ceros candidatos dentro de un rango exponencialmente grande. El algoritmo realiza una búsqueda en profundidad de todos los residuos m dentro del rango, y para cada cero candidato, construye un circuito aritmético que representa el término um y verifica la ceroedad en tiempo polinomial aleatorio. El tiempo de ejecución del algoritmo es exponencial en el orden de la LRS, lo cual es necesario debido a la complejidad NP-hard del problema acotado. Sin embargo, incluso para LRS de orden fijo, el problema implica detectar ceros dentro de un rango exponencialmente grande, lo que requiere el uso del análisis p-adico. El algoritmo se basa en un enfoque p-adico introducido por Skolem en su prueba original del Teorema de Skolem-Mahler-Lech. Esto implica extender la LRS a una función analítica p-adica F, y utilizar el análisis p-adico para encontrar ceros de F. El algoritmo utiliza la representación de serie de Mahler de series p-adicas, lo que le permite trabajar con la LRS subyacente sin calcular directamente con números p-adicos. La corrección del algoritmo depende de una refinamiento cuantitativo de la prueba de Skolem, debido a Van der Poorten y Schlickewei. Este resultado proporciona un límite superior sobre el número de ceros de F en el campo p-adico, lo que se traduce en un límite polinomial sobre el número de ceros candidatos examinados por el algoritmo. Además, este resultado se utiliza en combinación con el Teorema de Preparación de Weierstrass para determinar en tiempo polinomial si la serie de potencias F tiene un cero en el campo p-adico. En conclusión, el artículo presenta un algoritmo aleatorio para el Problema de Skolem acotado que se ejecuta en tiempo polinomial para LRS de orden hasta d, y muestra que el Problema de Skolem sin restricciones para LRS de orden hasta 4 se encuentra en coRP. La complejidad del algoritmo es exponencial en el orden de la LRS, lo cual es necesario debido a la complejidad NP-hard del problema.