Tenemos que PTIME ⊆ RP ∩ co-RP ¿Podemos demostrar que PTIME = RP ∩ co-RP?
IIC3810
–
Complejidad probabil´ıstica
38 / 44
¿Qu´e sabemos sobre RP ∩ co-RP?
Tenemos que PTIME ⊆ RP ∩ co-RP ¿Podemos demostrar que PTIME = RP ∩ co-RP? !
IIC3810
–
Este es un problema abierto
Complejidad probabil´ıstica
38 / 44
¿Qu´e sabemos sobre RP ∩ co-RP?
Tenemos que PTIME ⊆ RP ∩ co-RP ¿Podemos demostrar que PTIME = RP ∩ co-RP? !
Este es un problema abierto
Pero podemos demostrar que para cada problema en RP ∩ co-RP existe un algoritmo que lo decide en tiempo polynomial esperado.
IIC3810
–
Complejidad probabil´ıstica
38 / 44
Un algoritmo de tiempo polinomial esperado
Sea L ∈ RP ∩ co-RP con alfabeto Σ
IIC3810
–
Complejidad probabil´ıstica
39 / 44
Un algoritmo de tiempo polinomial esperado
Sea L ∈ RP ∩ co-RP con alfabeto Σ
Entonces existen MTs probabil´ısticas M1 y M2 tales que: ! tM1 (n) es O(nk ) y para cada w ∈ Σ∗ : ! !
Si w ∈ L, entonces Pr(M1 acepte w ) ≥ 34 Si w ∈ ̸ L, entonces Pr(M1 acepte w ) = 0
! tM2 (n) es O(nℓ ) y para cada w ∈ Σ∗ : ! !
IIC3810
–
Si w ∈ L, entonces Pr(M2 acepte w ) = 1 Si w ∈ ̸ L, entonces Pr(M2 rechace w ) ≥ 34
Complejidad probabil´ıstica
39 / 44
Un algoritmo de tiempo polinomial esperado Sea g (n) = m´ax{tM1 (n), tM2 (n)}
IIC3810
–
Complejidad probabil´ıstica
40 / 44
Un algoritmo de tiempo polinomial esperado Sea g (n) = m´ax{tM1 (n), tM2 (n)} Considere el siguiente algoritmo para decidir si w ∈ L: 1. Escoja al azar y con distribuci´on uniforme un string s1 ∈ {0, 1}∗ tal que |s1 | = g (|w |) 2. Verifique si M1 (w , s1 ) acepta. Si es as´ı retorne s´ı, sino vaya al paso 3 3. Escoja al azar y con distribuci´on uniforme un string s2 ∈ {0, 1}∗ tal que |s2 | = g (|w |) 4. Verifique si M2 (w , s2 ) rechaza. Si es as´ı retorne no, sino vaya al paso 1
IIC3810
–
Complejidad probabil´ıstica
40 / 44
Un algoritmo de tiempo polinomial esperado
El algoritmo anterior puede no detenerse. !
IIC3810
–
Si se detiene entrega el resultado correcto
Complejidad probabil´ıstica
41 / 44
Un algoritmo de tiempo polinomial esperado
El algoritmo anterior puede no detenerse. !
Si se detiene entrega el resultado correcto
¿Cu´al es el tiempo esperado de funcionamiento del algoritmo?
IIC3810
–
Complejidad probabil´ıstica
41 / 44
Un algoritmo de tiempo polinomial esperado
El algoritmo anterior puede no detenerse. !
Si se detiene entrega el resultado correcto
¿Cu´al es el tiempo esperado de funcionamiento del algoritmo? !
IIC3810
–
Calcular el n´umero esperado de veces que se ejecuta la secuencia de pasos 1 al 4 se reduce a calcular la esperanza de una variable aleatoria con distribuci´ on geom´etrica de par´ametro 43
Complejidad probabil´ıstica
41 / 44
Un algoritmo de tiempo polinomial esperado
El algoritmo anterior puede no detenerse. !
Si se detiene entrega el resultado correcto
¿Cu´al es el tiempo esperado de funcionamiento del algoritmo? !
Calcular el n´umero esperado de veces que se ejecuta la secuencia de pasos 1 al 4 se reduce a calcular la esperanza de una variable aleatoria con distribuci´ on geom´etrica de par´ametro 43
Concluimos que el algoritmo funciona en tiempo polinomial esperado.
IIC3810
–
Complejidad probabil´ıstica
41 / 44
Una clase de complejidad probabil´ıstica m´as general
IIC3810
–
Complejidad probabil´ıstica
42 / 44
Una clase de complejidad probabil´ıstica m´as general
Definici´on Sea L un lenguaje sobre un alfabeto Σ. Entonces L est´a en BPP si existe una MT probabil´ıstica M tal que tM (n) es O(nk ) y para cada w ∈ Σ∗ :
IIC3810
–
!
Si w ∈ L, entonces Pr(M acepte w ) ≥
!
Si w ̸∈ L, entonces Pr(M acepte w ) ≤
Complejidad probabil´ıstica
3 4 1 4
42 / 44
¿D´onde est´a la clase BPP?
Teorema BPP = co-BPP
IIC3810
–
Complejidad probabil´ıstica
43 / 44
¿D´onde est´a la clase BPP?
Teorema BPP = co-BPP
Ejercicio Demuestre el teorema.
IIC3810
–
Complejidad probabil´ıstica
43 / 44
¿D´onde est´a la clase BPP?
Teorema BPP = co-BPP
Ejercicio Demuestre el teorema.
Corolario RP ⊆ BPP y co-RP ⊆ BPP
IIC3810
–
Complejidad probabil´ıstica
43 / 44
¿D´onde est´a la clase BPP?
Es un problema abierto si PTIME = BPP
IIC3810
–
Complejidad probabil´ıstica
44 / 44
¿D´onde est´a la clase BPP?
Es un problema abierto si PTIME = BPP !
IIC3810
–
De esto se concluir´ıa que BPP = RP = co-RP = PTIME
Complejidad probabil´ıstica
44 / 44
¿D´onde est´a la clase BPP?
Es un problema abierto si PTIME = BPP !
De esto se concluir´ıa que BPP = RP = co-RP = PTIME
Pero vamos a demostrar que BPP est´a contenida en la jerarqu´ıa polinomial.