Reducción de grano fino

En teoría de la complejidad computacional , una reducción detallada es una transformación de un problema computacional a otro, utilizada para relacionar la dificultad de mejorar los límites de tiempo para los dos problemas. De manera intuitiva, proporciona un método para resolver un problema de manera eficiente utilizando la solución del otro problema como una subrutina . Si el problema se puede resolver a tiempo y el problema se puede resolver a tiempo , entonces la existencia de una reducción de un problema a otro implica que cualquier aceleración significativa del problema también conduciría a una aceleración del problema . ${\displaystyle A}$ ${\displaystyle a(n)}$ ${\displaystyle B}$ ${\displaystyle b(n)}$ ${\displaystyle (a,b)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$

Definición

Sean y problemas computacionales, especificados como la salida deseada para cada entrada posible. Sean y ambas funciones construibles en el tiempo que toman un argumento entero y producen un resultado entero. Por lo general, y son los límites de tiempo para algoritmos conocidos o ingenuos para los dos problemas y, a menudo, son monomios como . ^[1] ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle n^{2}}$

Entonces se dice que es reducible a si, para cada número real , existe un número real y un algoritmo que resuelve instancias del problema transformándolo en una secuencia de instancias del problema , tomando tiempo para la transformación en instancias de tamaño , y produciendo una secuencia de instancias cuyos tamaños están limitados por . ^[1] ${\displaystyle A}$ ${\displaystyle (a,b)}$ ${\displaystyle B}$ ${\displaystyle \epsilon >0}$ ${\displaystyle \delta >0}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle O{\bigl (}a(n)^{1-\delta }{\bigr )}}$ ${\displaystyle n}$ ${\displaystyle n_{i}}$ ${\displaystyle \sum _{i}b(n_{i})^{1-\epsilon }<a(n)^{1-\delta }}$

Una reducción viene dada por el mapeo desde al par de un algoritmo y . ^[1] ${\displaystyle (a,b)}$ ${\displaystyle \epsilon }$ ${\displaystyle \delta }$

Implicación de aceleración

Supongamos que es reducible a y existe algo que puede resolverse a tiempo . Entonces, con estos supuestos, también existen otros que se pueden solucionar con el tiempo . Es decir, sea el valor dado por la reducción y resuelva aplicando la transformación de la reducción y usando el algoritmo rápido para cada subproblema resultante. ^[1] ${\displaystyle A}$ ${\displaystyle (a,b)}$ ${\displaystyle B}$ ${\displaystyle \epsilon >0}$ ${\displaystyle B}$ ${\displaystyle O{\bigl (}b(n)^{1-\epsilon }{\bigr )}}$ ${\displaystyle \delta >0}$ ${\displaystyle A}$ ${\displaystyle O{\bigl (}a(n)^{1-\delta }{\bigr )}}$ ${\displaystyle \delta }$ ${\displaystyle (a,b)}$ ${\displaystyle A}$ ${\displaystyle B}$

De manera equivalente, si no se puede resolver en un tiempo significativamente más rápido que , entonces no se puede resolver en un tiempo significativamente más rápido que . ^[1] ${\displaystyle A}$ ${\displaystyle a(n)}$ ${\displaystyle B}$ ${\displaystyle b(n)}$

Historia

Virginia Vassilevska Williams y Ryan Williams definieron reducciones de grano fino, en el caso especial de que y sean monomios iguales, en 2010. También mostraron la existencia de reducciones entre varios problemas, incluidos los caminos más cortos de todos los pares , encontrando el segundo más corto. ruta entre dos vértices dados en un gráfico ponderado, encontrar triángulos de peso negativo en gráficos ponderados y probar si una matriz de distancia dada describe un espacio métrico . Según sus resultados, o todos estos problemas tienen límites de tiempo con exponentes menores que tres, o ninguno de ellos los tiene. ^[2] ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle (n^{3},n^{3})}$

El término "reducción de grano fino" proviene de un trabajo posterior de Virginia Vassilevska Williams en una presentación invitada en el X Simposio Internacional sobre Computación Exacta y Parametrizada. ^[1]

Aunque la definición original de reducciones detalladas involucraba algoritmos deterministas, también se han considerado los conceptos correspondientes para algoritmos aleatorios y algoritmos no deterministas . ^[3]

Referencias

1. Williams, Virginia V. (2015), "Dureza de problemas fáciles: basar la dureza en conjeturas populares como la hipótesis del tiempo exponencial fuerte", Décimo Simposio Internacional sobre Computación Exacta y Parametrizada , LIPIcs. Internacional Leibniz. Proc. Informar., vol. 43, Palacio Dagstuhl. Leibniz-Zent. Informar., Wadern, págs. 17–29, SEÑOR  3452406
2. Williams, Virginia Vassilevska ; Williams, R. Ryan (2018), "Equivalencias subcúbicas entre problemas de trayectoria, matriz y triángulo", Journal of the ACM , 65 (5): A27:1–A27:38, doi :10.1145/3186893, hdl : 1721.1/ 134750 , señor  3856539. En el Simposio de 2010 sobre fundamentos de la informática se presentó una versión preliminar de estos resultados, incluida la definición de "reducción subcúbica", un caso especial de reducción de grano fino .
3. Carmosino, Marco L.; Gao, Jiawei; Impagliazzo, Russell ; Mihajlin, Iván; Paturi, Ramamohan; Schneider, Stefan (2016), "Extensiones no deterministas de la hipótesis del tiempo exponencial fuerte y consecuencias para la no reducibilidad", ITCS'16 — Actas de la Conferencia ACM de 2016 sobre innovaciones en informática teórica , ACM, Nueva York, págs. 270, señor  3629829