¿Cuál es la simulación de BPP más rápida conocida utilizando los algoritmos de Las Vegas?

$\mathsf{BPP}$ y $\mathsf{ZPP}$ son dos de las clases básicas de complejidad probabilística.

$\mathsf{BPP}$ es la clase de lenguajes decididos por algoritmos probabilísticos de tiempo de polinomio de Turing donde la probabilidad de que el algoritmo devuelva una respuesta incorrecta está limitada, es decir, la probabilidad de error es como máximo $\frac{1}{3}$ (para las instancias SÍ y NO).

Por otro lado, los algoritmos $\mathsf{ZPP}$ pueden verse como aquellos algoritmos probabilísticos que nunca devuelven una respuesta incorrecta, siempre que devuelven una respuesta es correcta. Sin embargo, su tiempo de ejecución no está limitado por un polinomio, sino que se ejecutan en el polinomio esperado.

Sea $\mathsf{ZPTime}(f)$ la clase de lenguaje decidida por algoritmos probabilísticos con probabilidad de error cero y tiempo de ejecución esperado $f$ . Estos también se conocen como algoritmos de Las Vegas y $\mathsf{ZPP} = \mathsf{ZPTime}(n^{O(1)})$ .

Mi pregunta es, ¿cuál es la mejor simulación de algoritmos $\mathsf{BPP}$ utilizando los algoritmos de Las Vegas? ¿Podemos simularlos en tiempo esperado subexponencial? ¿Hay alguna mejora conocida sobre la simulación trivial de fuerza bruta que lleva tiempo exponencial?

Más formalmente, ¿sabemos si $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{O(n^{\epsilon})})$ o $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{n-n^{\epsilon}})$ para algún $\epsilon>0$ ?

cc.complexity-theory complexity-classes randomness randomized-algorithms echuly
fuente

¿Cuál es n, la longitud de la entrada? ¿Por qué podemos aceptar en

2^{n}

$2^n$

domotorp

es lo mismo que

2^{p o l y (n) - n^{ϵ}}

$2^{\mathrm{poly}(n)-n^\epsilon}$

2^{p o l y (n)}

$2^{\mathrm{poly}(n)}$

Emil Jeřábek

La pregunta me parece bastante interesante. Edité la pregunta para hacerla más legible y precisa. Siéntase libre de editar más. ps: Supongo que probablemente quisiste tener en cuenta los polinomios muchos bits aleatorios utilizados por el algoritmo BPP como parámetro para el tiempo de simulación, pero como Emil señala, lo que escribiste da

. Si desea que tenga que reemplazar BPP con una clase particular de algoritmos probabilísticos de error acotado que tienen un parámetro para el número de bits aleatorios utilizados por el algoritmo.

2^{p o l y (n)}

$2^{poly(n)}$

Kaveh

Puede preguntar si podemos simular un algoritmo BPP que utiliza

bits aleatorios en

r (n)

$r(n)$

ya que la simulación de fuerza bruta se ejecuta en

tiempo.

Z P T i m e (2^{r (n) - n^{ϵ}} n^{O (1)})

$\mathsf{ZPTime}(2^{r(n)-n^\epsilon}n^{O(1)})$

2^{r (n)} n^{O (1)}

$2^{r(n)}n^{O(1)}$

Kaveh

Respuestas:

Primero, observe que si para alguna constante , entonces . (Prueba por jerarquía de tiempo no determinista.) Por lo tanto, probar tal inclusión sería significativo, no solo porque es una simulación mejorada sino que también produciría el primer progreso en límites inferiores de tiempo aleatorio en décadas. $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ $c$ $\mathsf{BPP} \neq \mathsf{NEXP}$

A continuación, considere la clase $\mathsf{PromiseBPP}$ , para la cual el siguiente problema es " -hard": $\mathsf{PromiseBPP}$

Circuito Aproximación Probabilidad Problema (CAPP): Dado un circuito , la salida de la aceptación de probabilidad de dentro de un factor de aditivo. $C$ $C$ $1/6$

Los resultados de Impagliazzo, Kabanets y Wigderson 2002 implican que un algoritmo de error cero de para CAPP (donde es el tamaño de ) implicaría . En STOC'10, extendí esto para mostrar: suponiendo que por cada con bits de entrada tamaño, se pueda calcular CAPP de forma no determinista (por lo tanto, basta con cero errores) en $2^{n^{\varepsilon}}$ $n$ $C$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ $C$ $k$ $n$ tiempo, entonces . Es decir, ciertamente hay problemas computables con aleatoriedad de error de dos lados, para los cuales los algoritmos de error cero que incluso superan ligeramente la búsqueda exhaustiva implicarían límites inferiores del circuito. Creo que esto debería interpretarse como un posible método para probar los límites inferiores; Su experiencia puede ser diferente. $2^{k-\omega(\log k)}\mathrm{poly}(n)$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$

Tenga en cuenta que incluso probar también está abierto, y probar que también implicaría límites inferiores: por Kabanets e Impagliazzo 2004, si la prueba de identidad polinómica (un problema de ) es en para todos , entonces tenemos límites inferiores para el permanente o $\mathsf{RP} \subseteq \mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\mathsf{coRP}$ $\mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\varepsilon > 0$ $\mathsf{NEXP}$ . Recientemente (próximamente en STOC'13), probé incondicionalmente que o tiene circuitos tamaño, basándose en el método de "testigo fácil" de Kabanets. Esto implica dos cosas: $\mathsf{BPP} \subseteq \mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^{\varepsilon}$ $\mathsf{RTIME}[2^n]$ $n^c$

Hay una tal que para todo , está incondicionalmente en $c$ $\varepsilon > 0$ $\mathsf{RP}$ : esta es la mejor desrandomización incondicional de en que sabemos hasta ahora. $\mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^c$ $\mathsf{RP/BPP}$ $\mathsf{ZPP}$
Para comenzar a obtener interesantes simulaciones subexponenciales de , "solo" debe asumir que no tiene circuitos de tamaño polinómico fijo. $\mathsf{BPP}$ $\mathsf{RTIME}[2^n]$

Ryan Williams
fuente

Gracias a Niel por tomarse el tiempo para hacer legible mi respuesta :)

Ryan Williams

Ryan, creo que estoy a punto de hacer una pregunta muy estúpida, pero aquí voy: en tu primera oración, ¿por qué necesitas "para todos

"? El subconjunto BPP de ZPTIME (2 ^ (n ^ c)) para algunos c fijos implica el subconjunto BPP de RTIME (2 ^ (n ^ c)) y, por lo tanto, NTIME (2 ^ (n ^ c)), entonces BPP es no es igual a NEXP o de lo contrario NTIME (2 ^ (2n ^ c)) es un subconjunto de NTIME (2 ^ (n ^ c))?

ϵ

$\epsilon$

Sasho Nikolov

Para nada estúpido, de hecho,

para algunos

es suficiente para

, gracias por señalarlo. Sin embargo, los algoritmos de tiempo subexponencial son necesarios para las otras consecuencias.

B P P \subseteq N T I M E (2^{n^{c}})

$BPP \subseteq NTIME(2^{n^c})$

c

$c$

B P P \neq N E X P

$BPP \neq NEXP$

Ryan Williams

Ryan: Si quisiera entender tu trabajo, ¿con qué libro / trabajos sobre la complejidad del circuito me recomiendan estar familiarizado?

T ....

Hola Arul, afortunadamente Bill Gasarch me hizo esta pregunta hace un tiempo y colocó la siguiente página web de enlaces: cs.umd.edu/~gasarch/ryan/ryan.html

Ryan Williams

Depende de las suposiciones que esté dispuesto a hacer.

Bajo ciertos supuestos de dureza, a saber, , se obtiene que . Esto en particular implica que , y por lo tanto, cada lenguaje es aceptado por una máquina de Las Vegas (ver "P = BPP a menos que E tenga Circuitos Subexponenciales: Desrandomizando el Lema XOR", por Impagliazzo y Wigderson). $E \not\subseteq SIZE(2^{\varepsilon n})$ $P = BPP$ $BPP = ZPP$ $L \in BPP$

También puede hacer una suposición de dureza más leve, a saber, que , y obtener que (consulte el Lema 46 en "En busca de un testigo fácil: tiempo exponencial versus tiempo polinomial probabilístico "por Impagliazzo, Kabanets y Wigderson). $ZPE \not\subseteq \rm{io-DTIME}(2^{\varepsilon n})$ $BPP = ZPP$

O meir
fuente

Salvo cualquier avance en la aleatorización, me parece que el requisito de que la máquina de Las Vegas no cometa errores es crucial, por lo que hay poco o ningún beneficio de tener aleatoriedad en este caso.

Para un lenguaje BPP decidido por un algoritmo adecuado , que actúa sobre las entradas una cadena aleatoria representa sus elecciones aleatorias, el criterio de error cero implica que la máquina de Las Vegas debe determinar con certeza cuál de los dos casos $L$ $A$ $x \in \{0,1\}^n$ $r \in \{0,1\}^{N(n)}$ presas. Si no se nos da más información sobre, entonces este es esencialmente un problema de promesa de oráculo: dado un oráculocomputando, y dada la promesa de queproduce una salidapara al menos el doble de entradas que la salida opuesta, determine qué salida es más común.

\underset{r}{Pr} (A accepts (x, r)) ⩾ \frac{2}{3} or \underset{r}{Pr} (A accepts (x, r)) ⩽ \frac{1}{3}

$\Pr_r(\text{$A$ accepts $(x,r)$}) \geqslant \tfrac{2}{3} \quad\text{or}\quad \Pr_r(\text{$A$ accepts $(x,r)$}) \leqslant \tfrac{1}{3}$

A

$A$

A^{'}

$A'$

A^{'} (r) = A (x, r)

$A'(r) = A(x,r)$

A^{'}

$A'$

a \in {0, 1}

$a \in \{0,1\}$

1 - a

$1-a$

Aunque la máquina de Las Vegas puede usar técnicas aleatorias, si de hecho nos vemos obligados a tratar a como un oráculo, podemos ver que la única estrategia disponible para una máquina de Las Vegas es realizar una encuesta relativamente exhaustiva (aunque no exhaustiva) de cadenas aleatorias , para ver qué respuesta se da para cada una. Solo puede estar seguro si encuentra más de $A'$ $r$ cadenas distintas que dan lugar a la misma salida; de lo contrario, con una probabilidad pequeña (¡pero no nula!), puede ser desafortunado y obtener una muestra no representativa de los posibles resultados. Para obtener un error cero, debe muestrear al menos $2^{N(n)}\!/3$ $r$ entradas $2^{N(n)}\!/3$ $r$ .

Debido a que la máquina de Las Vegas debe inspeccionar al menos una fracción constante de todas las cadenas aleatorias posibles , asintóticamente no estamos mejor que si probamos determinísticamente todas las cadenas aleatorias posibles. No obtenemos ninguna ventaja asintótica al simular BPP $r$ aleatoria de algoritmos en un entorno de error cero, más allá de lo que podemos hacer determinísticamente por fuerza bruta.

Tenga en cuenta que este mismo argumento da lugar a una separación de oráculo entre BPP y ZPP , es decir , hay un oráculo tal que porque el algoritmo ZPP toma tiempo exponencial, mientras que un algoritmo BPP puede resolver la pregunta sobre El oráculo en una sola consulta y tener éxito con un error acotado. Sin embargo, no le dice más de lo que ya sospechaba (que la sobrecarga de la simulación puede ser peor que el polinomio) ni que las asintóticas son tan malas como una simulación determinista ingenua. $A$

{Z PAG PAG}^{UNA} ⫋ {si PAG PAG}^{UNA}

$\mathsf{ZPP}^A \subsetneqq \mathsf{BPP}^A$

Niel de Beaudrap
fuente

corrígeme si me equivoco: estás dando un razonamiento intuitivo por el cual la desrandomización parece imposible, pero sabemos que, bajo algunos supuestos razonables, BPP, ZPP y P son lo mismo. para que la intuición no sea necesariamente buena

Sasho Nikolov

De ningún modo. La desrandomización presumiblemente sería una idea de cómo simular BPP por P , ¿no? Solo estoy describiendo cómo, si quiere resultados incondicionales que no exploten la estructura del algoritmo en sí, también puede realizar una simulación determinista como una aleatorización de error cero. ¿O hay algo mal con esta explicación?

Niel de Beaudrap

Creo que todo lo que está diciendo es que la ingenua simulación de fuerza bruta de BPP por ZPP no es mucho más rápida que la ingenua simulación de fuerza bruta de BPP por P. pero no puedo ver lo que se supone que muestra. para mí esto es como alguien preguntando "cuál es el algoritmo más rápido para encontrar una coincidencia máxima" y obteniendo como respuesta "bueno, fallando cualquier idea sobre la estructura de las coincidencias, es tiempo exponencial". la pregunta es si hay alguna información conocida sobre la estructura de BPP que hace posible la simulación eficiente de ZPP

Sasho Nikolov

@ SashoNikolov: Realmente no estaba destinado a ser una visión profunda. Según la redacción de la pregunta, me pareció límite para migrar a CS.SE. Decidí responderlo literalmente, a saber: hasta donde sabemos , el tiempo de ejecución esperado más eficiente de Las Vegas Machine que acepta un lenguaje L∈BPP no es mucho mejor que una máquina determinista que explora las posibilidades de la fuerza bruta. Las respuestas que dicen que podría ser algún límite superior polinómico si se cumplen algunas condiciones son excelentes e informativas, y las voto por eso; pero me dirijo a la pregunta real.

Niel de Beaudrap

Creo que esta es una buena respuesta (también más legible ahora después de editar). No tenemos un resultado condicional como "P = ZPP implica P = BPP" o "ZPP = BPP implica P = BPP", por lo que aún es posible que podamos simular BPP mediante algoritmos ZP más rápido que con algoritmos deterministas. Sin embargo, el resultado de la relativización parece implicar que esto no puede suceder por ninguna simulación relativizante, ¿lo entiendo correctamente?

Kaveh