Adleman ha demostrado en 1978 que BPP⊆P/polyBPP⊆P/poly\mathrm{BPP}\subseteq \mathrm{P/poly} : si una función booleana fff de nnn variables puede calcularse mediante un circuito booleano probabilístico de tamaño MMM , entonces fff también puede calcularse mediante un circuito booleano determinista...
Las desigualdades de tipo Chernoff se usan para mostrar que la probabilidad de que una suma de variables aleatorias independientes se desvíe significativamente de su valor esperado es exponencialmente pequeña en el valor esperado y la desviación. ¿Existe una desigualdad de tipo Chernoff para...
Dado X1,…,XkX1,…,XkX_1,\ldots,X_k (iid gaussianos con media 000 y varianza 111 ), ¿es posible (¿cómo?) Muestrear (para m=k2m=k2m=k^2 ) Y1,…,YmY1,…,YmY_1, \ldots, Y_m tal que YiYiY_i son pares gaussianos independientes con media 000 y varianza 111
Los algoritmos de flujo requieren aleatorización en su mayor parte para hacer algo no trivial, y debido a la restricción de espacio pequeño, necesitan PRG que usen poco espacio. Sé de dos métodos que se han citado para su uso en algoritmos de flujo hasta ahora: -wise PRGs independientes como la...
Se sabe que agregar aleatorización de error limitado a PSPACE no agrega potencia. Es decir, BPPSAPCE = PSPACE. Se desconoce si P = BPP, pero se sabe que .B PPAG⊆ Σ2∩ Π2BPP⊆Σ2∩Π2BPP\subseteq \Sigma_2\cap \Pi_2 Por lo tanto, es posible (mientras se conjetura que es falso) que agregar probabilidad a...
Dada compuesto N∈NN∈NN\in\Bbb N tamiz campo de número general es mejor algoritmo de factorización conocida para la factorización de enteros de NNN . Es un algoritmo aleatorio y obtenemos una complejidad esperada de
Estaba leyendo un artículo titulado Random Oracles with (out) Programmability . El último párrafo de la sección 2.3 dice: [Utilizando nuestro enfoque novedoso] no hay necesidad de aplicar técnicas de desrandomización asintóticas clásicas (y uniformes) bien conocidas basadas en el lema de...
He desarrollado una nueva técnica de desrandomización que está dirigida a algoritmos aleatorios recursivos (o) algoritmos aleatorios más generales que usan una pila. Desafortunadamente, no pude encontrar algoritmos aleatorios naturales para aplicar mis técnicas. Las cadenas recursivas de Markov y...
Tengo algunas preguntas sobre engañar a los circuitos de profundidad constante. Se sabe que la independencia de es necesaria para engañar a los circuitos A C 0 de profundidad d , donde n es el tamaño de la entrada. ¿Cómo se puede probar esto?Iniciar sesiónO ( d)( n )logO(d)(n)\log^{O(d)}(n)A C0...
Estoy leyendo el famoso documento Impagliazzo y Wigderson en 1997. Como soy nuevo en este campo y el documento es una versión concisa de la conferencia, tengo dificultades para seguir sus pruebas. En particular, algunos de sus nuevos teoremas carecen de pruebas. Que yo sepa, no se ha publicado una...
Dado modo que los coeficientes de están delimitados por , hace ¿sostener?p , q B p ≡ qp(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]p,qp,qp,qBBBp≡qp≡qp\equiv q El lema de Schwartz-Zippel se aplica aquí, ya que es válido...
Es bien sabido que el cálculo de una máquina de Turing no determinista (NTM) es representable como un árbol de configuraciones, enraizado en la configuración inicial. Cualquier transición en el programa está representada por un enlace padre-hijo en este árbol. También se pueden construir árboles...
La inclusión inversa es obvia, como lo es el hecho de que cualquier lenguaje NP auto reducible en BPP también está en RP. ¿También se sabe que esto es válido para idiomas NP no
Deje ser una constante fija. Dado un número entero , queremos construir una permutación tal que:n σ ∈ S nk > 0k>0 0k>0nortenortenσ∈ Snorteσ∈Snorte\sigma \in S_n La construcción utiliza tiempo y espacio constantes (es decir, el preprocesamiento requiere tiempo y espacio constantes). Podemos...
En la prueba de identidad polinómica buscamos un algoritmo determinista para inferir la igualdad de dos polinomios . Desrandomizar algoritmos aleatorizados eficientes conocidos y producir un algoritmo determinista eficiente es un importante problema abierto. ¿Existe un problema completo para PIT de...
Parece que hay muchos algoritmos aleatorios para las pruebas de identidad polinomiales, que verifican si un polinomio dado es cero o no. ¿Hay algún resultado de algoritmos que hagan algún tipo de estimación de polinomios sobre un conjunto específico de puntos? Esto podría ser, por ejemplo,...
Estoy interesado en ejemplos de construcciones en la teoría de la complejidad que son mejores que las construcciones aleatorias. El único ejemplo de tal construcción que conozco es en el campo de los códigos de corrección de errores. Los códigos de geometría algebraica son mejores en algún rango...
Por BPP / lineal, me refiero a máquinas BPP con asesoramiento lineal, que cumple la promesa cuando se le da el consejo "correcto", y la desrandomización debería darnos, por ejemplo, un algoritmo P / lineal o (SUBEXP / lineal). Si usamos suposiciones no uniformes, creo que los resultados clásicos...
Sea una clase de complejidad y sea la contraparte aleatoria de definida de la misma manera que se define con respecto aCC\mathcal{C}BP-CBP-C\textrm{BP-}\mathcal{C}CC\mathcal{C}BPPBPP\textrm{BPP}PP\textrm{P} . Más formalmente, proporcionamos polinómicamente muchos bits aleatorios y aceptamos una...
Considere una máquina (es decir, un algoritmo probabilístico que usa espacio de registro y polinomialmente muchos bits aleatorios). Se sabe (Saks-Zhou) que B P L ⊆ D S P A C E ( l o g 1.5 ( n ) ) .B PLsiPAGSLBPLB PL ⊆ D SPAGSA Cmi( l o g1,5( n ) )siPAGSL⊆reSPAGSUNACmi(losol1,5(norte))BPL \subseteq...