Reducción de grano fino

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

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

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

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

Suponer${\displaystyle A}$es${\displaystyle (a,b)}$-reducible a${\displaystyle B}$y existe${\displaystyle \epsilon >0}$de tal manera que${\displaystyle B}$se puede resolver a tiempo${\displaystyle O{\bigl (}b(n)^{1-\epsilon }{\bigr )}}$. Entonces, con estas suposiciones, también existe${\displaystyle \delta >0}$de tal manera que${\displaystyle A}$se puede resolver a tiempo${\displaystyle O{\bigl (}a(n)^{1-\delta }{\bigr )}}$. Es decir, dejemos${\displaystyle \delta }$sea ​​el valor dado por el${\displaystyle (a,b)}$-reducción y resolver${\displaystyle A}$aplicando la transformación de la reducción y utilizando el algoritmo rápido para${\displaystyle B}$para cada subproblema resultante. ^{[ 1 ]}

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

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

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

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