La autorreductibilidad aleatoria (RSR) es la regla de que un buen algoritmo para el caso promedio implica un buen algoritmo para el peor de los casos. RSR es la capacidad de resolver todas las instancias de un problema resolviendo una gran fracción de las instancias.
Definición
Si para una función f que evalúa cualquier instancia x se puede reducir en tiempo polinomial a la evaluación de f en una o más instancias aleatorias y i , entonces es auto-reducible (esto también se conoce como una auto-reducción uniforme no adaptativa ) . En una autorreducción aleatoria, una instancia arbitraria del peor de los casos x en el dominio de f se asigna a un conjunto aleatorio de instancias y 1 , ..., y k . Esto se hace para que f ( x ) se pueda calcular en tiempo polinomial, dada la secuencia de lanzamiento de moneda del mapeo, x , y f ( y 1 ), ..., f ( y k ). Por lo tanto, tomando el promedio con respecto a la distribución inducida en y i , la complejidad de caso promedio de f es la misma (dentro de los factores polinomiales) que la complejidad aleatorizada del peor caso de f .
Un caso especial a destacar es cuando cada instancia aleatoria y i se distribuye uniformemente sobre todo el conjunto de elementos en el dominio de f que tienen una longitud de | x |. En este caso, f es tan difícil en promedio como en el peor de los casos. Este enfoque contiene dos restricciones clave. Primero, la generación de y 1 , ..., y k se realiza de forma no adaptativa. Esto significa que y 2 se elige antes de que se conozca f ( y 1 ). En segundo lugar, no es necesario que los puntos y 1 , ..., y k estén distribuidos uniformemente.
Aplicación en protocolos criptográficos
Los problemas que requieren cierta privacidad en los datos (generalmente problemas criptográficos ) pueden usar la aleatorización para garantizar esa privacidad. De hecho, el único sistema criptográfico comprobablemente seguro (el bloc de notas de un solo uso ) tiene su seguridad que depende totalmente de la aleatoriedad de los datos clave suministrados al sistema.
El campo de la criptografía utiliza el hecho de que ciertas funciones de la teoría de números son autoreducibles aleatoriamente. Esto incluye cifrado probabilístico y generación de números pseudoaleatorios criptográficamente fuertes . Además, los esquemas de ocultación de instancias (donde un dispositivo privado débil usa un dispositivo público fuerte sin revelar sus datos) se ejemplifican fácilmente mediante autorreducciones aleatorias.
Ejemplos de
El problema del logaritmo discreto , el problema de la residuosidad cuadrática , el problema de la inversión RSA y el problema de calcular la permanente de una matriz son problemas aleatorios autorreducibles.
Logaritmo discreto
Teorema : Dado un grupo cíclico G de tamaño | G |. Si un algoritmo de tiempo polinomial determinista A calcula el logaritmo discreto para una fracción 1 / poli ( n ) de todas las entradas (donde n = log | G | es el tamaño de entrada), entonces hay un algoritmo de tiempo polinomial aleatorio para el logaritmo discreto para todos entradas.
Dado un generador g de un grupo cíclico G = { g i | 0 ≤ i <| G | }, y una x ∈ G , el logaritmo discreto de x a la base g es el entero k (0 ≤ k <| G |) con x = g k . Considere que B se distribuye uniformemente en {0, ..., | G | - 1}, y después xg B = g k + B también se distribuye uniformemente sobre G . Por lo tanto, xg B es independiente de x , y su logaritmo se puede calcular con probabilidad 1 / poli ( n ) en tiempo polinomial. Entonces log g x ≡ log g xg B - B (mod | G |) y el logaritmo discreto es autorreducible.
Permanente de una matriz
Dada la definición de la permanente de una matriz, es evidente que PERM ( M ) para cualquier n -by- n matriz M es un polinomio multivariable de grado n sobre las entradas en M . Calcular el permanente de una matriz es una tarea computacional difícil; se ha demostrado que PERM es # P-completo ( prueba ). Además, la capacidad de calcular PERM ( M ) para la mayoría de las matrices implica la existencia de un programa aleatorio que calcula PERM ( M ) para todas las matrices. Esto demuestra que PERM es auto-reducible al azar. La discusión siguiente considera el caso donde las entradas de la matriz se extraen de un campo finito F p para algún primo p , y donde toda la aritmética se realiza en ese campo.
Sea X una matriz aleatoria de n por n con entradas de F p . Dado que todas las entradas de cualquier matriz M + kX son funciones lineales de k , al componer esas funciones lineales con el polinomio multivariado de grado n que calcula PERM ( M ) obtenemos otro polinomio de grado n en k , que llamaremos p ( k ) . Claramente, p (0) es igual a la permanente de M .
Suponga que conocemos un programa que calcula el valor correcto de PERM ( A ) para la mayoría de n- por- n matrices con entradas de F p --- específicamente, 1 - 1 / (3 n ) de ellas. Luego, con una probabilidad de aproximadamente dos tercios, podemos calcular PERM ( M + kX ) para k = 1,2, ..., n + 1. Una vez que tenemos esos valores n + 1, podemos resolver los coeficientes de p ( k ) usando interpolación (recuerde que p ( k ) tiene grado n ). Una vez que conocemos p ( k ) exactamente, evaluamos p (0), que es igual a PERM ( M ).
Si lo hacemos, corremos el riesgo de equivocarnos 1/3 de las veces, pero al elegir varias X aleatorias y repetir el procedimiento anterior muchas veces, y solo proporcionar el ganador mayoritario como respuesta, podemos impulsar la tasa de error. muy bajo.
Consecuencias
- Si un problema NP-completo es auto-reducible al azar no adaptativo, la jerarquía de polinomios colapsa a Σ 3 .
- Si un problema de CoNP-difícil es aleatorio autorreducible en O (log n / n ) entonces Σ 2 = Π 2 .
Referencias
- M. Abadi, J. Feigenbaum y J. Kilian, Sobre la ocultación de información de un oráculo , J. Comput. Syst. Ciencia, 1989
- S. Arora, Alrededor del teorema de la PCP , 1996
- J. Feigenbaum, L. Fortnow, Sobre la autorreductibilidad aleatoria de conjuntos completos , 1991