Problemas en P con algoritmos aleatorios probablemente más rápidos

¿Hay algún problema en que tenga algoritmos aleatorios que superen los límites inferiores en algoritmos deterministas? Más concretamente, ¿conocemos alguna para la cual ? Aquí significa el conjunto de idiomas que puede decidir una TM aleatorizada con un error constante (uno o dos lados) en pasos de . $\mathsf{P}$ $k$ $\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)$ $\mathsf{PTIME}(f(n))$ $f(n)$

¿La aleatoriedad nos compra algo dentro de $\mathsf{P}$ ?

Para ser claros, estoy buscando algo donde la diferencia sea asintótica (preferiblemente polinomial, pero me conformaría con el pollogarítmico), no solo una constante.

Estoy buscando algoritmos asintóticamente mejores en el peor de los casos. Algoritmos con mejor complejidad esperada no son lo que estoy buscando. Me refiero a algoritmos aleatorios como en RP o BPP, no en ZPP.

algorithms complexity-theory randomized-algorithms aelguindy
fuente

Quizás "la técnica de Yao" es lo que estás buscando. Se puede encontrar una breve descripción en cs.pitt.edu/~kirk/cs2150/yao/yao.html

Wu Yin

@WuYin si entiendo correctamente que va en la dirección de algoritmos aleatorios de límite inferior por el comportamiento promedio de los casos del algoritmo determinista ... Lo investigaré más a fondo, pero tal como lo veo, esto solo podría conducir a probar esa aleatoriedad no no nos comprar cualquier cosa dentro de

P

$P$ .. Estoy en lo correcto?

aelguindy

Para encontrar cualquier elemento en secuencia de longitud

n

$n$ con rango en [

\frac{n}{4}

$\frac{n}{4}$ ,

\frac{3 * n}{4}

$\frac{3*n}{4}$ ] simplemente podemos devolver cualquier elemento aleatorio y será correcto con

\frac{1}{2}

$\frac{1}{2}$ probabilidad por lo tanto su O (1)! Mientras que un algoritmo determinista examinaría al menos alguna fracción de la entrada y, por lo tanto,

Ω (n)

$\Omega(n)$ .

rizwanhudda

@rizwanhudda Puede haber algunos problemas con eso. Primero, estoy buscando un problema de decisión. En segundo lugar, en el modelo de Turing, devolver un elemento aleatorio es , ya que no hay acceso aleatorio. Tal vez, ¿la máquina siempre emite el primer elemento? Aún así, el primer problema es más grande.

Ω (n)

$\Omega (n)$

aelguindy

El último párrafo no tiene sentido porque cada algoritmo de Las Vegas se puede convertir en un algoritmo de Monte Carlo.

Tsuyoshi Ito

Respuestas:

La prueba de identidad polinómica admite un algoritmo de tiempo polinómico aleatorio (vea el lema de Schwartz-Zippel ), y actualmente no tenemos un tiempo polinómico determinista o incluso un algoritmo de tiempo sub-exponencial para ello.

Evaluación del árbol del juego Considere un árbol binario completo connodos de hoja, cada uno de los cuales almacena un valor 0/1. Los nodos internos contienen compuertas OR / AND en niveles alternativos. Puede probarse usando argumentos adversos que cada algoritmo determinista tendría que examinarnodos de hoja en el peor de los casos. Sin embargo, hay un algoritmo aleatorio simple que tomael tiempo de ejecución esperado de Mire las diapositivas 14-27 de la charla. $n$ $\Omega{(n)}$ $O(n^{0.793})$

Ruteo inconsciente en un hipercubo Considere un cubo en-dimensiones que contiene vértices. Cada vértice tiene un paquete de datos y un destino al que desea entregar el paquete. El destino de todos los paquetes es diferente. Incluso para esto, se ha demostrado que cualquier estrategia de enrutamiento determinista tomaría lospasos. Sin embargo, existe una estrategia aleatoria simple que terminará enpasos esperados con alta probabilidad . $n$ $N=2^n$ $\Omega{\big(\sqrt{\frac{N}{n}}\big)}$ $O(n)$

Tenga en cuenta que en algoritmos aleatorios, el costo esperado con alta probabilidad (como por ejemplo, ) es equivalente al peor de los casos en la práctica. $E(F(n))$ $Pr[F(n) > 10 \cdot E(F(n))] < \frac{1}{n^2}$

rizwanhudda
fuente

Además, considere la prueba para las matrices , y si . Actualmente no conocemos el algoritmo , conocemos un algoritmo aleatorio . El punto es, ¿hay problemas para los cuales podamos probar que los algoritmos aleatorios son mejores?

A

$A$

B

$B$

C

$C$

A B = C

$A B = C$

o (2^{2.3})

$o(2^{2.3})$

O (n^{2})

$O(n^2)$

aelguindy

@aelguindy entiendo tu punto. Pero, para PIT, el algoritmo determinístico más conocido es exponencial. Y, desrandomizar PIT es un importante problema abierto en CS teórico.

rizwanhudda

He agregado la evaluación del árbol de juegos y el enrutamiento de hipercubos a la publicación, para lo cual los algoritmos aleatorios funcionan mejor que los equivalentes determinísticos.

rizwanhudda

OK, para la evaluación de Game Tree, si entiendo correctamente, se ejecuta en esperado , ¿verdad? Quiero decir que hay casos en los que se ejecutará en . ¿Es el caso con el tercer ejemplo también? No estoy permitiendo un mejor tiempo esperado, estoy buscando una mejor complejidad en el peor de los casos, error permitido en la salida.

O (n^{0.793})

$O(n^{0.793})$

Ω (n)

$\Omega(n)$

aelguindy

Entonces no son mejores en el peor de los casos. Por mucho que aprecie los ejemplos, me temo que no es exactamente lo que estoy buscando. ¡Sin embargo, los ejemplos fueron muy esclarecedores!

aelguindy

Investigar el peor de los casos no tiene sentido para los algoritmos aleatorios. No solo el tiempo de ejecución del peor de los casos será a menudo infinito, sino que tampoco pueden superar a los algoritmos deterministas en esa métrica.

Considere cualquier algoritmo aleatorio . Obtenga un algoritmo determinista fijando la cinta aleatoria de a . Entonces, para todo . $A$ $B$ $A$ $0^\infty$ $T_B(n) \leq T_A(n)$ $n$

Rafael
fuente

Hay muchos problemas en los que sabemos de un algoritmo aleatorio eficiente, y no sabemos de ningún algoritmo determinista que podamos probar que sea eficiente. Sin embargo, esto puede reflejar deficiencias en nuestra capacidad para probar cosas sobre la complejidad en lugar de cualquier diferencia fundamental.

Según su comentario , parece que quería preguntar si existe algún problema cuando existe un algoritmo aleatorio eficiente, y podemos demostrar que no existe un algoritmo determinista de eficiencia comparable. No sé de tal problema.

De hecho, hay motivos razonables para sospechar que es probable que tales problemas no existan. Heurísticamente, la existencia de tal problema probablemente significaría que la criptografía segura es imposible. Eso parece un resultado bastante inverosímil.

¿Cuál es la conexión, preguntas? Bueno, considere cualquier algoritmo aleatorio que resuelva algún problema de manera eficiente. Se basa en monedas aleatorias: bits aleatorios obtenidos de una fuente aleatoria verdadera. Ahora supongamos que tomamos un generador pseudoaleatorio de calidad criptográfica y reemplazamos la fuente aleatoria verdadera con la salida del generador pseudoaleatorio. Llame al algoritmo resultante . Tenga en cuenta que es un algoritmo determinista y su tiempo de ejecución es aproximadamente la misma que . $A$ $A'$ $A'$ $A$

Además, si el PRNG criptográfico es seguro, heurísticamente deberíamos esperar que sea un buen algoritmo si es: $A'$ $A$

Por ejemplo, si es un algoritmo de Las Vegas (siempre genera la respuesta correcta y termina rápidamente con alta probabilidad), entonces será un algoritmo determinista bastante bueno (siempre genera la respuesta correcta y termina rápidamente para la mayoría de las entradas) . $A$ $A'$
Como otro ejemplo, si es un algoritmo de Monte Carlo (tiempo de ejecución determinista, y genera la respuesta correcta con una probabilidad de al menos ), entonces será un algoritmo determinista bastante bueno (tiempo de ejecución determinista, y genera la respuesta correcta) en una fracción de todas las entradas). $A'$ $1-\varepsilon$ $A$ $1-\varepsilon$

Por lo tanto, si el PRNG criptográfico es seguro y hay un algoritmo aleatorio eficiente, obtienes un algoritmo determinista que es bastante bueno. Ahora hay muchas construcciones de PRNG criptográficos que se garantiza que son seguras si se cumplen ciertos supuestos criptográficos. En la práctica, esos supuestos criptográficos se creen ampliamente: al menos, el comercio y las transacciones seguras dependen de que sean ciertos, por lo que aparentemente estamos dispuestos a apostar grandes sumas de dinero a que existe una criptografía segura. La única forma en que esta transformación puede fallar es si el PRNG criptográfico no existe, lo que a su vez implica que la criptografía segura es imposible. Si bien no tenemos ninguna prueba de que este no sea el caso, parece un resultado poco probable.

Detalles de la construcción: así es como funciona . En la entrada , se deriva una semilla para el PRNG criptográfica como una función de (por ejemplo, por hashing ), y luego simula , utilizando la salida del PRNG criptográfica como las monedas para . Por ejemplo, una instanciación específica sería establecer , luego usar como semilla para AES256 en modo contador, o alguna otra PRNG criptográfica. Podemos probar las declaraciones anteriores bajo el modelo de oráculo aleatorio. $A'$ $x$ $x$ $x$ $A(x)$ $A$ $k=\text{SHA256}(x)$ $k$

Si no está satisfecho con la idea de que pueda generar resultados incorrectos en una pequeña fracción de las entradas, eso puede abordarse. Si repites varias veces y tomas un voto mayoritario, la probabilidad de error disminuye exponencialmente rápido en el número de iteraciones. Por lo tanto, iterando un número constante de veces, se puede obtener la probabilidad de error para estar por debajo de , lo que significa las posibilidades de que se ejecuta a través de una entrada $A'$ $A'$ $\varepsilon$ $1/2^{256}$ $x$ donde el algoritmo genera la respuesta incorrecta son muy pequeñas (menos que las posibilidades de ser alcanzado por un rayo varias veces seguidas). Además, con la construcción que di anteriormente, las posibilidades de que un adversario pueda encontrar una entrada donde da la respuesta incorrecta pueden hacerse muy pequeñas, ya que eso requeriría romper la seguridad del hash SHA256. (Técnicamente, esto requiere que el modelo de oráculo aleatorio se justifique, por lo que significa que debe ser elegido para ser "independiente" de SHA256 y no codificar en él los cálculos relacionados con SHA256, pero casi todos los algoritmos del mundo real satisfarán ese requisito .) $x$ $A'$ $A$

Si desea una base teórica más fuerte, se puede iterar veces, y obtener la probabilidad de error a estar por debajo de , donde es la longitud de la entrada . Ahora la fracción de entradas -bit donde da una respuesta incorrecta es estrictamente menor que . Pero solo hay posibles entradas de bits, y en cada una es correcta o incorrecta, por lo que se deduce que no hay entrada donde $A$ $\Theta(n)$ $1/2^n$ $n$ $x$ $n$ $A'$ $1/2^n$ $2^n$ $n$ $A$ $A'$ es incorrecto: es correcto en todas las entradas, y esto se cumple incondicionalmente. Si corre en el tiempo , entonces corre en el tiempo , entonces es un poco más lento que pero no demasiado lento. Este es el contenido de la prueba de Adleman de que BPP está contenido en P / poli. Para fines prácticos, esto probablemente sea exagerado, pero si le gustan las pruebas limpias que evitan los supuestos criptográficos o si lo aborda desde la perspectiva de un teórico, entonces puede que le guste más esta versión. $A'$ $A$ $t(n)$ $A'$ $\Theta(n \cdot t(n))$ $A'$ $A$

Para obtener más detalles sobre las últimas consideraciones teóricas y problemas adicionales en los que conocemos un algoritmo aleatorio eficiente pero no conocemos ningún algoritmo determinista que podamos probar que sea eficiente, consulte /cstheory//q/31195 / 5038

En resumen: para cualquier problema en el que conocemos un algoritmo aleatorio eficiente, también conocemos un algoritmo determinista que probablemente sea eficiente en la práctica, pero en la actualidad no sabemos cómo demostrar que es eficiente. Una posible interpretación es que simplemente no somos muy buenos para probar cosas sobre algoritmos.

DW
fuente