Ejemplos de desrandomización exitosa de BPP a P

¿Cuáles son algunos ejemplos importantes de desrandomización exitosa o al menos progreso en mostrar evidencia concreta hacia el objetivo (no la conexión de aleatoriedad de dureza)? $P=BPP$

El único ejemplo que me viene a la mente es la prueba de primitiva de tiempo polinomial determinista de AKS (incluso para esto había una metodología que suponía GRH). Entonces, ¿qué evidencia específica a través del ejemplo tenemos para la aleatorización (de nuevo, no la dureza o la conexión del oráculo)?

Guarde ejemplos solo donde la mejora de la complejidad del tiempo se mostró de polietileno aleatorizado a poli determinista o algo que está muy cerca de problemas específicos.

Lo siguiente es más un comentario y no sé mucho, ayudará a esta consulta.

Chazelle tiene una declaración muy intrigante en http://www.cs.princeton.edu/~chazelle/linernotes.html bajo 'El método de discrepancia: aleatoriedad y complejidad (Cambridge University Press, 2000)'.

'Para mí ha sido una fuente interminable de fascinación que una comprensión más profunda de la computación determinista requiera el dominio de la aleatorización. Escribí este libro para ilustrar esta poderosa conexión. Desde los árboles de expansión mínima hasta la programación lineal y las triangulaciones de Delaunay, los algoritmos más eficientes son a menudo las aleatorizaciones de las soluciones probabilísticas. El método de discrepancia pone de relieve una de las preguntas más fructíferas en toda la informática: si cree que necesita bits aleatorios, díganos por qué.

cc.complexity-theory big-list randomized-algorithms derandomization pseudorandom-generators
fuente

Muchos algoritmos pueden ser aleatorizados usando técnicas generales como el método de expectativas condicionales, el método de estimadores pesimistas y el uso de espacios de muestra de independencia acotada. De hecho, las pruebas de primalidad y las pruebas de identidad polinomial son tan famosas porque son ejemplos raros de funciones naturales que resisten las técnicas de desradiación estándar.

Sasho Nikolov

@SashoNikolov gracias, puede ser que el comentario podría ampliarse como una respuesta completa en algunos ejemplos. Además, ¿es la conexión dureza-aleatoriedad a través de la complejidad del circuito la única razón por la que las personas creen que

P = B P P

$P=BPP$

Creo que esto es demasiado básico para una respuesta. Vea el capítulo sobre desrandomización en Alon-Spencer para obtener detalles y ejemplos: cubre las tres técnicas que mencioné.

Sasho Nikolov el

Lo interesante de la clase BPP es que su definición teórica requiere bits de entrada aleatorios que pueden mostrarse fácilmente, utilizando desaleatorización y medidas de aleatoriedad débil de kolomogrov, para que no existan en dominios finitos. No sé cómo las personas pueden vivir con esta inconsistencia. Yo mismo no creo que haya una clase explícita BPP (es NP o P).

Respuestas:

. $SL = L$

significa logspace aleatorizado y es una versión más pequeña del problema . Una piedra importante paso a paso fue la prueba de Reingold en '04 ( "no dirigido ST Conectividad en LOGSPACE") que , donde significa "simétrica" y es una clase intermedia entre y . $RL$ $RL=L$ $RP=P$ $SL = L$ $S$ $SL$ $RL$ $L$

La idea es pensar en una máquina Turing de espacio de registro aleatorio como un gráfico dirigido de tamaño polinómico, donde los nodos son estados de la máquina, y un algoritmo RL realiza un recorrido aleatorio que tiene buenas propiedades. SL corresponde a gráficos no dirigidos de esta forma. La prueba de Reingold se basó en el trabajo en gráficos expansores, en particular el "producto en zigzag" de Reingold, Vadhan y Wigderson, para realizar cualquier recorrido aleatorio en un gráfico no dirigido con buenas propiedades y convertirlo en un recorrido psuedorandom que conserve esas propiedades.

editar esta pregunta se publicó antes de que la pregunta se cambiara explícitamente para enfocarse exclusivamente en P vs BPP ... Lo dejo porque parece ser de interés.

usul
fuente

Por favor no La respuesta es interesante.

Emil Jeřábek apoya a Monica

Hola, @Student., Creo que las personas que lleguen a la pregunta interesadas en ejemplos de desrandomización exitosa estarán interesadas en esta respuesta, por lo que la guardaré, sin que eso signifique falta de respeto a sus objetivos (que solo se editaron más tarde para especificar la complejidad del tiempo ... )

usul

También debo decir que las preguntas y respuestas en este sitio deben formularse de manera que sean generalmente útiles para futuros visitantes como un recurso de referencia, no solo para satisfacer los objetivos particulares del póster. Por mi parte, la pregunta sin restricciones artificiales a la complejidad del tiempo y BPP es mucho más útil.

Emil Jeřábek apoya a Monica el

@ EmilJeřábek Ok, gracias, dejaremos la publicación de usul como está aquí.

@usul 'La idea es que se pueda pensar en una máquina Turing de espacio de registro aleatorio como un gráfico dirigido de tamaño polinómico'. ¿Existe una intuición adecuada que funcione para NL? Sé que L no es NL se conjetura, pero PSPACE = NPSPACE y, por lo tanto, el espacio puede ser diferente al tiempo.

T ....

Básicamente, solo hay un problema interesante en BPP que no se conoce en P: Prueba de identidad polinómica, dado que un circuito algebraico es el polinomio que genera idénticamente cero. Impagliazzo y Kabanets muestran que PIT en P implicaría algunos límites inferiores del circuito. Entonces, los límites inferiores del circuito son la única razón (pero bastante buena) por la que creemos que P = BPP.

Lance Fortnow
fuente

Si bien estoy de acuerdo con usted en un alto nivel, creo que la gran cantidad de algoritmos aleatorios en la teoría de grupos computacionales sugieren otra clase muy unida de preguntas interesantes de desrandomización, que no parecen reducirse a PIT. Si bien la mayoría de estos son funciones en lugar de problemas de decisión, algunos de ellos se pueden reformular como problemas de decisión interesantes en BPP, por ejemplo, cstheory.stackexchange.com/a/11440/129

Joshua Grochow el

O (f (n))

$O(f(n))$

O (f (n))

$O(f(n))$

B P P

$BPP$

B P P

$BPP$

f (n)

$f(n)$

P = B P P

$P=BPP$

Además de la prueba de identidad polinómica, otro problema muy importante que se sabe que está en BPP pero no en P es aproximar el permanente de una matriz no negativa o incluso el número de coincidencias perfectas en un gráfico. Hay un algoritmo aleatorio de tiempo múltiple para aproximar estos números dentro de un factor (1 + eps), mientras que los mejores algoritmos deterministas solo alcanzan aproximaciones de factor ~ 2 ^ n.

Si bien el ejemplo principal es permanente, existen muchos problemas de conteo aproximados para los cuales existe una gran brecha entre los algoritmos aleatorios (generalmente basados en métodos 'MCMC') y los algoritmos deterministas.

Otro problema en una veta similar es aproximar el volumen de un cuerpo convexo dado explícitamente (digamos un poliedro descrito por una colección de desigualdades lineales).

Raghu Meka
fuente

Una sutileza en P vs BPP, que desearía poder entender mejor, es la diferencia entre problemas de función y problemas de decisión. Puede ser que haya muchos problemas funcionales que se pueden resolver (en cierto sentido) al azar pero no de manera determinista en tiempo polinómico, pero P = BPP. Parece que sus ejemplos probablemente se traducen fácilmente en problemas de decisión, ¿es así?

usul

Los problemas de decisión frente a la función son un poco más sutiles que en el mundo NP, pero aún se sabe mucho: por ejemplo, este artículo en la sección 3 da un ejemplo de un "problema de búsqueda de tiempo polivalente aleatorio" que ni siquiera es decidible. Pero si la función es uno a uno, entonces P = BPP implica que un "problema aleatorio de función de tiempo polivinílico solucionable" tiene un algoritmo determinista de tiempo polivinílico (el documento da muchos más ejemplos también)

Joe Bebel