randomized-algorithms – ¿Cuándo la aleatorización acelera los algoritmos y "no debería"?

Pregunta:

La prueba de Adleman de que $ BPP $ está contenido en $ P / poly $ muestra que si hay un algoritmo aleatorio para un problema que se ejecuta en el tiempo $ t (n) $ en entradas de tamaño $ n $, entonces también hay un algoritmo determinista para el problema que se ejecuta en el tiempo $ \ Theta (t (n) \ cdot n) $ en entradas de tamaño $ n $ [el algoritmo ejecuta el algoritmo aleatorio en $ \ Theta (n) $ cadenas de aleatoriedad independientes. Debe haber aleatoriedad para el algoritmo repetido que sea bueno para todas las entradas posibles de $ 2 ^ n $]. El algoritmo determinista no es uniforme; puede comportarse de manera diferente para diferentes tamaños de entrada. Entonces, el argumento de Adleman muestra que, si a uno no le importa la uniformidad, la aleatorización solo puede acelerar los algoritmos por un factor que es lineal en el tamaño de entrada.

¿Cuáles son algunos ejemplos concretos en los que la aleatorización acelera los cálculos (según nuestro conocimiento)?

Un ejemplo son las pruebas de identidad polinomial. Aquí la entrada es un circuito aritmético de tamaño n que calcula un polinomio variable m sobre un campo, y la tarea es averiguar si el polinomio es idénticamente cero. Un algoritmo aleatorio puede evaluar el polinomio en un punto aleatorio, mientras que el mejor algoritmo determinista que conocemos (y posiblemente el mejor que existe) evalúa el polinomio en muchos puntos.

Otro ejemplo es el árbol de expansión mínimo, donde el mejor algoritmo aleatorio de Karger-Klein-Tarjan es el tiempo lineal (¡y la probabilidad de error es exponencialmente pequeña!), Mientras que el mejor algoritmo determinista de Chazelle se ejecuta en el tiempo $ O (m \ alpha (m , n)) $ ($ \ alpha $ es la función de Ackermann inversa, por lo que la aceleración de la aleatorización es muy pequeña). Curiosamente, Pettie y Ramachandran demostraron que si existe un algoritmo de tiempo lineal determinista no uniforme para el árbol de expansión mínimo, entonces también existe un algoritmo de tiempo lineal determinista uniforme.

¿Cuáles son algunos otros ejemplos? ¿Qué ejemplos conoce en los que la aceleración de la aleatorización es grande, pero esto posiblemente se deba a que aún no hemos encontrado algoritmos deterministas suficientemente eficientes?

Respuesta:

No sé si la aleatorización "debería" o "no debería" ayudar, sin embargo, las pruebas de primalidad de enteros se pueden realizar en el tiempo $ \ tilde O (n ^ 2) $ usando Miller-Rabin aleatorizado, mientras que hasta donde yo sé , los algoritmos deterministas más conocidos son $ \ tilde O (n ^ 4) $ asumiendo GRH (determinista Miller-Rabin) o $ \ tilde O (n ^ 6) $ incondicionalmente (variantes de AKS).

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım