La autorreducibilidad aleatoria ( RSR ) es la regla según la cual un buen algoritmo para el caso promedio implica un buen algoritmo para el peor caso. RSR es la capacidad de resolver todas las instancias de un problema resolviendo una fracción grande de las instancias.
Si para una función f que evalúa cualquier instancia x puede reducirse en tiempo polinomial a la evaluación de f en una o más instancias aleatorias y i , entonces es autoreducible (esto también se conoce como una autorreducción uniforme no adaptativa ). En una autorreducción aleatoria, una instancia arbitraria del peor caso 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 ) pueda calcularse 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 del caso promedio de f es la misma (dentro de los factores polinomiales) que la complejidad aleatoria del peor caso de f .
Un caso especial que vale la pena mencionar 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 lo es en el peor de los casos. Este enfoque contiene dos restricciones clave. Primero, la generación de y 1 , ..., y k se realiza de manera no adaptativa. Esto significa que y 2 se elige antes de que se conozca f ( y 1 ). Segundo, no es necesario que los puntos y 1 , ..., y k estén distribuidos uniformemente.
Los problemas que requieren cierta privacidad en los datos (normalmente, los problemas criptográficos ) pueden utilizar la aleatorización para garantizar dicha privacidad. De hecho, el único sistema criptográfico demostrablemente seguro (el block de un solo uso ) tiene su seguridad basada totalmente en la aleatoriedad de los datos clave suministrados al sistema.
El campo de la criptografía aprovecha el hecho de que ciertas funciones de la teoría de números son aleatoriamente autorreducibles. Esto incluye el cifrado probabilístico y la generación de números pseudoaleatorios criptográficamente fuertes . Además, los esquemas de ocultamiento de instancias (donde un dispositivo privado débil utiliza un dispositivo público fuerte sin revelar sus datos) se ejemplifican fácilmente mediante autorreducciones aleatorias.
El problema del logaritmo discreto , el problema de residuosidad cuadrática , el problema de inversión RSA y el problema de calcular la permanente de una matriz son problemas aleatorios autorreducibles.
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/poly( n ) de todas las entradas (donde n = log | G | es el tamaño de la entrada), entonces hay un algoritmo de tiempo polinomial aleatorio para el logaritmo discreto para todas las entradas.
Dado un generador g de un grupo cíclico G = { g i | 0 ≤ i < | G | }, y un x ∈ G , el logaritmo discreto de x en base g es el entero k (0 ≤ k < | G |) con x = g k . Supongamos que B se distribuye uniformemente en {0,...,| G | − 1}, entonces xg B = g k + B también se distribuye uniformemente en G . Por lo tanto, xg B es independiente de x , y su logaritmo se puede calcular con probabilidad 1/poly( n ) en tiempo polinomial. Entonces log g x ≡ log g xg B - B (mod | G |) y el logaritmo discreto es autoreducible.
Dada la definición de la permanente de una matriz, es claro que PERM ( M ) para cualquier matriz n -por- n M es un polinomio multivariado de grado n sobre las entradas en M . Calcular la 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 aleatorio auto-reducible. La discusión a continuación considera el caso donde las entradas de la matriz se extraen de un cuerpo finito F p para algún primo p , y donde toda la aritmética se realiza en ese cuerpo.
Sea X una matriz aleatoria n por n con entradas de F p . Como 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 sobre k , al que llamaremos p ( k ). Claramente, p (0) es igual a la permanente de M .
Supongamos que conocemos un programa que calcula el valor correcto de PERM ( A ) para la mayoría de las matrices n -por- n con entradas de F p ---específicamente, 1 − 1/(3 n ) de ellas. Entonces, con una probabilidad de aproximadamente dos tercios, podemos calcular PERM ( M + kX ) para k = 1,2,..., n + 1. Una vez que tenemos esos n + 1 valores, 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 así, corremos el riesgo de equivocarnos 1/3 del tiempo, pero al elegir múltiples X al azar y repetir el procedimiento anterior muchas veces, y solo proporcionar el ganador de la mayoría como respuesta, podemos reducir la tasa de error a un nivel muy bajo.