La desrandomización es el concepto general de tomar un algoritmo aleatorio y hacer que no use la aleatoriedad (o menos aleatoriedad). Este es un concepto algo amplio y puede tomar muchas formas.
Un algoritmo aleatorio es un algoritmo que se ejecuta con alguna fuente de aleatoriedad, imagínese el lanzamiento de monedas (o simplemente “bits aleatorios”). Un algoritmo aleatorio se considera “correcto” si produce la respuesta correcta con alta probabilidad (digamos> 99% de probabilidad).
Un algoritmo determinista es un algoritmo que siempre hace lo mismo y siempre da la respuesta correcta.
- ¿Cómo se propagan los gusanos?
- ¿Puedes sugerir algún buen proyecto de Linux para menores de último año?
- ¿UBC, USC o UCI son mejores para la informática de pregrado?
- ¿Cuáles son las preguntas más estimulantes que ha encontrado mientras se preparaba para la informática de GATE?
- ¿Qué tan rápido tendrán que ser las computadoras para descifrar una contraseña de 20 caracteres en un día?
Es crucial que solo requiramos que un algoritmo aleatorio sea correcto el 99% del tiempo. De lo contrario, el concepto era inútil. Por ejemplo, supongamos que teníamos un algoritmo aleatorio que siempre daba la respuesta correcta, con probabilidad 1. Entonces, en particular, el algoritmo daría la respuesta correcta cuando la moneda arroje todos los Jefes. Entonces podríamos hacer un algoritmo determinista que solo finja que todos los lanzamientos de monedas son Caras.
Lo que pasa con los algoritmos aleatorios es que no sabemos qué secuencia de lanzamiento de moneda da como resultado una respuesta correcta. Con un algoritmo aleatorio, se puede demostrar que la mayoría de las secuencias le darán la respuesta correcta (donde la mayoría significa algo preciso, como> 99%, aunque esto puede variar). Pero no puede precisar solo una secuencia aleatoria que funcione.
Aquí hay un ejemplo de un problema computacional en el que un algoritmo aleatorio funciona bien: Prueba de identidad polinómica. La pregunta es: dado un polinomio en [matemáticas] x [/ matemáticas] (descrito como una secuencia arbitraria de operaciones de suma y multiplicación), determine si el polinomio es idénticamente 0. Es demasiado difícil de evaluar como una expresión que involucra [matemáticas] x [/ math], pero es fácil evaluar un valor específico de [math] x [/ math]. Por lo tanto, puede seleccionar aleatoriamente algunos valores [matemática] x [/ matemática] y evaluar el polinomio allí. Si sale a 0 cada vez, entonces la expresión es probablemente idénticamente 0.
Sin embargo, no existe un algoritmo determinista conocido para resolver las pruebas de identidad polinómica.
Otro ejemplo de un problema donde la aleatoriedad ayuda es en la prueba de primalidad (es decir, dado un número, ¿es primo?) Durante un tiempo, solo hubo algoritmos aleatorios para verificar de manera eficiente. En 2002, sin embargo, se encontró la prueba de primalidad AKS, que es determinista. Técnicamente, eso se consideraría un ejemplo de desrandomización. Teníamos algoritmos aleatorios y ahora tenemos un algoritmo determinista. Pero AKS no arroja mucha información sobre los procedimientos generales de aleatorización.
Una pregunta importante en CS teórica pregunta: ¿es posible desrandomizar cualquier algoritmo aleatorio? Más sucintamente, podríamos preguntarnos si P = BPP. P es la clase de problemas que se pueden resolver en tiempo polinómico mediante un algoritmo determinista; BPP es la clase de problemas que se pueden resolver en tiempo polinómico mediante un algoritmo aleatorio. (Oh, supongo que debería mencionar que he estado hablando implícitamente sobre algoritmos de tiempo polinomiales todo este tiempo).
Es posible que esté familiarizado con el famoso problema de P vs NP. Bueno, P vs BPP es un problema difícil como ese, aunque probablemente sea más fácil. De hecho, es probable que P = BPP, mientras que P ≠ NP.
Entonces, ¿ por qué es probable que P = BPP? Bueno, dado un problema en BPP, hay un enfoque bastante convincente para mostrar que también está en P.
Digamos que tengo un problema (como las pruebas de identidad polinómica, o cualquier otra cosa) con un algoritmo aleatorio correcto. Ahora, ejecute su algoritmo, pero en lugar de usar números aleatorios, simplemente use un generador de números pseudoaleatorios (PRG) . Probablemente haya oído hablar de estos si ha utilizado algún lenguaje de programación; por ejemplo, C tiene una función rand que usa un PRG. Un PRG es un algoritmo que genera números que parecen aleatorios, pero que en realidad es determinista. Ejecute el algoritmo con el generador pseudoaleatorio varias veces para una buena medida y tome el resultado más frecuente.
(Este es, yo diría, el enfoque de desrandomización más directo, lo primero en lo que pienso cuando escuché “desrandomización”).
No podemos decir con certeza que esto funcione a menos que tengamos un PRG con ciertas propiedades. La propiedad que queremos es que es imposible distinguir los números aleatorios del PRG de una secuencia aleatoria real. Tales cosas tienen aplicaciones importantes en criptografía. Pero aquí, la razón por la que nos preocupamos es simplemente que si tuviéramos un PRG, entonces debe dar la respuesta correcta cuando se usa en un algoritmo aleatorio correcto, ya que si da una respuesta incorrecta, esa sería una forma de distinguir el PRG de una secuencia aleatoria real!
Por supuesto, la razón por la que no solo mostré que BPP = P es que no se sabe que existan PRG. Este es otro problema difícil. Pero la relación es bastante ordenada. BPP = P es un resultado de “facilidad” (es decir: los problemas de BPP son lo suficientemente “fáciles” como para ser resueltos en tiempo polinómico) pero está implícito en un resultado de “dureza” (es decir: es “difícil” distinguir números pseudoaleatorios de números al azar).
Puedes ver esta sección de Wikipedia para algunos detalles. El interesante es el resultado Impagliazzo-Wigderson que dice que BPP = P si las funciones de tiempo exponencial tienen una complejidad de circuito suficientemente grande. Esencialmente, usan este hecho para construir un generador con buenas propiedades.
—————
La desrandomización no se refiere solo a la creación de algoritmos completamente deterministas. Reducir la cantidad de aleatoriedad necesaria también es un área de estudio. (Nota: si puede reducir el número de bits a O (log n), inmediatamente obtiene un algoritmo de tiempo polinomial determinista: puede probar todas las cadenas de bits al azar posibles).
Un área divertida en este tema es la amplificación determinista .
La amplificación, por sí sola, es simplemente el proceso de tomar un algoritmo aleatorio y hacer que su probabilidad de error sea mucho menor. Esto es bastante fácil de hacer: simplemente ejecute el algoritmo varias veces y tome la respuesta más frecuente. La probabilidad de error crecerá exponencialmente pequeña. (Pronto estará más preocupado por la falla de su computadora que de que su nuevo algoritmo dé el resultado incorrecto). Pero si el algoritmo original requiere r bits aleatorios, y lo ejecuta k veces, terminará usando rk random bits en total
¿Podemos hacerlo mejor que eso? ¿Podemos mejorar la probabilidad de error con solo un poco más de r bits? Resulta que podemos. La idea es ejecutar nuestro algoritmo k veces como antes, pero en lugar de generar r bits aleatorios cada vez, podemos “reciclar” bits aleatorios entre ejecuciones.
Por supuesto, tenemos que tener mucho cuidado con esto para que funcione. Ahora, las diferentes ejecuciones del algoritmo ya no son independientes, por lo que el análisis directo no funcionará. Tienes que generar tus entradas aleatorias de una manera especial usando algo aleatorio en estas cosas llamadas gráficas expansivas. Los gráficos expansores son un tema fascinante en el que realmente no tengo espacio para entrar aquí. (También se utilizan en los resultados que mencioné anteriormente). Este documento: Cómo reciclar bits aleatorios describe los detalles. (Estos resultados son mucho más fáciles que los de P vs BPP anteriores, y tampoco se basan en suposiciones no comprobadas).
