Suponemos que . Entonces el siguiente hecho es bien conocido:G∈G(n,p),p=lnn+lnlnn+c(n)nG∈G(n,p),p=lnn+lnlnn+c(n)nG\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n} Pr[G has a Hamiltonian cycle]=⎧⎩⎨⎪⎪10e−e−c(c(n)→∞)(c(n)→−∞)(c(n)→c)Pr[G has a Hamiltonian...
Estoy leyendo el clásico "Dureza contra aleatoriedad" de Nisan y Wigderson. Deje , y arregle una función . Definen una familia de funciones para ser pseudoaleatoria en el caso de cada circuito de tamaño que tengamosB = { 0 , 1 }si={0 0,1}B=\{0,1\}l : N → Nl:norte→nortel\colon \mathbb{N} \to...
Estoy interesado en la generación de números pseudoaleatorios para la criptografía. Además del Capítulo 5 de Menezes / Oorschot / Vanstone ; Capítulo 8 de Stinson ; y el Capítulo 3 de Goldreich , ¿dónde más podría encontrar más? Me interesan los principios generales para diseñar PRNG (propiedades...
En el documento de Pruebas naturales de Razborov-Rudich , página 6, en la parte que discuten que hay "fuertes pruebas de límites inferiores contra modelos de circuito monótono " y cómo encajan en la imagen, están las siguientes oraciones: Aquí el problema no es la constructividad, las...
Hay muchas situaciones en las que una "prueba" aleatorizada es mucho más fácil que una prueba determinista, siendo el ejemplo canónico la prueba de identidad polinómica. Pregunta : ¿Hay algún "teorema" matemático natural donde se conozca una prueba aleatoria pero no una prueba determinista? Por...
Si se colocan bolas en n contenedores de manera uniforme al azar, el contenedor cargado más pesado tiene O ( lg n / lg lg n ) bolas con alta probabilidad. En "The Power of Simple Tabulation Hashing" , Pătraşcu y Thorup mencionan que "los límites de Chernoff-Hoeffding para aplicaciones con...
ppp≤d≤d\le dbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon * Cuando escribo polinomios aleatorios con grados yn variables, puedes pensar en cada...
¿Podemos probar un resultado de concentración aguda en la suma de variables aleatorias exponenciales independientes, es decir, Sea X1,…XrX1,…XrX_1, \ldots X_r sean variables aleatorias independientes tales como Pr(Xi<x)=1−e−x/λiPr(Xi<x)=1−e−x/λiPr(X_i < x) = 1 - e^{-x/\lambda_i} . Deje...
Suponga que uno tiene un algoritmo aleatorio (BPP) usa bits de aleatoriedad. Las formas naturales de amplificar su probabilidad de éxito a , para cualquier elegido , sonAAArrr1−δ1−δ1-\deltaδ>0δ>0\delta>0 Ejecuciones independientes + voto mayoritario: ejecute independientemente veces, y...
Deje ser una constante. ¿Cómo podemos construir de manera comprobable un generador pseudoaleatorio que engañe a los autómatas finitos de estado d ?dddddd Aquí, una -state autómatas finitos tiene d nodos, un nodo de inicio, un conjunto de nodos que representan aceptar estados, y dos bordes...
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...
Me pregunto, ¿qué sucedería si en la definición de (Jerarquía polinómica, ver, por ejemplo, aquí ), el papel de N P fuera reemplazado por R P ?PHPHPHNPNPNPRPRPRP Parece, podríamos construir una jerarquía, del mismo modo que se construye, simplemente usando R P todas partes en lugar de N P y C O R...
Es ampliamente conocido que las fórmulas CNF se pueden dividir aproximadamente en 2 clases amplias: aleatoria versus estructurada. Las fórmulas estructuradas de CNF, en oposición a las fórmulas aleatorias de CNF, exhiben algún tipo de orden, mostrando patrones que es poco probable que ocurran por...
Hay 4 restricciones diferentes que podemos tener al definir Random K-SAT. 1) El número total de literales en una cláusula dada es exactamente K o como máximo K 2) Un literal dado se puede usar con o sin reemplazo en la misma cláusula (A o A o A) 3) Una variable dada se puede usar con o sin...
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...
¿Cuál es la complejidad de tiempo exacta del algoritmo de espacio de registro de conectividad st no dirigida por Omer
Deje que la clase BPNC (la combinación de y ) sean algoritmos paralelos de profundidad logarítmica con probabilidad de error limitada y acceso a una fuente aleatoria (no estoy seguro si este tiene un nombre diferente). Defina la clase DBPNC de manera similar, excepto que todos los procesos tienen...
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...
BPPBPP\mathsf{BPP} yZPPZPP\mathsf{ZPP} son dos de las clases básicas de complejidad probabilística. BPPBPP\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á...
¿Ha habido intentos de demostrar que la aleatoriedad de Kolmogorov sería suficiente para RP ? ¿La probabilidad utilizada en el enunciado "Si la respuesta correcta es SÍ, entonces (la máquina probabilística de Turing) devuelve SÍ con probabilidad ..." siempre estaría bien definida en ese caso? ¿O...