La prueba de Adleman de que está contenido en muestra que si hay un algoritmo aleatorio para un problema que se ejecuta en el tiempo en entradas de tamaño , entonces también hay un algoritmo determinista para el problema que se ejecuta en el tiempo en entradas de tamaño [el algoritmo ejecuta el algoritmo aleatorio en cadenas de aleatoriedad independientes . Debe haber aleatoriedad para el algoritmo repetido que es bueno para todosP / p o l y t ( n ) n Θ ( t ( n ) ⋅ n ) n Θ ( n ) 2 nposibles entradas]. 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 donde la aleatorización acelera la computación (según nuestro conocimiento)?
Un ejemplo es la prueba de identidad polinómica. Aquí la entrada es un circuito aritmético de tamaño n que computa un polinomio de variante 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 ( es la función inversa de Ackermann, por lo que la aceleración de la aleatorización es realmente pequeña). Curiosamente, Pettie y Ramachandran demostraron que si hay un algoritmo de tiempo lineal determinista no uniforme para un á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 sabe donde la aceleración de la aleatorización es grande, pero esto es posiblemente solo porque todavía no hemos encontrado algoritmos deterministas suficientemente eficientes?
fuente
Respuestas:
No sé si la aleatorización "debería" o "no debería" ayudar, sin embargo, la prueba de primalidad de enteros se puede hacer a tiempo usando Miller – Rabin aleatorizado, mientras que, hasta donde yo sé, el Los algoritmos deterministas más conocidos son suponiendo GRH (determinista Miller – Rabin) o incondicionalmente (variantes de AKS). ˜ O (n4) ˜ O (n6)O~( n2) O~( n4 4) O~( n6 6)
fuente
Un viejo ejemplo es el cálculo de volumen. Dado un politopo descrito por un oráculo de membresía, hay un algoritmo aleatorio que se ejecuta en tiempo polinómico para estimar su volumen a un factor , pero ningún algoritmo determinista puede acercarse incluso incondicionalmente .1 + ϵ
El primer ejemplo de dicha estrategia aleatoria fue Dyer, Frieze y Kannan, y el resultado de dureza para algoritmos deterministas es Bárány y Füredi. Alistair Sinclair tiene buenas notas de lectura sobre esto .
No estoy seguro de entender completamente la parte "y no debería" de la pregunta, así que no estoy seguro de que esto se ajuste a la factura.
fuente
No sé si esto responde a su pregunta (o al menos parte de ella). Pero para los ejemplos del mundo real donde la aleatorización puede proporcionar una aceleración está en los problemas de optimización y la relación con el teorema de No Free Lunch ( NFL ) .
Hay un documento "Quizás no un almuerzo gratis, sino al menos un aperitivo gratis" donde se demuestra que el uso de la asignación al azar, los algoritmos (de optimización) pueden tener un mejor rendimiento.
Referencias
Resumen sobre almuerzos gratuitos (y almuerzos gratis) por David H. Wolpert, ¿Cuánto cuesta la cena? ( tenga en cuenta que los teoremas de tipo NFL nunca especifican un " precio " real debido a su tipo de prueba)
Específicamente para la optimización generalizada (GO):
Finalmente, una observación simple (y no tan simple) de por qué la aleatorización (de una forma u otra) puede proporcionar un rendimiento superior sobre algoritmos estrictamente deterministas.
fuente
El mejor ejemplo es en el área considerada actualmente como los mejores candidatos para OWF, donde parece que cada OWF popular que se prepara sorprendentemente tiene un algoritmo sub-exponencial aleatorio, mientras que no existe un algoritmo sub-exponencial determinista (tome la factorización entera por ejemplo). De hecho, en muchos casos, probablemente exista un algoritmo eficiente dado algunas cadenas de consejos (criptoanálisis).
fuente
Si tiene un algoritmo que usa la asignación al azar, siempre puede reemplazarlo con un algoritmo determinista que usa números pseudoaleatorios: tome la descripción del problema, calcule un código hash, use ese código hash como la semilla de un buen generador de números pseudoaleatorios . En la práctica, eso es lo que probablemente sucederá cuando alguien implemente un algoritmo utilizando la asignación al azar.
Si omitimos el código hash, la diferencia entre este algoritmo y un algoritmo que utiliza la asignación al azar verdadera es que puedo predecir la secuencia de números aleatorios generados, y podría producir un problema de tal manera que el número aleatorio predicho aplicado a mi problema siempre tomar la peor decisión posible Por ejemplo, para Quicksort con un pivote pseudoaleatorio, podría construir una matriz de entrada donde el pivote pseudoaleatorio siempre encuentre el mayor valor posible en la matriz. Con una verdadera aleatoriedad que no es posible.
Con el código hash, sería muy difícil para mí construir un problema donde los números pseudoaleatorios producen peores resultados. Todavía puedo predecir los números aleatorios, pero si cambio el problema, la secuencia de números pseudoaleatorios cambia completamente. Aún así, sería casi imposible para ti demostrar que no puedo construir tal problema.
fuente