Un algoritmo cuyo comportamiento está determinado por su entrada y un generador que produce números aleatorios uniformes.
La prueba de Adleman de que está contenido en muestra que si hay un algoritmo aleatorio para un problema que se ejecuta en el tiempo en entradas de tamaño , entonces también hay un algoritmo determinista para el problema que se ejecuta en el tiempo en entradas de tamaño [el algoritmo ejecuta el...
Muchos creen que BPP=P⊆NPBPP=P⊆NP\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP} . Sin embargo, solo sabemos que BPPBPP\mathsf{BPP} está en el segundo nivel de jerarquía polinómica, es decir, BPP⊆ΣP2∩ΠP2BPP⊆Σ2P∩Π2P\mathsf{BPP}\subseteq \Sigma^ \mathsf{P}_2 \cap \Pi^ \mathsf{P}_2 . Un paso hacia la...
A menudo escucho que para muchos problemas conocemos algoritmos aleatorios muy elegantes, pero no, o solo soluciones deterministas más complicadas. Sin embargo, solo conozco algunos ejemplos de esto. Lo más destacado Selección rápida aleatoria (y algoritmos geométricos relacionados, por ejemplo,...
¿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...
Log-space-uniform NC está contenido en un espacio polylog determinista (a veces escrito PolyL). ¿Log-space-uniform RNC también está en esta clase? La versión aleatoria estándar de PolyL debería estar en PolyL, pero no veo que el RNC (uniforme) esté en PolyL aleatorizado. La dificultad que veo es...
Editar: elijo la respuesta con la puntuación más alta antes del 06 de diciembre de 2012. Esta es una pregunta suave. El concepto de algoritmos (deterministas) se remonta a BC. ¿Qué pasa con los algoritmos probabilísticos? En esta entrada de la wiki , el algoritmo de Rabin para el problema de par...
Acabo de enseñar el algoritmo de mincut aleatorio Karger-Stein en mi clase de algoritmos de posgrado. Esta es una verdadera joya algorítmica , así que no puedo no enseñarlo, pero siempre me deja frustrado, porque no conozco ninguna otra aplicación de la técnica principal. (Por lo tanto, es difícil...
Estoy seguro de que todos conocen el experimento de la aguja de Buffon en el siglo XVIII, que es uno de los primeros algoritmos probabilísticos para calcular .ππ\pi La implementación del algoritmo en las computadoras generalmente requiere el uso de , o una función trigonométrica, que, incluso si...
RP es la clase de problemas que puede resolver una máquina de Turing no determinista que termina en tiempo polinómico, pero también se permite un error unilateral. P es la clase habitual de problemas que puede resolver una máquina de Turing determinista que termina en tiempo polinómico. P = RP se...
Un importante artículo de 2003 de Childs et al.introdujo el "problema de los árboles combinados": un problema que admite una aceleración cuántica exponencial que es diferente a casi cualquier otro problema que conozcamos. En este problema, se nos da un gráfico exponencialmente grande como el que se...
Para los algoritmos aleatorios AA\mathcal{A} toman valores reales, el "truco mediano" es una forma simple de reducir la probabilidad de falla a cualquier umbral δ>0δ>0\delta > 0 , a costa de solo un multiplicativo t=O(log1δ)t=O(log1δ)t=O(\log\frac{1}{\delta})sobrecarga. A saber, si...
PPPXX\mathcal{X}AA\mathcal{A}PPPDD\mathcal{D}RR\mathcal{R}AA\mathcal{A}minA∈AEcost(A,D)≤maxx∈XEcost(R,x)for all D and R.minA∈AEcost(A,D)≤maxx∈XEcost(R,x)for all D and R.\min_{A\in\mathcal{A}}\quad\mathbb{E} cost(A,\mathcal{D}) \leq \max_{x\in\mathcal{X}}\quad\mathbb{E} cost(\mathcal{R},x)...
Cuando enseño límites de cola, uso la progresión habitual: Si su rv es positivo, puede aplicar la desigualdad de Markov Si tiene independencia y también varianza limitada, puede aplicar la desigualdad de Chebyshev Si cada rv independiente también tiene todos los momentos limitados, entonces...
Si es una función convexa, la desigualdad de Jensen establece que , y mutatis mutandis cuando es cóncava. Claramente, en el peor de los casos, no puede el límite superior en términos de para una convexa , pero ¿hay un límite que vaya en esta dirección si es convexo pero "no demasiado convexo"?...
Sea sea una función. Queremos estimar el promedio de ; es decir: .f E [ f ( n ) ] = 2 - n ∑ x ∈ { 0 , 1 } n f ( x )f:{0,1}n→(2−n,1]f:{0,1}n→(2−n,1]f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]fffE[f(n)]=2−n∑x∈{0,1}nf(x)E[f(n)]=2−n∑x∈{0,1}nf(x)\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1...
Considere el siguiente modelo: una cadena de n bits r = r 1 ... r n se elige de manera uniforme al azar. A continuación, cada índice i∈ {1, ..., n} se coloca en un conjunto A con probabilidad independiente 1/2. Por último, se permite que un adversario, para cada i∈A separado, a r flip i si se...
Sea la clase de los problemas de decisión que tienen un algoritmo aleatorio de error de dos lados limitado que se ejecuta en el tiempo .O ( f ( n ) )B P T I M E (f( n ) )BPTIME(f(n))\mathsf{BPTIME}(f(n))O ( f( n ) )O(f(n))O(f(n)) ¿Conocemos algún problema tal que pero ? ¿Está comprobada su...
Una cosa que las computadoras cuánticas pueden hacer (posiblemente incluso con solo circuitos cuánticos de profundidad logarítmica BPP +) es aproximar-muestrear la transformada de Fourier de una función de valor booleano en P.± 1±1\pm 1 Aquí y más abajo, cuando hablo de probar la transformada de...
Supongamos que considero la siguiente variante de BPP, que nos permite llamar E (xact) BPP: un lenguaje está en EBPP si hay un TG polinomial aleatorio que acepta cada palabra del idioma con exactamente 3/4 de probabilidad y cada palabra no en el lenguaje con exactamente 1/4 de probabilidad....
Esta pregunta está inspirada en la camiseta de Georgia Tech Algorithms and Randomness Center , que pregunta "¿Aleatorizar o no?" Hay muchos ejemplos en los que la aleatorización ayuda, especialmente cuando se opera en entornos adversos. También hay algunas configuraciones donde la aleatorización...