Algoritmo aleatorizado que "parece" determinista?

31

¿Hay un ejemplo interesante de un algoritmo aleatorio para un problema de búsqueda que siempre genera la misma respuesta (correcta), independientemente de su aleatoriedad interna, pero que explota la aleatoriedad para que su tiempo de ejecución esperado sea mejor que el tiempo de ejecución del más rápido conocido algoritmo determinista para el problema?

En particular, me preguntaba si existe un algoritmo para encontrar un primo entre n y 2n. No se conoce un algoritmo determinista de tiempo polinómico. Hay un algoritmo aleatorio trivial que funciona simplemente muestreando enteros aleatorios en el intervalo, que funciona gracias al teorema de los números primos . ¿Pero hay un algoritmo del tipo anterior cuyo tiempo de ejecución esperado es intermedio entre los dos?

EDITAR: Para refinar mi pregunta un poco, quería un algoritmo de este tipo para un problema en el que hay muchas salidas correctas posibles y, sin embargo, el algoritmo aleatorio se instala en uno independiente de su aleatoriedad. Me doy cuenta de que la pregunta probablemente no está completamente especificada ...

arnab
fuente
3
Para darle algunas palabras clave de búsqueda, los algoritmos aleatorios que siempre producen la respuesta correcta (y utilizan la aleatoriedad para un tiempo de ejecución más corto) se denominan algoritmos de Las Vegas (a diferencia de los algoritmos de Monte Carlo) o algoritmos de error cero, y una clase de complejidad relacionada es ZPP .
Tsuyoshi Ito
@ Tsuyoshi: Gracias por tu comentario. Pero no conozco los algoritmos de tipo Las Vegas para problemas de búsqueda. Esta es mi pregunta
arnab
Si hay un algoritmo aleatorio para encontrar equilibrios únicos de Nash que respondería a su pregunta.
Warren Schudy el
¿Quizás haya algún problema relacionado con los ataques de cumpleaños ( en.wikipedia.org/wiki/Birthday_attack ) que se ajuste a sus requisitos?
Warren Schudy 01 de

Respuestas:

23

¡Shafi Goldwasser me comunicó que ella y sus coautores han estado investigando exactamente tales algoritmos para problemas de teoría de números! Se sabe lo siguiente:

  1. Lenstra ha demostrado que existe un algoritmo de este tipo para encontrar una modificación cuadrática sin residuos de un primo dado.

  2. Gat y Goldwasser han demostrado que existe un algoritmo para encontrar un generador de , donde p es un primo dado de la forma 2 q + 1 para un primo q .Zpp2q+1q

(No sé de referencias citables.) También hay investigaciones en curso sobre la pregunta que hice sobre la búsqueda de un primo entre y 2 n .n2n

EDITAR: El documento de Gat y Goldwasser ahora se publica: http://eccc.hpi-web.de/report/2011/136/ . Sin embargo, este documento no resuelve la cuestión de encontrar un primo entre y 2 n .n2n

revs arnab
fuente
1
Virtual +1. Esto es realmente interesante, buscará el periódico.
András Salamon
2
A pesar de la nota, voté por esta respuesta simplemente porque esta es una buena respuesta. No creo que haya nada malo en votar una buena respuesta publicada para otra persona. Comencé una discusión sobre Meta sobre esto.
Tsuyoshi Ito
1
Eliminé la nota y la hice "wiki de la comunidad" según la discusión sobre el meta hilo.
arnab
El meta hilo mencionado por arnab se puede encontrar aquí: meta.cstheory.stackexchange.com/q/607/873 .
MS Dousti
18

¿Cuentan las estructuras de datos aleatorizados?

Existe la lista de omisión que es una estructura de datos de mapa asociativo ordenado.

Su tiempo de ejecución para operaciones comunes como la inserción, recuperación y eliminación están (en el caso esperado) a la par con las de los árboles de búsqueda equilibrados, es decir, . Sin embargo, a veces se afirma que la estructura de datos tiene un factor constante mucho mejor que las implementaciones del árbol de búsqueda cuando se realiza correctamente (esto se basa fundamentalmente en una fuente buena y eficiente de aleatoriedad). El mejor factor constante probablemente sea el resultado del hecho de que no debe realizarse un reequilibrio (o cualquier operación similar).O(logn)

Konrad Rudolph
fuente
¡Gracias! Esto definitivamente cuenta y es una respuesta no trivial a mi pregunta original. Quería un problema, aunque más análogo al problema de búsqueda principal, donde hay muchas soluciones potenciales.
arnab
Agregue listas de salto a ese tren de pensamiento.
Raphael el
13

¿Qué tal el algoritmo simplex de tiempo polinómico aleatorio de Kelner y Spielman? Encuentra el vértice óptimo de un programa lineal. No se conoce un algoritmo determinista simplex que se pruebe que se ejecute en tiempo polinómico, y para muchos de ellos, se pueden construir instancias patológicas que hagan que el algoritmo tome tiempo exponencial.

Por supuesto, hay algoritmos de punto interior de tiempo polinómico, por lo que no es exactamente lo que está buscando.

Peter Shor
fuente
Si hay varios puntos óptimos, ¿Kelner-Spielman siempre devolvería el mismo punto?
Sasho Nikolov
3
Los programas lineales genéricos tienen solo un punto óptimo, por lo que, utilizando la perturbación, se puede hacer una variante de Kelner-Spielman que siempre devuelve el mismo punto óptimo.
Peter Shor
12

2nn2n

2n1

¿Esto califica?

András Salamon
fuente
¡¡Agradable!! Esto definitivamente califica, aunque estaba buscando un ejemplo más trivial donde la mejora en el tiempo de ejecución es más sustancial.
arnab
No necesita la estructura de árbol, esto funciona en una matriz.
sdcvvc
7

Fplogpp

logp

Srikanth
fuente
3

Con respecto a su primera pregunta, pensé en Quicksort primero, pero eso debería ser obvio.

Hay un algoritmo de coincidencia de cadenas ( Nebel, 2006 ) que usa ideas probabilísticas. Sin embargo, sí sé si este es el enfoque más rápido existente, y aparentemente necesita algunas muestras para la capacitación.

Rafael
fuente
La búsqueda de la mediana también es más rápida, pero no dramáticamente.
Aram Harrow
3

El siguiente documento de STACS '97 podría ser interesante para su caso: La complejidad de generar instancias de prueba .

Resumen: Recientemente, Watanabe propuso un nuevo marco para probar la corrección y el comportamiento promedio de los algoritmos que pretenden resolver un problema de búsqueda de NP de manera eficiente en promedio. La idea es generar al azar instancias certificadas de una manera que se parezca a la distribución subyacente. Discutimos este enfoque y mostramos que se pueden generar instancias de prueba para cada problema de búsqueda de NP con consultas no adaptativas a un oráculo de NP. Además, presentamos los generadores de instancias de prueba de Las Vegas y Monte Carlo y mostramos que estos generadores se pueden usar para averiguar si un algoritmo es correcto y eficiente en promedio. De hecho, no es difícil construir generadores Monte Carlo para todos los problemas de búsqueda de RP, así como generadores de Las Vegas para todos los problemas de búsqueda de ZPP. Por otra parte,

Especialmente, eche un vistazo a la página 384, en el Corolario 12:

ZPPRPZPPNPNPcoNP

MS Dousti
fuente
2

1ncpolylog(n)

Ramprasad
fuente
3
Esto se refiere a probar y no encontrar ...
Dana Moshkovitz
Estaba más interesado en los problemas de búsqueda. Para problemas de decisión, hay algoritmos de Las Vegas.
arnab