Un FPRAS más rápido para #NFA

Dado un autómata finito no determinista (NFA) A con m estados, y un número natural n (presentado en unary), el problema #NFA pregunta por determinar el tamaño del conjunto L(A,n) de palabras de longitud n aceptadas por A. Mientras que el problema de decisión correspondiente de comprobar la vacuidad de L(A,n) se puede resolver en tiempo polinómico, se sabe que el problema #NFA es #P-duro. Recientemente, la larga pregunta sin respuesta ---si existe un FPRAS (esquema de aproximación aleatoria totalmente polinómico) para #NFA--- fue resuelta por Arenas, Croquevielle, Jayaram y Riveros en ACJR19. Los autores demostraron la existencia de un esquema de aproximación aleatoria totalmente polinómica con una complejidad temporal de ~O(m 17 n 17 • 1/ε 14 • log (1/δ)), para una tolerancia dada ε y parámetro de confianza δ. Dada la complejidad temporal prohibitivamente alta en términos de cada uno de los parámetros de entrada, y considerando la aplicación generalizada del conteo aproximado (y muestreo) en varias tareas en Ciencias de la Computación, surge una pregunta natural: ¿existe un FPRAS más rápido para #NFA que pueda allanar el camino para la implementación práctica de herramientas aproximadas para #NFA? En este trabajo, respondemos afirmativamente a esta pregunta. Demostramos que se pueden lograr mejoras significativas en la complejidad del tiempo, y proponemos un FPRAS para #NFA que es más eficiente tanto en términos de tiempo como de complejidad de muestra. Un ingrediente clave en el FPRAS debido a Arenas, Croquevielle, Jayaram y Riveros ACJR19 es la inter-reducibilidad del muestreo y el conteo, lo que requiere una inspección más cercana de la medida más informativa ---el número de muestras mantenidas para cada par de estado q y longitud i <= n. En particular, el esquema de ACJR19 mantiene O(m 7 /n 7 ε 7) muestras por par de estado y longitud. En el FPRAS que proponemos, reducimos sistemáticamente el número de muestras requeridas para cada estado para que dependa solo polilogarítmicamente de m, con una dependencia significativamente menor de n y ε, manteniendo solo ~O(n 4 /ε 2) muestras por estado. En consecuencia, nuestro FPRAS se ejecuta en tiempo ~O((m 2 n 10 + m 3 n 6) • 1/ε 4 • log 2 (1/δ)). El FPRAS y su análisis utilizan varias ideas novedosas. Primero, nuestro FPRAS mantiene un invariante más débil sobre la calidad de la estimación del número de muestras para cada estado q y longitud i <= n. Segundo, nuestro FPRAS solo requiere que la distribución de las muestras mantenidas esté cercana a una distribución uniforme solo en distancia de variación total (en lugar de norma máxima). Creemos que nuestras ideas pueden conducir a reducciones adicionales en la complejidad del tiempo y, por lo tanto, abrir una avenida prometedora para trabajos futuros hacia la implementación práctica de herramientas para el #NFA aproximado.