Aleatorizacion [2010-10-14 Thu]--[2010-10-19 Tue]
Jérémy Barbay 9 Nov 201009/11/10 at 11:302010-11-09 11:30:09
Aleatorizacion (1 semana = 2 charlas)
=====================================
Author: Jérémy Barbay
Date: 2010-11-09 11:28:36 CLST
* REFERENCIA:
- Capitulo 1 en "Randomized Algorithms", de Rajeev Motwani and Prabhakar Raghavan.
Table of Contents
=================
1 Definiciones
2 El poder de un algoritmo aleatorizado
3 Aleatorizacion de la entrada
3.1 SkipLists
3.1.1 Paginamiento al Azar
3.1.2 Arboles Binarios de Busqueda aleatorizados
3.1.3 Complejidad Probabilistica: cotas inferiores
4 *Relacion con Problemas NP-Dificiles*
5 Complejidad de un algoritmo aleatorizado
6 Tecnicas de cotas inferiores de la complejidad aleatorizada
7 Algoritmos tipo Monte Carlo y Las Vegas
8 Primalidad
9 Clases de complejidad aleatorizada
9.1 RP
9.2 ZPP
9.3 PP
9.4 BPP
1 DONE Definiciones
~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-14 Thu 12:00-13:30>
- *Algoritmos deterministico*
- algoritmo que usa solamente instrucciones
*deterministicas*.
- algoritmo de cual la ejecucion (y, entonces, el
rendimiento) depende solamente del input.
- *Algoritmos aleatorizados*
- algoritmo que usa una instruccion *aleatorizada*
(potentialemente muchas veces)
- una distribucion de probabilidades sobre una familia de
algoritmos deterministicos.
- *Análisis probabilistica*
- analysis del rendimiento de un algoritmo, en promedio
sobre
- el aleatorio de la entrada, o
- el aleatorio del algoritmo, o
- los dos.
- veamos que son nociones equivalentes.
2 DONE El poder de un algoritmo aleatorizado
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-14 Thu 12:00-13:30>
- Nota: Trae los juguetes/cajas de colores, con un tesoro a esconder a dentro.
Ejemplos de algoritmos o estructuras de datos aleatorizados
1. *hidden coin*
- Decidir si un elemento pertenece en un lista
desordenada de tamaño k, o si hay una moneda a dentro
de una de las $k$ caja.
- cual son las complejidades determinisitica y
aleatorizada del problema de encontrar *una* moneda,
con $c$ la cantidad de monedas,
- si $c=1$?
- si $c=n-1$?
- si $c=n/2$?
- Respuestas:
- Si una sola instancia de la valor buscada
- k en el peor caso deterministico
- k/2 en (promedio y en) el peor caso aleatorio
- con una dirección al azar
- con lg(k!) bits aleatorios
- Si r instancias de la valor buscada
- k-r en el peor caso deterministico
- O(k/r) en (promedio y en) el peor caso aleatorio
3. Decidir si un elemento pertenece en una lista ordenadas
de tamaño n
* \Theta(\lg n) comparaciones en ambos casos,
deterministico y probabilÃ-stico.
4. *problema de union*
* Decidir si un elemento pertenece en una de las k listas
ordenadas de tamaño n
* Si una sola lista contiene la valor buscada
- k búsquedas en el peor caso deterministico, que da
k\lg(n) comparaciones
- k/2 búsquedas en (promedio y en) el peor caso
aleatorio, que da k\lg(n)/2 comparaciones
* Si r
* Independencia de la distribucion de la entrada
- Si el input sigue una distribucion non-conocida, el input
perturbado tiene una distribucion conocida (para una
perturbacion bien elegida)
- Ejemplo:
- flip $b$ de una bit con probabilidad $p$ que puede ser
distinta de $1/2$.
- suma-lo modulo 1 con un otro bit aleatorizado, con
probabilidad $1/2$ de ser uno.
- la suma es igual a uno con probabilidad $1/2$.
* Estructuras de datos aleatorizadas
- *funciones de hash*:
- estructura de datos aleatorizada,
- donde (a,b) son elegidos al azar.
- *skiplists*
- estructura de datos aleatorizada,
- que simula en promedio un arbol binario
3.1 DONE SkipLists
===================
1) Estructuras de datos para diccionarios
- [X] Arreglo ordenado
- [ ] "Move To Front" list (did they see it already?)
- [X] Arboles binarios
- [X] Arboles binarios aleatorizados
- [X] Arboles 2-3 ( they saw it already?)
- [X] Red-Black Trees ( they saw it already?)
- [X] AVL
- [X] Skip List
- [ ] Splay trees
2) Skip Lists
1. Motivación
- un arbol binario con entradas aleatorizadas tienen una
altura O(lg n), pero eso supone un orden de input
aleatorizados.
- El objetivo de las "skip lists" es de poner el aleatorio
a dentro de la estructura.
- también, es el equivalente de una búsqueda binaria en
listas via un resumen de resumen de resumen...
2. Definición
- una skip-list de altura $h$ para un diccionario $D$ de
$n$ elementos es una familia de lists $S_0,\ldots,S_h$ y
un puntero al primero elemento de $S_h$, tal que
- $S_0$ contiene $D$;
- cada $S_i$ contiene un subconjunto aleatorio de $S_{i-1}$
(en promedio la mitad)
- se puede navegar de la izquierda a la derecha, y de la
cima hasta abajo.
- se puede ver como $n$ torres de altura aleatorizadas,
conectadas horizontalmente con punteros de la
izquierda a la derecha.
- la información del diccionario están solamente en S_0 (no
se duplica)
3. Ejemplo
4 X - - - - - - -> X
3 X - -> X - - - -> X
2 X - -> X X -> X -> X
1 X X -> X X -> X -> X
0 X X X X X X X X X
---+---------+----+----+----+----+----+----+----+--------
-\infty 10 20 30 40 50 60 70 \infty
4. Operaciones
* Search(x):
- Start a the first element of $S_h$
- while not in $S_0$
- go down one level
- go right till finding a key larger than x
* Insert(x)
- Search(x)
- create a tower of random height (p=1/2 to increase
height, typically)
- insert it in all the lists it cuts.
* Delete(x)
- Search(x)
- remove tower from all lists.
5. Ejemplos
* Insert(55) con secuencia aleatora (1,0)
4 X - - - - - - - -> X
3 X - -> X - - - - -> X
2 X - -> X X - -> X -> X
1 X X -> X X *->* *X* X -> X
0 X X X X X X *X* X X X
---+---------+----+----+----+----+------+------+----+----+--------
-\infty 10 20 30 40 50 *55* 60 70 \infty
* Insert(25) con (1,1,1,1,0)
5 *X* - - - - - - - - *->* *X*
4 X - *->* *X* - - - - - -> X
3 X - *->* *X* X - - - - -> X
2 X - *->* *X* X X - -> X -> X
1 X X *->* *X* X X -> X X -> X
0 X X X *X* X X X X X X X
---+---------+----+------+------+----+----+----+----+----+------+--------
-\infty 10 20 *25* 30 40 50 55 60 70 \infty
* Delete(60)
5 X - - - - - - - -> X
4 X - -> X - - - - -> X
3 X - -> X X - - - -> X
2 X - -> X X X - - *->* X
1 X X -> X X X -> X -> X
0 X X X X X X X X X X
---+---------+----+----+----+----+----+----+----+------+--------
-\infty 10 20 25 30 40 50 55 70 \infty
6. Analisis
* Espacio: Cuanto nodos en promedio?
- cuanto nodos en lista S_i?
- $n/2^i$ en promedio
- Summa sobre todos los niveles
- $n \sum 1/2^i < 2n$
* Tiempo:
- altura promedio es O(\lg n)
- tiempo promedio es O(\lg n)
3.1.1 DONE Paginamiento al Azar :OPTIONAL:
------------------------------------------
- REFERENCIA:
- Capitulo 3 en "Online Computation and Competitive Analysis", de
Allan Borodin y Ran El-Yaniv
- Capitulo 13 en "Randomized Algorithms", de Rajeev Motwani and
Prabhakar Raghavan, p. 368
1) Tipos de Adversarios (cf p372 [Motwani Raghavan]
* Veamos en el caso deterministico un tipo de adversario
offline, como medida de dificultad para las instancias online.
Para el problema de paginamiento con k paginas, el ratio
óptima entre un algoritmo online y offline es de $k$
(e.g. entre LRU y LFD).
* DEFINICIÓN:
En el caso aleatorizado, se puede considerar mas tipos de
adversarios, cada uno definiendo una medida de dificultad y
un modelo de complejidad.
1. Adversario "Oblivious" ("Oblivious Adversary")
El adversario conoce $A$ pero no $R$: el elija su instancia
completamente al inicial, antes de la ejecución online del
algoritmo.
2. Adversario Offline adaptativo
Para este definición, es mas fácil de pensar a un
adversario como un agente distinto del algoritmo offline
con quien se compara el algoritmo online.
El adversario conoce $A$ en total, pero $R$ online, y le
utiliza para generar una instancia peor $I$. Este instancia
$I$ es utilizada de nuevo para ejecutar el algoritmo
offline (quien conoce el futuro) y producir las
complejidades (a cada instante online) con cual comparar la
complejidad del algoritmo online.
3. Adversario Online adaptativo
En este definición, el algoritmo conoce $A$ en total,
construir la instancia $I$ online como en el caso
precedente, pero tiene de tiene de resolverla online también
(de una manera, no se ve en el futuro).
* Comparación de los Tipos de adversarios.
- Por las definiciones, es claro que
- el adversario offline adaptativo
- es mas poderoso que
- el adversario online adaptativo
- es mas poderoso que
- el adversario oblivious
* Competitiva Ratios
* Para un algoritmo online $A$
- Para cada tipo de adversario se define un competitivo ratio:
- C_A^{obl}: competitivo ratio con adversario oblivious
- C_A^{aon}: competitivo ratio con adversario adaptativo online
- C_A^{aof}: competitivo ratio con adversario adaptativo offline
- Es obvio que, para $A$ fijada, considerando un adversario
mas poderoso va aumentar el competitivo ratio:
C_A^{obl} \leq C_A^{aon} \leq C_A^{aof}
* Para un problema
- el competitivo ratio de un problema es el competitivo
ratio mÃ-nima sobre todos los algoritmos correctos para
este problema.
C^{obl} \leq C^{aon} \leq C^{aof} \leq C^{det}
- donde C^{det} es el competitivo ratio de un algoritmo
online deterministico.
3.1.2 DONE Arboles Binarios de Busqueda aleatorizados
------------------------------------------------------
- Conrado MartÃ-nez. Randomized binary search trees. Algorithms
Seminar. Universitat Politecnica de Catalunya, Spain, 1996.
- Conrado MartÃ-nez and Salvador Roura. Randomized binary search
trees. J. ACM, 45(2):288–323, 1998.
- [en.wikipedia.org/ ... d_binary_search_tree]
3.1.3 DONE Complejidad Probabilistica: cotas inferiores
--------------------------------------------------------
* REFERENCIA:
- Capitulo 1 en "Randomized Algorithms", de Rajeev Motwani and Prabhakar Raghavan.
* Notes:
1) Problema
- Strategia de adversario no funciona
- En algunos casos, teorÃ-a de códigos es suficiente
- e.g. búsqueda en arreglo ordenado
- eso es una cota inferior sobre el tamaño del
certificado
- En otros caso, teorÃ-a de códigos no es suficiente
- en particular, cuando el precio para verificar un
certificado es mas pequeño que de encontrarlo.
- En estos casos, utilizamos otras técnicas:
- teorÃ-a de juegos (que vamos a ver) y equilibro de Nash
- cotas sobre la comunicación en un sistema de
"Interactive Proof"
2) Algunas Notaciones Algebraicas
Sea:
- A una familia de $n_a$ algoritmos deterministicos
- $a$ un vector (0,...,0,1,0,...,0) de dimensión $n_a$
- $\alpha$ una distribución de probabilidad de dimensión $n_a$
- B una familia de $n_n$ instancias
- $b$ un vector (0,...,0,1,0,...,0) de dimensión $n_b$
- $\beta$ una distribución de probabilidad de dimensión $n_b$
- M una matriz de dimensión $n_a\times n_b$ tal que M_{a,b}
es el costo del algoritmo $a$ sobre la instancia $b$.
Por definición,
- a^t M b = M_{a,b}
- \alpha^t M b es la complejidad en promedio (sobre el
aleatorio del algoritmo \alpha) de \alpha sobre b
- a^t M \beta es la complejidad en promedio (sobre la
distribución de instancias \beta) de a sobre \beta
- \alpha^t M \beta es la complejidad en promedio del
algoritmo aleatorizados \alpha sobre la distribución de
instancia \beta.
3) von Neuman's theorem: infsup = supinf = minmax = maxmin
1. OPCIONAL Existencia de $\tilde{\alpha}$ et $\tilde{\beta}$
Dado $\phi$ y $\psi$ definidas sobre $\mathbb{R}^m$ y $\mathbb{R}^n$ por
$$\phi(\alpha) = \sup_\beta \alpha ^T M \beta
\,\mbox{ y }\,
\psi(\beta) = \inf_\alpha \alpha ^T M \beta$$
Entonces:
- $\phi(\alpha) = \max_\beta \alpha ^T M \beta$
- $\psi(\beta) = \min_\alpha \alpha ^T M \beta$
- hay estrategias mixtas
- $\tilde{\alpha}$ por \A\
- $\tilde{\beta}$ por \B\
- tal que
- $\phi$ es a su mÃ-nima en $\tilde{\alpha}$ y
- $\psi$ es a su máxima en $\tilde{\beta}$.
2. Resultado de von Neuman:
Dado un juego $\Gamma$ definido por la matrica $M$~:
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
3. Interpretación:
+ Este resultado significa que si consideramos ambos
distribuciones sobre algoritmos y instancias, no
importa el orden del max o min:
- podemos elegir el mejor algoritmo (i.e. minimizar
sobre los algoritmos aleatorizados) y después
elegir la peor distribución de instancias para el
(i.e. maximizar sobre las distribuciones de
instancias), o al reves
- podemos elegir la peor distribución de instancias
(i.e. maximizar sobre las distribuciones de
instancias), y considerar el mejor algoritmo
(i.e. minimizar sobre los algoritmos
aleatorizados) para este distribución.
+ ATENCIÓN!!!! Veamos que
- El promedio (sobre las instancias) de las
complejidades (de los algoritmos) en el peor caso
- no es igual
- al peor caso (sobre las instancias) de la complejidad
en promedio (sobre el aleatorio del algoritmo)
- donde el segundo termo es realmente la complejidad de
un algoritmo aleatorizados.
+ TodavÃ-a falta la relación con la complejidad en el
peor caso $b$ de un algoritmo aleatorizados $\alpha$:
$\max_b \min_\alpha \alpha ^T M b$
4) Lema de Loomis
* Dado una estrategia aleatoria $\alpha$, emite una instancia
$b$ tal que $\alpha$ es tan mal en $b$ que en el
peor $\beta$.
$$
\forall \alpha \exists b,
\max_\beta \alpha^T M \beta = \alpha^T M b
$$
* Dado una distribución de instancias $\beta$, existe un
algoritmo deterministico $a$ tal que $a$ es tan
bien que el mejor algoritmo aleatorizados $\alpha$ sobre
la distribución de instancias $\beta$:
$$
\forall \beta \exists a,
\min_\alpha \alpha^T M \beta = a^T M \beta
$$
* Interpretación:
+ En frente a una distribución de instancias especifica,
siempre existe un algoritmo deterministico óptima en
comparación con los algoritmos aleatorizados (que
incluen los deterministicos).
+ En frente a un algoritmo aleatorizados, siempre existe
una instan ca tan mal que la pero distribución de
instancias.
5) PrÃ-ncipe de Yao
* Del leima de Loomis podemos concluir que
$$
\max_\beta \alpha^T M \beta = \max_b \alpha^T M b
$$
$$
\min_\alpha \alpha^T M \beta = \min_a a^T M \beta
$$
* Del resultado de von Neuman sabemos que maxmin=minmax
(sobre \alpha y \beta):
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
* Entonces
$$
\min_alpha \max_b \alpha^T M b
= (Loomis)
\min_\alpha \max_\beta \alpha ^T M \beta
= (von Neuman)
\max_\beta \min_\alpha \alpha ^T M \beta
= (Loomis)
\max_\beta \min_a a^T M \beta
$$
* Interpretación
\min_\alpha \max_b \alpha^T M b
\_______ La complejidad
\______ _______ ________ del mejor algoritmo aleatorizado
\___ ___________ en el peor caso
es igual a
\max_\beta \min_a \alpha^T M b
\_______ La complejidad
\___ ___________ del mejor algoritmo deterministico
\______ _______ ________ sobre la peor distribución de instancias
"El peor caso del mejor algoritmo aleatorizado
corresponde a
la peor distribución para el mejor algoritmo deterministico."
* Ejemplos de cotas inferiores:
1. Decidir si un elemento pertenece en una lista ordenadas de tamaño n
- Cual es el peor caso $b$ de un algoritmo aleatorizado $\alpha$?
- Buscamos una distribución $\beta_0$ que es mala para todos
los algoritmos deterministicos $a$ (del modelo de comparaciones)
- Consideramos la distribución uniforma.
- Cada algoritmo deterministico se puede representar como un
arbol de decisión (binario) con $2n+1$ hojas.
- Ya utilizamos para la cota inferior deterministica que la
altura de un tal arbol es al menos $\lg(2n+1)\in\Omega(\lg
n)$. Esta propiedad se muestra por recurrencia.
- De manera similar, se puede mostrar por recurrencia que la
altura en promedio de un tal arbol binario es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, la complejidad promedio de cada algoritmo
deterministico $a$ sobre $\beta_0$ es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, utilizando el principie de Yao, la complejidad en
el peor caso de un algoritmo aleatorizado en el modelo de
comparaciones es al menos $\lg(2n+1)\in\Omega(\lg n)$.
- El corolario interesante, es que el algoritmo
deterministico de búsqueda binaria es *oprima* a dentro de
la clase mas general de algoritmos aleatorizados.
2. Decidir si un elemento pertenece en un lista desordenada de tamaño k
* Si una sola instancia de la valor buscada ($r=1$)
* Cotas superiores
- k en el peor caso deterministico
- (k+1)/2 en el peor caso aleatorio
- con una dirección al azar
- con lg(k!) bits aleatorios
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición, y que
consideran todas las posiciones en el peor caso:
entonces cada algoritmo puede ser representado por una
permutación sobre $k$.
- Dado un algoritmo deterministico $a$, para cada
$i\in[1,k]$, hay una instancia sobre cual el performe
$i$ comparaciones. Entonces, su complejidad en promedio
en este instancia es $\sum_i i/k$, que es $k(k+1)/2k =
(k+1)/2$. Como eso es verdad para todos los algoritmos
deterministicos, es verdad para el mejor de ellos
también.
- Entonces, utilizando el principio de Yao, la complejidad
en el peor caso de un algoritmo aleatorizado en el
modelo de comparaciones es al menos $(k+1)/2$.
* Si r instancias de la valor buscada
* Cotas superiores
- k-r en el peor caso deterministico
- O(k/r) en (promedio y en) el peor caso aleatorio
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición.
- De verdad, no algoritmo tiene de considerar mas
posiciones que $k-r+1$, entonces hay menos algoritmos
que de permutaciones sobre $k$ elementos. Para
simplificar la prueba, podemos exigir que los algoritmos
especifican una permutación entera, pero no vamos a
contar las comparaciones después que un de las $r$
valores fue encontrada.
3. Decidir si un elemento pertenece en k listas ordenadas de tamaño n/k
* Cotas superiores
* Si una sola lista contiene la valor buscada
- k búsquedas en el peor caso deterministico, que da
k\lg(n/k) comparaciones
- k/2 búsquedas en (promedio y en) el peor caso
aleatorio, que da k\lg(n/k)/2 comparaciones
* Si r
* Ejemplos de Problemas NP-Dificiles
1. *Maxcut*
- dado un grafe $G=(V,E)$
- encontrar una partition $(L,R)$ tq $L\cup R=V$ y que
*maximiza* la cantidad de aristas entre $L$ y $R$
- el problema es NP dificil
- se aproxima con un factor de dos con un algoritmo
aleatorizado en tiempo polinomial.
2. *mincut*
- dado un grafe $G=(V,E)$
- encontrar una partition $(L,R)$ tq $L\cup R=V$ y que
minimiza la cantidad de aristas entre $L$ y $R$
- el problema es NP dificil
* Relacion con la nocion de NP:
- El arbol representando la ejecucion de un algoritmo
non-deterministico en tiempo polynomial (i.e. NP) se
decomposa en dos partes, de altura polynomial $p(n)$:
- una parte de *decisiones* non-deterministica (fan-out)
- una parte de *verificacion* deterministica (straight)
- Si una solamente de las $2^{p(n))$ soluciones corresponde a
una solucion valida del problema, la aleatorizacion no
ayuda, pero si una proporcion constante
(e.g. 1/2,1/3,1/4,...) de las ramas corresponden a una
solucion correcta, existe un algoritmo aleatorizado que
resuelve el problema NP-dificil en tiempo polynomial *en
promedio*.
5 DONE Complejidad de un algoritmo aleatorizado
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-19 Tue 12:00-13:30>
* Considera algoritmos con comparaciones
- algoritmos deterministicos se pueden ver como arboles de
decisión.
- algoritmos aleatorios se pueden ver (de manera
intercambiable) como
- una distribución sobre los arboles de decisión,
- un arbol de decisión con algunos nodos "aleatorios".
- La complejidad en una instancia de un algoritmo aleatorio
es el promedio de la complejidad (en este instancia) de
los algoritmos deterministicos que le compasan:
C((A_r)_r,I) = E_r( C(A_r,I) )
- La complejidad en el peor caso de un algoritmo aleatorio
es el peor caso del promedio de la complejidad de los
algoritmos deterministicos que le composan:
C((A_r)_r) = \max_I C((A_r)_r,I) = \max_I E_r( C(A_r,I) )
6 DONE Tecnicas de cotas inferiores de la complejidad aleatorizada
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-19 Tue 12:00-13:30>
REFERENCIA: Capitulo 2, "Randomized Complexity" en "Concepts of
Combinatorial Optimization", pages 21--38, 2010.
[www.cs.uwaterloo.ca/ ... RandomizedComplexity]
* Notes:
1) Problema
- Strategia de adversario no funciona
- En algunos casos, teoría de códigos es suficiente
- e.g. búsqueda en arreglo ordenado
- eso es una cota inferior sobre el tamaño del
certificado
- En otros caso, teoría de códigos no es suficiente
- en particular, cuando el precio para verificar un
certificado es mas pequeño que de encontrarlo.
- En estos casos, utilizamos otras técnicas:
- teoría de juegos (que vamos a ver) y equilibro de Nash
- cotas sobre la comunicación en un sistema de
"Interactive Proof"
2) Algunas Notaciones Algebraicas
Sea:
- A una familia de $n_a$ algoritmos deterministicos
- $a$ un vector (0,...,0,1,0,...,0) de dimensión $n_a$
- $\alpha$ una distribución de probabilidad de dimensión $n_a$
- B una familia de $n_n$ instancias
- $b$ un vector (0,...,0,1,0,...,0) de dimensión $n_b$
- $\beta$ una distribución de probabilidad de dimensión $n_b$
- M una matriz de dimensión $n_a\times n_b$ tal que
$M_{a,b}$ es el costo del algoritmo $a$ sobre la instancia
$b$. Por definición,
- a^t M b = M_{a,b}
- \alpha^t M b es la complejidad en promedio (sobre el
aleatorio del algoritmo \alpha) de \alpha sobre b
- a^t M \beta es la complejidad en promedio (sobre la
distribución de instancias \beta) de a sobre \beta
- \alpha^t M \beta es la complejidad en promedio del
algoritmo aleatorizados \alpha sobre la distribución de
instancia \beta.
3) von Neuman's theorem: infsup = supinf = minmax = maxmin
1. OPCIONAL Existencia de $\tilde{\alpha}$ et $\tilde{\beta}$
Dado $\phi$ y $\psi$ definidas sobre $\mathbb{R}^m$ y $\mathbb{R}^n$ por
$$\phi(\alpha) = \sup_\beta \alpha ^T M \beta
\,\mbox{ y }\,
\psi(\beta) = \inf_\alpha \alpha ^T M \beta$$
Entonces:
- $\phi(\alpha) = \max_\beta \alpha ^T M \beta$
- $\psi(\beta) = \min_\alpha \alpha ^T M \beta$
- hay estrategias mixtas
- $\tilde{\alpha}$ por \A\
- $\tilde{\beta}$ por \B\
- tal que
- $\phi$ es a su mínima en $\tilde{\alpha}$ y
- $\psi$ es a su máxima en $\tilde{\beta}$.
2. Resultado de von Neuman:
Dado un juego $\Gamma$ definido por la matrica $M$~:
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
3. Interpretación:
+ Este resultado significa que si consideramos ambos
distribuciones sobre algoritmos y instancias, no
importa el orden del max o min:
- podemos elegir el mejor algoritmo (i.e. minimizar
sobre los algoritmos aleatorizados) y después
elegir la peor distribución de instancias para el
(i.e. maximizar sobre las distribuciones de
instancias), o al reves
- podemos elegir la peor distribución de instancias
(i.e. maximizar sobre las distribuciones de
instancias), y considerar el mejor algoritmo
(i.e. minimizar sobre los algoritmos
aleatorizados) para este distribución.
+ ATENCIÓN!!!! Veamos que
- El promedio (sobre las instancias) de las
complejidades (de los algoritmos) en el peor caso
- no es igual
- al peor caso (sobre las instancias) de la complejidad
en promedio (sobre el aleatorio del algoritmo)
- donde el segundo termo es realmente la complejidad de
un algoritmo aleatorizados.
+ Todavía falta la relación con la complejidad en el
peor caso $b$ de un algoritmo aleatorizados $\alpha$:
$\max_b \min_\alpha \alpha ^T M b$
4) Lema de Loomis
* Dado una estrategia aleatoria $\alpha$, emite una instancia
$b$ tal que $\alpha$ es tan mal en $b$ que en el
peor $\beta$.
$$
\forall \alpha \exists b,
\max_\beta \alpha^T M \beta = \alpha^T M b
$$
* Dado una distribución de instancias $\beta$, existe un
algoritmo deterministico $a$ tal que $a$ es tan
bien que el mejor algoritmo aleatorizados $\alpha$ sobre
la distribución de instancias $\beta$:
$$
\forall \beta \exists a,
\min_\alpha \alpha^T M \beta = a^T M \beta
$$
* Interpretación:
+ En frente a una distribución de instancias especifica,
siempre existe un algoritmo deterministico óptima en
comparación con los algoritmos aleatorizados (que
incluen los deterministicos).
+ En frente a un algoritmo aleatorizados, siempre existe una
instancia tan mal que la peor distribución de
instancias.
5) Príncipe de Yao
* Del lema de Loomis podemos concluir que
$$
\max_\beta \alpha^T M \beta = \max_b \alpha^T M b
$$
$$
\min_\alpha \alpha^T M \beta = \min_a a^T M \beta
$$
* Del resultado de von Neuman sabemos que maxmin=minmax
(sobre \alpha y \beta):
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
* Entonces
$$
\min_alpha \max_b \alpha^T M b
= (Loomis)
\min_\alpha \max_\beta \alpha ^T M \beta
= (von Neuman)
\max_\beta \min_\alpha \alpha ^T M \beta
= (Loomis)
\max_\beta \min_a a^T M \beta
$$
* Interpretación
\min_\alpha \max_b \alpha^T M b
\_______ La complejidad
\______ _______ ________ del mejor algoritmo aleatorizado
\___ ___________ en el peor caso
es igual a
\max_\beta \min_a \alpha^T M b
\_______ La complejidad
\___ ___________ del mejor algoritmo deterministico
\______ _______ ________ sobre la peor distribución de instancias
"El peor caso del mejor algoritmo aleatorizado
corresponde a
la peor distribución para el mejor algoritmo deterministico."
* Ejemplos de cotas inferiores:
1. Decidir si un elemento pertenece en una lista ordenadas de tamaño n
- Cual es el peor caso $b$ de un algoritmo aleatorizado $\alpha$?
- Buscamos una distribución $\beta_0$ que es mala para todos
los algoritmos deterministicos $a$ (del modelo de comparaciones)
- Consideramos la distribución uniforma.
- Cada algoritmo deterministico se puede representar como un
arbol de decisión (binario) con $2n+1$ hojas.
- Ya utilizamos para la cota inferior deterministica que la
altura de un tal arbol es al menos $\lg(2n+1)\in\Omega(\lg
n)$. Esta propiedad se muestra por recurrencia.
- De manera similar, se puede mostrar por recurrencia que la
altura en promedio de un tal arbol binario es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, la complejidad promedio de cada algoritmo
deterministico $a$ sobre $\beta_0$ es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, utilizando el principie de Yao, la complejidad en
el peor caso de un algoritmo aleatorizado en el modelo de
comparaciones es al menos $\lg(2n+1)\in\Omega(\lg n)$.
- El corolario interesante, es que el algoritmo
deterministico de búsqueda binaria es *oprima* a dentro de
la clase mas general de algoritmos aleatorizados.
2. Decidir si un elemento pertenece en un lista desordenada de tamaño k
* Si una sola instancia de la valor buscada ($r=1$)
* Cotas superiores
- k en el peor caso deterministico
- (k+1)/2 en el peor caso aleatorio
- con una dirección al azar
- con lg(k!) bits aleatorios
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición, y que
consideran todas las posiciones en el peor caso:
entonces cada algoritmo puede ser representado por una
permutación sobre $k$.
- Dado un algoritmo deterministico $a$, para cada
$i\in[1,k]$, hay una instancia sobre cual el performe
$i$ comparaciones. Entonces, su complejidad en promedio
en este instancia es $\sum_i i/k$, que es $k(k+1)/2k =
(k+1)/2$. Como eso es verdad para todos los algoritmos
deterministicos, es verdad para el mejor de ellos
también.
- Entonces, utilizando el principio de Yao, la complejidad
en el peor caso de un algoritmo aleatorizado en el
modelo de comparaciones es al menos $(k+1)/2$.
* Si r instancias de la valor buscada
* Cotas superiores
- k-r en el peor caso deterministico
- O(k/r) en (promedio y en) el peor caso aleatorio
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición.
- De verdad, no algoritmo tiene de considerar mas
posiciones que $k-r+1$, entonces hay menos algoritmos
que de permutaciones sobre $k$ elementos. Para
simplificar la prueba, podemos exigir que los algoritmos
especifican una permutación entera, pero no vamos a
contar las comparaciones después que un de las $r$
valores fue encontrada.
3. Decidir si un elemento pertenece en k listas ordenadas de tamaño n/k
* Cotas superiores
* Si una sola lista contiene la valor buscada
- k búsquedas en el peor caso deterministico, que da
k\lg(n/k) comparaciones
- k/2 búsquedas en (promedio y en) el peor caso
aleatorio, que da k\lg(n/k)/2 comparaciones
* Si r
* Formalización
Algoritmos clásicos Non clásicos
------------------------+---------------
Siempre hacen lo mismo aleatorizados
Nunca se equivocan Monte Carlo
Siempre terminan Las Vegas
* Clasificación de los algoritmos *de decisión* aleatorizados
1. ProbabilÃ-stico: Monte Carlo
- P(error) < épsilon
- Ejemplo:
- detección de cliquas
- Se puede considerar también variantes mas fines:
- two-sided error ( => clase de complejidad BPP)
- P(accept | negative) < \epsilon
- P(refuse | negative) > 1-\epsilon
- P(accept | positive) > 1-\epsilon
- P(refuse | positive) < epsilon
- One-sided error
- P(accept | negative) < epsilon
- P(refuse | negative) > 1 -\epsilon
- P(accept | positive) = 1
- P(refuse | positive) = 0
2. ProbabilÃ-stico: Las Vegas
- Tiempo es una variable aleatoria
- Ejemplos:
- determinar primalidad [Miller Robin]
- búsqueda en arreglo desordenado
- intersección de arreglos ordenados
- etc...
* Relación
- Si se puede verificar el resultado en tiempo razonable,
Monte Carlos iterado hasta correcto => Las Vegas
8 CANC Primalidad
~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-21 Thu 12:00-13:30>
REFERENCIAS:
- Primalidad: Capitulo 14.6 en "Randomized Algorithms", de Rajeev Motwani and Prabhakar Raghavan.
- [en.wikipedia.org/ ... lity_test#Complexity]
* Algoritmo "Random Walks" para SAT
1. eliga cualquieras valores $x_1,\ldots,x_n$
2. si todas las clausilas son satisfechas,
- accepta
3. sino
- eliga una clausula non satisfecha (deterministicamente
o no)
- eliga una de las variables de esta closula.
4. Repite es $r$ veces.
* PRIMES is in coNP
si $x\in coNP$, eliga non-deterministicamente una
decomposicion de $x$ y verificalo.
* PRIMES is in NP (hence in NP\cap coNP)
In 1975, Vaughan Pratt showed that there existed a
certificate for primality that was checkable in polynomial
time, and thus that PRIMES was in NP, and therefore in NP Á
coNP.
* PRIMES in coRP
The subsequent discovery of the Solovay-Strassen and
Miller-Rabin algorithms put PRIMES in coRP.
* PRIMES in ZPP = RP \cap coRP
In 1992, the Adleman-Huang algorithm reduced the complexity
to ZPP = RP Á coRP, which superseded Pratt's result.
* PRIMES in QP
The cyclotomy test of Adleman, Pomerance, and Rumely from
1983 put PRIMES in QP (quasi-polynomial time), which is not
known to be comparable with the classes mentioned above.
* PRIMES in P
Because of its tractability in practice, polynomial-time
algorithms assuming the Riemann hypothesis, and other
similar evidence, it was long suspected but not proven that
primality could be solved in polynomial time. The existence
of the AKS primality test finally settled this long-standing
question and placed PRIMES in P.
* PRIMES \in NC? PRIMES \in L?
PRIMES is not known to be P-complete, and it is not known
whether it lies in classes lying inside P such as NC or L.
9 CANC Clases de complejidad aleatorizada :BONUS:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-21 Thu 12:00-13:30>
9.1 RP
=======
- "A *precise* polynomial-time bounded nondeterministic Turing
Machine", aka "maquina de Turing non-deterministica acotadada
polinomialemente *precisa*", es una maquina tal que su
ejecucion sobre las entradas de tamaño n toman tiempo p(n)
*todas*.
- "A *polynomial Monte-Carlo Turing machine*", aka una
"*maquina de Turing de Monte-Carlo* polynomial" para el
idioma $L$, es una tal maquina tal que
- si $x\in L$, al menos la mitad de los $2^{p(|x|)}$ caminos
acceptan $x$
- si $x\not\in L$, *todas* los caminos rechazan $x$.
- La definicion corresponde exactamente a la definicion de
algoritmos de Monte-Carlo. La classe de idiomas reconocidos
por una *maquina de Turing de Monte-Carlo* polynomial es
$RP$.
- $P \subset BP \subset NP$:
- un algoritmo en $P$ accepta con todos sus caminos cuando
una palabra $x$ es en $L$, que es "al menos" la mitad.
- un algoritmo en $NP$ accepta con al menos un camino: un
algoritmo en $RP$ accepta con al menos la mitad de sus
caminos.
9.2 ZPP
========
- ZPP = RP \cap coRP
- Primes \in ZPP
9.3 PP
=======
- Maquina que, si $x\in L$, accepta en la mayoridad de sus
entradas.
- PP probablemente no en NP
- PP probablemente no en RP
9.4 BPP
========
- BPP = { L, \forall x,
- x\in L \implies 3/4 de los caminos acceptan x
- x\not\in L \implies 3/4 de los caminos rechazan x
- RP \subset BPP \subset PP
- BPP = coBPP
=====================================
Author: Jérémy Barbay
Date: 2010-11-09 11:28:36 CLST
* REFERENCIA:
- Capitulo 1 en "Randomized Algorithms", de Rajeev Motwani and Prabhakar Raghavan.
Table of Contents
=================
1 Definiciones
2 El poder de un algoritmo aleatorizado
3 Aleatorizacion de la entrada
3.1 SkipLists
3.1.1 Paginamiento al Azar
3.1.2 Arboles Binarios de Busqueda aleatorizados
3.1.3 Complejidad Probabilistica: cotas inferiores
4 *Relacion con Problemas NP-Dificiles*
5 Complejidad de un algoritmo aleatorizado
6 Tecnicas de cotas inferiores de la complejidad aleatorizada
7 Algoritmos tipo Monte Carlo y Las Vegas
8 Primalidad
9 Clases de complejidad aleatorizada
9.1 RP
9.2 ZPP
9.3 PP
9.4 BPP
1 DONE Definiciones
~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-14 Thu 12:00-13:30>
- *Algoritmos deterministico*
- algoritmo que usa solamente instrucciones
*deterministicas*.
- algoritmo de cual la ejecucion (y, entonces, el
rendimiento) depende solamente del input.
- *Algoritmos aleatorizados*
- algoritmo que usa una instruccion *aleatorizada*
(potentialemente muchas veces)
- una distribucion de probabilidades sobre una familia de
algoritmos deterministicos.
- *Análisis probabilistica*
- analysis del rendimiento de un algoritmo, en promedio
sobre
- el aleatorio de la entrada, o
- el aleatorio del algoritmo, o
- los dos.
- veamos que son nociones equivalentes.
2 DONE El poder de un algoritmo aleatorizado
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-14 Thu 12:00-13:30>
- Nota: Trae los juguetes/cajas de colores, con un tesoro a esconder a dentro.
Ejemplos de algoritmos o estructuras de datos aleatorizados
1. *hidden coin*
- Decidir si un elemento pertenece en un lista
desordenada de tamaño k, o si hay una moneda a dentro
de una de las $k$ caja.
- cual son las complejidades determinisitica y
aleatorizada del problema de encontrar *una* moneda,
con $c$ la cantidad de monedas,
- si $c=1$?
- si $c=n-1$?
- si $c=n/2$?
- Respuestas:
- Si una sola instancia de la valor buscada
- k en el peor caso deterministico
- k/2 en (promedio y en) el peor caso aleatorio
- con una dirección al azar
- con lg(k!) bits aleatorios
- Si r instancias de la valor buscada
- k-r en el peor caso deterministico
- O(k/r) en (promedio y en) el peor caso aleatorio
3. Decidir si un elemento pertenece en una lista ordenadas
de tamaño n
* \Theta(\lg n) comparaciones en ambos casos,
deterministico y probabilÃ-stico.
4. *problema de union*
* Decidir si un elemento pertenece en una de las k listas
ordenadas de tamaño n
* Si una sola lista contiene la valor buscada
- k búsquedas en el peor caso deterministico, que da
k\lg(n) comparaciones
- k/2 búsquedas en (promedio y en) el peor caso
aleatorio, que da k\lg(n)/2 comparaciones
* Si r
* Independencia de la distribucion de la entrada
- Si el input sigue una distribucion non-conocida, el input
perturbado tiene una distribucion conocida (para una
perturbacion bien elegida)
- Ejemplo:
- flip $b$ de una bit con probabilidad $p$ que puede ser
distinta de $1/2$.
- suma-lo modulo 1 con un otro bit aleatorizado, con
probabilidad $1/2$ de ser uno.
- la suma es igual a uno con probabilidad $1/2$.
* Estructuras de datos aleatorizadas
- *funciones de hash*:
- estructura de datos aleatorizada,
- donde (a,b) son elegidos al azar.
- *skiplists*
- estructura de datos aleatorizada,
- que simula en promedio un arbol binario
3.1 DONE SkipLists
===================
1) Estructuras de datos para diccionarios
- [X] Arreglo ordenado
- [ ] "Move To Front" list (did they see it already?)
- [X] Arboles binarios
- [X] Arboles binarios aleatorizados
- [X] Arboles 2-3 ( they saw it already?)
- [X] Red-Black Trees ( they saw it already?)
- [X] AVL
- [X] Skip List
- [ ] Splay trees
2) Skip Lists
1. Motivación
- un arbol binario con entradas aleatorizadas tienen una
altura O(lg n), pero eso supone un orden de input
aleatorizados.
- El objetivo de las "skip lists" es de poner el aleatorio
a dentro de la estructura.
- también, es el equivalente de una búsqueda binaria en
listas via un resumen de resumen de resumen...
2. Definición
- una skip-list de altura $h$ para un diccionario $D$ de
$n$ elementos es una familia de lists $S_0,\ldots,S_h$ y
un puntero al primero elemento de $S_h$, tal que
- $S_0$ contiene $D$;
- cada $S_i$ contiene un subconjunto aleatorio de $S_{i-1}$
(en promedio la mitad)
- se puede navegar de la izquierda a la derecha, y de la
cima hasta abajo.
- se puede ver como $n$ torres de altura aleatorizadas,
conectadas horizontalmente con punteros de la
izquierda a la derecha.
- la información del diccionario están solamente en S_0 (no
se duplica)
3. Ejemplo
4 X - - - - - - -> X
3 X - -> X - - - -> X
2 X - -> X X -> X -> X
1 X X -> X X -> X -> X
0 X X X X X X X X X
---+---------+----+----+----+----+----+----+----+--------
-\infty 10 20 30 40 50 60 70 \infty
4. Operaciones
* Search(x):
- Start a the first element of $S_h$
- while not in $S_0$
- go down one level
- go right till finding a key larger than x
* Insert(x)
- Search(x)
- create a tower of random height (p=1/2 to increase
height, typically)
- insert it in all the lists it cuts.
* Delete(x)
- Search(x)
- remove tower from all lists.
5. Ejemplos
* Insert(55) con secuencia aleatora (1,0)
4 X - - - - - - - -> X
3 X - -> X - - - - -> X
2 X - -> X X - -> X -> X
1 X X -> X X *->* *X* X -> X
0 X X X X X X *X* X X X
---+---------+----+----+----+----+------+------+----+----+--------
-\infty 10 20 30 40 50 *55* 60 70 \infty
* Insert(25) con (1,1,1,1,0)
5 *X* - - - - - - - - *->* *X*
4 X - *->* *X* - - - - - -> X
3 X - *->* *X* X - - - - -> X
2 X - *->* *X* X X - -> X -> X
1 X X *->* *X* X X -> X X -> X
0 X X X *X* X X X X X X X
---+---------+----+------+------+----+----+----+----+----+------+--------
-\infty 10 20 *25* 30 40 50 55 60 70 \infty
* Delete(60)
5 X - - - - - - - -> X
4 X - -> X - - - - -> X
3 X - -> X X - - - -> X
2 X - -> X X X - - *->* X
1 X X -> X X X -> X -> X
0 X X X X X X X X X X
---+---------+----+----+----+----+----+----+----+------+--------
-\infty 10 20 25 30 40 50 55 70 \infty
6. Analisis
* Espacio: Cuanto nodos en promedio?
- cuanto nodos en lista S_i?
- $n/2^i$ en promedio
- Summa sobre todos los niveles
- $n \sum 1/2^i < 2n$
* Tiempo:
- altura promedio es O(\lg n)
- tiempo promedio es O(\lg n)
3.1.1 DONE Paginamiento al Azar :OPTIONAL:
------------------------------------------
- REFERENCIA:
- Capitulo 3 en "Online Computation and Competitive Analysis", de
Allan Borodin y Ran El-Yaniv
- Capitulo 13 en "Randomized Algorithms", de Rajeev Motwani and
Prabhakar Raghavan, p. 368
1) Tipos de Adversarios (cf p372 [Motwani Raghavan]
* Veamos en el caso deterministico un tipo de adversario
offline, como medida de dificultad para las instancias online.
Para el problema de paginamiento con k paginas, el ratio
óptima entre un algoritmo online y offline es de $k$
(e.g. entre LRU y LFD).
* DEFINICIÓN:
En el caso aleatorizado, se puede considerar mas tipos de
adversarios, cada uno definiendo una medida de dificultad y
un modelo de complejidad.
1. Adversario "Oblivious" ("Oblivious Adversary")
El adversario conoce $A$ pero no $R$: el elija su instancia
completamente al inicial, antes de la ejecución online del
algoritmo.
2. Adversario Offline adaptativo
Para este definición, es mas fácil de pensar a un
adversario como un agente distinto del algoritmo offline
con quien se compara el algoritmo online.
El adversario conoce $A$ en total, pero $R$ online, y le
utiliza para generar una instancia peor $I$. Este instancia
$I$ es utilizada de nuevo para ejecutar el algoritmo
offline (quien conoce el futuro) y producir las
complejidades (a cada instante online) con cual comparar la
complejidad del algoritmo online.
3. Adversario Online adaptativo
En este definición, el algoritmo conoce $A$ en total,
construir la instancia $I$ online como en el caso
precedente, pero tiene de tiene de resolverla online también
(de una manera, no se ve en el futuro).
* Comparación de los Tipos de adversarios.
- Por las definiciones, es claro que
- el adversario offline adaptativo
- es mas poderoso que
- el adversario online adaptativo
- es mas poderoso que
- el adversario oblivious
* Competitiva Ratios
* Para un algoritmo online $A$
- Para cada tipo de adversario se define un competitivo ratio:
- C_A^{obl}: competitivo ratio con adversario oblivious
- C_A^{aon}: competitivo ratio con adversario adaptativo online
- C_A^{aof}: competitivo ratio con adversario adaptativo offline
- Es obvio que, para $A$ fijada, considerando un adversario
mas poderoso va aumentar el competitivo ratio:
C_A^{obl} \leq C_A^{aon} \leq C_A^{aof}
* Para un problema
- el competitivo ratio de un problema es el competitivo
ratio mÃ-nima sobre todos los algoritmos correctos para
este problema.
C^{obl} \leq C^{aon} \leq C^{aof} \leq C^{det}
- donde C^{det} es el competitivo ratio de un algoritmo
online deterministico.
3.1.2 DONE Arboles Binarios de Busqueda aleatorizados
------------------------------------------------------
- Conrado MartÃ-nez. Randomized binary search trees. Algorithms
Seminar. Universitat Politecnica de Catalunya, Spain, 1996.
- Conrado MartÃ-nez and Salvador Roura. Randomized binary search
trees. J. ACM, 45(2):288–323, 1998.
- [en.wikipedia.org/ ... d_binary_search_tree]
3.1.3 DONE Complejidad Probabilistica: cotas inferiores
--------------------------------------------------------
* REFERENCIA:
- Capitulo 1 en "Randomized Algorithms", de Rajeev Motwani and Prabhakar Raghavan.
* Notes:
1) Problema
- Strategia de adversario no funciona
- En algunos casos, teorÃ-a de códigos es suficiente
- e.g. búsqueda en arreglo ordenado
- eso es una cota inferior sobre el tamaño del
certificado
- En otros caso, teorÃ-a de códigos no es suficiente
- en particular, cuando el precio para verificar un
certificado es mas pequeño que de encontrarlo.
- En estos casos, utilizamos otras técnicas:
- teorÃ-a de juegos (que vamos a ver) y equilibro de Nash
- cotas sobre la comunicación en un sistema de
"Interactive Proof"
2) Algunas Notaciones Algebraicas
Sea:
- A una familia de $n_a$ algoritmos deterministicos
- $a$ un vector (0,...,0,1,0,...,0) de dimensión $n_a$
- $\alpha$ una distribución de probabilidad de dimensión $n_a$
- B una familia de $n_n$ instancias
- $b$ un vector (0,...,0,1,0,...,0) de dimensión $n_b$
- $\beta$ una distribución de probabilidad de dimensión $n_b$
- M una matriz de dimensión $n_a\times n_b$ tal que M_{a,b}
es el costo del algoritmo $a$ sobre la instancia $b$.
Por definición,
- a^t M b = M_{a,b}
- \alpha^t M b es la complejidad en promedio (sobre el
aleatorio del algoritmo \alpha) de \alpha sobre b
- a^t M \beta es la complejidad en promedio (sobre la
distribución de instancias \beta) de a sobre \beta
- \alpha^t M \beta es la complejidad en promedio del
algoritmo aleatorizados \alpha sobre la distribución de
instancia \beta.
3) von Neuman's theorem: infsup = supinf = minmax = maxmin
1. OPCIONAL Existencia de $\tilde{\alpha}$ et $\tilde{\beta}$
Dado $\phi$ y $\psi$ definidas sobre $\mathbb{R}^m$ y $\mathbb{R}^n$ por
$$\phi(\alpha) = \sup_\beta \alpha ^T M \beta
\,\mbox{ y }\,
\psi(\beta) = \inf_\alpha \alpha ^T M \beta$$
Entonces:
- $\phi(\alpha) = \max_\beta \alpha ^T M \beta$
- $\psi(\beta) = \min_\alpha \alpha ^T M \beta$
- hay estrategias mixtas
- $\tilde{\alpha}$ por \A\
- $\tilde{\beta}$ por \B\
- tal que
- $\phi$ es a su mÃ-nima en $\tilde{\alpha}$ y
- $\psi$ es a su máxima en $\tilde{\beta}$.
2. Resultado de von Neuman:
Dado un juego $\Gamma$ definido por la matrica $M$~:
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
3. Interpretación:
+ Este resultado significa que si consideramos ambos
distribuciones sobre algoritmos y instancias, no
importa el orden del max o min:
- podemos elegir el mejor algoritmo (i.e. minimizar
sobre los algoritmos aleatorizados) y después
elegir la peor distribución de instancias para el
(i.e. maximizar sobre las distribuciones de
instancias), o al reves
- podemos elegir la peor distribución de instancias
(i.e. maximizar sobre las distribuciones de
instancias), y considerar el mejor algoritmo
(i.e. minimizar sobre los algoritmos
aleatorizados) para este distribución.
+ ATENCIÓN!!!! Veamos que
- El promedio (sobre las instancias) de las
complejidades (de los algoritmos) en el peor caso
- no es igual
- al peor caso (sobre las instancias) de la complejidad
en promedio (sobre el aleatorio del algoritmo)
- donde el segundo termo es realmente la complejidad de
un algoritmo aleatorizados.
+ TodavÃ-a falta la relación con la complejidad en el
peor caso $b$ de un algoritmo aleatorizados $\alpha$:
$\max_b \min_\alpha \alpha ^T M b$
4) Lema de Loomis
* Dado una estrategia aleatoria $\alpha$, emite una instancia
$b$ tal que $\alpha$ es tan mal en $b$ que en el
peor $\beta$.
$$
\forall \alpha \exists b,
\max_\beta \alpha^T M \beta = \alpha^T M b
$$
* Dado una distribución de instancias $\beta$, existe un
algoritmo deterministico $a$ tal que $a$ es tan
bien que el mejor algoritmo aleatorizados $\alpha$ sobre
la distribución de instancias $\beta$:
$$
\forall \beta \exists a,
\min_\alpha \alpha^T M \beta = a^T M \beta
$$
* Interpretación:
+ En frente a una distribución de instancias especifica,
siempre existe un algoritmo deterministico óptima en
comparación con los algoritmos aleatorizados (que
incluen los deterministicos).
+ En frente a un algoritmo aleatorizados, siempre existe
una instan ca tan mal que la pero distribución de
instancias.
5) PrÃ-ncipe de Yao
* Del leima de Loomis podemos concluir que
$$
\max_\beta \alpha^T M \beta = \max_b \alpha^T M b
$$
$$
\min_\alpha \alpha^T M \beta = \min_a a^T M \beta
$$
* Del resultado de von Neuman sabemos que maxmin=minmax
(sobre \alpha y \beta):
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
* Entonces
$$
\min_alpha \max_b \alpha^T M b
= (Loomis)
\min_\alpha \max_\beta \alpha ^T M \beta
= (von Neuman)
\max_\beta \min_\alpha \alpha ^T M \beta
= (Loomis)
\max_\beta \min_a a^T M \beta
$$
* Interpretación
\min_\alpha \max_b \alpha^T M b
\_______ La complejidad
\______ _______ ________ del mejor algoritmo aleatorizado
\___ ___________ en el peor caso
es igual a
\max_\beta \min_a \alpha^T M b
\_______ La complejidad
\___ ___________ del mejor algoritmo deterministico
\______ _______ ________ sobre la peor distribución de instancias
"El peor caso del mejor algoritmo aleatorizado
corresponde a
la peor distribución para el mejor algoritmo deterministico."
* Ejemplos de cotas inferiores:
1. Decidir si un elemento pertenece en una lista ordenadas de tamaño n
- Cual es el peor caso $b$ de un algoritmo aleatorizado $\alpha$?
- Buscamos una distribución $\beta_0$ que es mala para todos
los algoritmos deterministicos $a$ (del modelo de comparaciones)
- Consideramos la distribución uniforma.
- Cada algoritmo deterministico se puede representar como un
arbol de decisión (binario) con $2n+1$ hojas.
- Ya utilizamos para la cota inferior deterministica que la
altura de un tal arbol es al menos $\lg(2n+1)\in\Omega(\lg
n)$. Esta propiedad se muestra por recurrencia.
- De manera similar, se puede mostrar por recurrencia que la
altura en promedio de un tal arbol binario es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, la complejidad promedio de cada algoritmo
deterministico $a$ sobre $\beta_0$ es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, utilizando el principie de Yao, la complejidad en
el peor caso de un algoritmo aleatorizado en el modelo de
comparaciones es al menos $\lg(2n+1)\in\Omega(\lg n)$.
- El corolario interesante, es que el algoritmo
deterministico de búsqueda binaria es *oprima* a dentro de
la clase mas general de algoritmos aleatorizados.
2. Decidir si un elemento pertenece en un lista desordenada de tamaño k
* Si una sola instancia de la valor buscada ($r=1$)
* Cotas superiores
- k en el peor caso deterministico
- (k+1)/2 en el peor caso aleatorio
- con una dirección al azar
- con lg(k!) bits aleatorios
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición, y que
consideran todas las posiciones en el peor caso:
entonces cada algoritmo puede ser representado por una
permutación sobre $k$.
- Dado un algoritmo deterministico $a$, para cada
$i\in[1,k]$, hay una instancia sobre cual el performe
$i$ comparaciones. Entonces, su complejidad en promedio
en este instancia es $\sum_i i/k$, que es $k(k+1)/2k =
(k+1)/2$. Como eso es verdad para todos los algoritmos
deterministicos, es verdad para el mejor de ellos
también.
- Entonces, utilizando el principio de Yao, la complejidad
en el peor caso de un algoritmo aleatorizado en el
modelo de comparaciones es al menos $(k+1)/2$.
* Si r instancias de la valor buscada
* Cotas superiores
- k-r en el peor caso deterministico
- O(k/r) en (promedio y en) el peor caso aleatorio
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición.
- De verdad, no algoritmo tiene de considerar mas
posiciones que $k-r+1$, entonces hay menos algoritmos
que de permutaciones sobre $k$ elementos. Para
simplificar la prueba, podemos exigir que los algoritmos
especifican una permutación entera, pero no vamos a
contar las comparaciones después que un de las $r$
valores fue encontrada.
3. Decidir si un elemento pertenece en k listas ordenadas de tamaño n/k
* Cotas superiores
* Si una sola lista contiene la valor buscada
- k búsquedas en el peor caso deterministico, que da
k\lg(n/k) comparaciones
- k/2 búsquedas en (promedio y en) el peor caso
aleatorio, que da k\lg(n/k)/2 comparaciones
* Si r
* Ejemplos de Problemas NP-Dificiles
1. *Maxcut*
- dado un grafe $G=(V,E)$
- encontrar una partition $(L,R)$ tq $L\cup R=V$ y que
*maximiza* la cantidad de aristas entre $L$ y $R$
- el problema es NP dificil
- se aproxima con un factor de dos con un algoritmo
aleatorizado en tiempo polinomial.
2. *mincut*
- dado un grafe $G=(V,E)$
- encontrar una partition $(L,R)$ tq $L\cup R=V$ y que
minimiza la cantidad de aristas entre $L$ y $R$
- el problema es NP dificil
* Relacion con la nocion de NP:
- El arbol representando la ejecucion de un algoritmo
non-deterministico en tiempo polynomial (i.e. NP) se
decomposa en dos partes, de altura polynomial $p(n)$:
- una parte de *decisiones* non-deterministica (fan-out)
- una parte de *verificacion* deterministica (straight)
- Si una solamente de las $2^{p(n))$ soluciones corresponde a
una solucion valida del problema, la aleatorizacion no
ayuda, pero si una proporcion constante
(e.g. 1/2,1/3,1/4,...) de las ramas corresponden a una
solucion correcta, existe un algoritmo aleatorizado que
resuelve el problema NP-dificil en tiempo polynomial *en
promedio*.
5 DONE Complejidad de un algoritmo aleatorizado
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-19 Tue 12:00-13:30>
* Considera algoritmos con comparaciones
- algoritmos deterministicos se pueden ver como arboles de
decisión.
- algoritmos aleatorios se pueden ver (de manera
intercambiable) como
- una distribución sobre los arboles de decisión,
- un arbol de decisión con algunos nodos "aleatorios".
- La complejidad en una instancia de un algoritmo aleatorio
es el promedio de la complejidad (en este instancia) de
los algoritmos deterministicos que le compasan:
C((A_r)_r,I) = E_r( C(A_r,I) )
- La complejidad en el peor caso de un algoritmo aleatorio
es el peor caso del promedio de la complejidad de los
algoritmos deterministicos que le composan:
C((A_r)_r) = \max_I C((A_r)_r,I) = \max_I E_r( C(A_r,I) )
6 DONE Tecnicas de cotas inferiores de la complejidad aleatorizada
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-19 Tue 12:00-13:30>
REFERENCIA: Capitulo 2, "Randomized Complexity" en "Concepts of
Combinatorial Optimization", pages 21--38, 2010.
[www.cs.uwaterloo.ca/ ... RandomizedComplexity]
* Notes:
1) Problema
- Strategia de adversario no funciona
- En algunos casos, teoría de códigos es suficiente
- e.g. búsqueda en arreglo ordenado
- eso es una cota inferior sobre el tamaño del
certificado
- En otros caso, teoría de códigos no es suficiente
- en particular, cuando el precio para verificar un
certificado es mas pequeño que de encontrarlo.
- En estos casos, utilizamos otras técnicas:
- teoría de juegos (que vamos a ver) y equilibro de Nash
- cotas sobre la comunicación en un sistema de
"Interactive Proof"
2) Algunas Notaciones Algebraicas
Sea:
- A una familia de $n_a$ algoritmos deterministicos
- $a$ un vector (0,...,0,1,0,...,0) de dimensión $n_a$
- $\alpha$ una distribución de probabilidad de dimensión $n_a$
- B una familia de $n_n$ instancias
- $b$ un vector (0,...,0,1,0,...,0) de dimensión $n_b$
- $\beta$ una distribución de probabilidad de dimensión $n_b$
- M una matriz de dimensión $n_a\times n_b$ tal que
$M_{a,b}$ es el costo del algoritmo $a$ sobre la instancia
$b$. Por definición,
- a^t M b = M_{a,b}
- \alpha^t M b es la complejidad en promedio (sobre el
aleatorio del algoritmo \alpha) de \alpha sobre b
- a^t M \beta es la complejidad en promedio (sobre la
distribución de instancias \beta) de a sobre \beta
- \alpha^t M \beta es la complejidad en promedio del
algoritmo aleatorizados \alpha sobre la distribución de
instancia \beta.
3) von Neuman's theorem: infsup = supinf = minmax = maxmin
1. OPCIONAL Existencia de $\tilde{\alpha}$ et $\tilde{\beta}$
Dado $\phi$ y $\psi$ definidas sobre $\mathbb{R}^m$ y $\mathbb{R}^n$ por
$$\phi(\alpha) = \sup_\beta \alpha ^T M \beta
\,\mbox{ y }\,
\psi(\beta) = \inf_\alpha \alpha ^T M \beta$$
Entonces:
- $\phi(\alpha) = \max_\beta \alpha ^T M \beta$
- $\psi(\beta) = \min_\alpha \alpha ^T M \beta$
- hay estrategias mixtas
- $\tilde{\alpha}$ por \A\
- $\tilde{\beta}$ por \B\
- tal que
- $\phi$ es a su mínima en $\tilde{\alpha}$ y
- $\psi$ es a su máxima en $\tilde{\beta}$.
2. Resultado de von Neuman:
Dado un juego $\Gamma$ definido por la matrica $M$~:
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
3. Interpretación:
+ Este resultado significa que si consideramos ambos
distribuciones sobre algoritmos y instancias, no
importa el orden del max o min:
- podemos elegir el mejor algoritmo (i.e. minimizar
sobre los algoritmos aleatorizados) y después
elegir la peor distribución de instancias para el
(i.e. maximizar sobre las distribuciones de
instancias), o al reves
- podemos elegir la peor distribución de instancias
(i.e. maximizar sobre las distribuciones de
instancias), y considerar el mejor algoritmo
(i.e. minimizar sobre los algoritmos
aleatorizados) para este distribución.
+ ATENCIÓN!!!! Veamos que
- El promedio (sobre las instancias) de las
complejidades (de los algoritmos) en el peor caso
- no es igual
- al peor caso (sobre las instancias) de la complejidad
en promedio (sobre el aleatorio del algoritmo)
- donde el segundo termo es realmente la complejidad de
un algoritmo aleatorizados.
+ Todavía falta la relación con la complejidad en el
peor caso $b$ de un algoritmo aleatorizados $\alpha$:
$\max_b \min_\alpha \alpha ^T M b$
4) Lema de Loomis
* Dado una estrategia aleatoria $\alpha$, emite una instancia
$b$ tal que $\alpha$ es tan mal en $b$ que en el
peor $\beta$.
$$
\forall \alpha \exists b,
\max_\beta \alpha^T M \beta = \alpha^T M b
$$
* Dado una distribución de instancias $\beta$, existe un
algoritmo deterministico $a$ tal que $a$ es tan
bien que el mejor algoritmo aleatorizados $\alpha$ sobre
la distribución de instancias $\beta$:
$$
\forall \beta \exists a,
\min_\alpha \alpha^T M \beta = a^T M \beta
$$
* Interpretación:
+ En frente a una distribución de instancias especifica,
siempre existe un algoritmo deterministico óptima en
comparación con los algoritmos aleatorizados (que
incluen los deterministicos).
+ En frente a un algoritmo aleatorizados, siempre existe una
instancia tan mal que la peor distribución de
instancias.
5) Príncipe de Yao
* Del lema de Loomis podemos concluir que
$$
\max_\beta \alpha^T M \beta = \max_b \alpha^T M b
$$
$$
\min_\alpha \alpha^T M \beta = \min_a a^T M \beta
$$
* Del resultado de von Neuman sabemos que maxmin=minmax
(sobre \alpha y \beta):
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
* Entonces
$$
\min_alpha \max_b \alpha^T M b
= (Loomis)
\min_\alpha \max_\beta \alpha ^T M \beta
= (von Neuman)
\max_\beta \min_\alpha \alpha ^T M \beta
= (Loomis)
\max_\beta \min_a a^T M \beta
$$
* Interpretación
\min_\alpha \max_b \alpha^T M b
\_______ La complejidad
\______ _______ ________ del mejor algoritmo aleatorizado
\___ ___________ en el peor caso
es igual a
\max_\beta \min_a \alpha^T M b
\_______ La complejidad
\___ ___________ del mejor algoritmo deterministico
\______ _______ ________ sobre la peor distribución de instancias
"El peor caso del mejor algoritmo aleatorizado
corresponde a
la peor distribución para el mejor algoritmo deterministico."
* Ejemplos de cotas inferiores:
1. Decidir si un elemento pertenece en una lista ordenadas de tamaño n
- Cual es el peor caso $b$ de un algoritmo aleatorizado $\alpha$?
- Buscamos una distribución $\beta_0$ que es mala para todos
los algoritmos deterministicos $a$ (del modelo de comparaciones)
- Consideramos la distribución uniforma.
- Cada algoritmo deterministico se puede representar como un
arbol de decisión (binario) con $2n+1$ hojas.
- Ya utilizamos para la cota inferior deterministica que la
altura de un tal arbol es al menos $\lg(2n+1)\in\Omega(\lg
n)$. Esta propiedad se muestra por recurrencia.
- De manera similar, se puede mostrar por recurrencia que la
altura en promedio de un tal arbol binario es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, la complejidad promedio de cada algoritmo
deterministico $a$ sobre $\beta_0$ es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, utilizando el principie de Yao, la complejidad en
el peor caso de un algoritmo aleatorizado en el modelo de
comparaciones es al menos $\lg(2n+1)\in\Omega(\lg n)$.
- El corolario interesante, es que el algoritmo
deterministico de búsqueda binaria es *oprima* a dentro de
la clase mas general de algoritmos aleatorizados.
2. Decidir si un elemento pertenece en un lista desordenada de tamaño k
* Si una sola instancia de la valor buscada ($r=1$)
* Cotas superiores
- k en el peor caso deterministico
- (k+1)/2 en el peor caso aleatorio
- con una dirección al azar
- con lg(k!) bits aleatorios
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición, y que
consideran todas las posiciones en el peor caso:
entonces cada algoritmo puede ser representado por una
permutación sobre $k$.
- Dado un algoritmo deterministico $a$, para cada
$i\in[1,k]$, hay una instancia sobre cual el performe
$i$ comparaciones. Entonces, su complejidad en promedio
en este instancia es $\sum_i i/k$, que es $k(k+1)/2k =
(k+1)/2$. Como eso es verdad para todos los algoritmos
deterministicos, es verdad para el mejor de ellos
también.
- Entonces, utilizando el principio de Yao, la complejidad
en el peor caso de un algoritmo aleatorizado en el
modelo de comparaciones es al menos $(k+1)/2$.
* Si r instancias de la valor buscada
* Cotas superiores
- k-r en el peor caso deterministico
- O(k/r) en (promedio y en) el peor caso aleatorio
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición.
- De verdad, no algoritmo tiene de considerar mas
posiciones que $k-r+1$, entonces hay menos algoritmos
que de permutaciones sobre $k$ elementos. Para
simplificar la prueba, podemos exigir que los algoritmos
especifican una permutación entera, pero no vamos a
contar las comparaciones después que un de las $r$
valores fue encontrada.
3. Decidir si un elemento pertenece en k listas ordenadas de tamaño n/k
* Cotas superiores
* Si una sola lista contiene la valor buscada
- k búsquedas en el peor caso deterministico, que da
k\lg(n/k) comparaciones
- k/2 búsquedas en (promedio y en) el peor caso
aleatorio, que da k\lg(n/k)/2 comparaciones
* Si r
* Formalización
Algoritmos clásicos Non clásicos
------------------------+---------------
Siempre hacen lo mismo aleatorizados
Nunca se equivocan Monte Carlo
Siempre terminan Las Vegas
* Clasificación de los algoritmos *de decisión* aleatorizados
1. ProbabilÃ-stico: Monte Carlo
- P(error) < épsilon
- Ejemplo:
- detección de cliquas
- Se puede considerar también variantes mas fines:
- two-sided error ( => clase de complejidad BPP)
- P(accept | negative) < \epsilon
- P(refuse | negative) > 1-\epsilon
- P(accept | positive) > 1-\epsilon
- P(refuse | positive) < epsilon
- One-sided error
- P(accept | negative) < epsilon
- P(refuse | negative) > 1 -\epsilon
- P(accept | positive) = 1
- P(refuse | positive) = 0
2. ProbabilÃ-stico: Las Vegas
- Tiempo es una variable aleatoria
- Ejemplos:
- determinar primalidad [Miller Robin]
- búsqueda en arreglo desordenado
- intersección de arreglos ordenados
- etc...
* Relación
- Si se puede verificar el resultado en tiempo razonable,
Monte Carlos iterado hasta correcto => Las Vegas
8 CANC Primalidad
~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-21 Thu 12:00-13:30>
REFERENCIAS:
- Primalidad: Capitulo 14.6 en "Randomized Algorithms", de Rajeev Motwani and Prabhakar Raghavan.
- [en.wikipedia.org/ ... lity_test#Complexity]
* Algoritmo "Random Walks" para SAT
1. eliga cualquieras valores $x_1,\ldots,x_n$
2. si todas las clausilas son satisfechas,
- accepta
3. sino
- eliga una clausula non satisfecha (deterministicamente
o no)
- eliga una de las variables de esta closula.
4. Repite es $r$ veces.
* PRIMES is in coNP
si $x\in coNP$, eliga non-deterministicamente una
decomposicion de $x$ y verificalo.
* PRIMES is in NP (hence in NP\cap coNP)
In 1975, Vaughan Pratt showed that there existed a
certificate for primality that was checkable in polynomial
time, and thus that PRIMES was in NP, and therefore in NP Á
coNP.
* PRIMES in coRP
The subsequent discovery of the Solovay-Strassen and
Miller-Rabin algorithms put PRIMES in coRP.
* PRIMES in ZPP = RP \cap coRP
In 1992, the Adleman-Huang algorithm reduced the complexity
to ZPP = RP Á coRP, which superseded Pratt's result.
* PRIMES in QP
The cyclotomy test of Adleman, Pomerance, and Rumely from
1983 put PRIMES in QP (quasi-polynomial time), which is not
known to be comparable with the classes mentioned above.
* PRIMES in P
Because of its tractability in practice, polynomial-time
algorithms assuming the Riemann hypothesis, and other
similar evidence, it was long suspected but not proven that
primality could be solved in polynomial time. The existence
of the AKS primality test finally settled this long-standing
question and placed PRIMES in P.
* PRIMES \in NC? PRIMES \in L?
PRIMES is not known to be P-complete, and it is not known
whether it lies in classes lying inside P such as NC or L.
9 CANC Clases de complejidad aleatorizada :BONUS:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-21 Thu 12:00-13:30>
9.1 RP
=======
- "A *precise* polynomial-time bounded nondeterministic Turing
Machine", aka "maquina de Turing non-deterministica acotadada
polinomialemente *precisa*", es una maquina tal que su
ejecucion sobre las entradas de tamaño n toman tiempo p(n)
*todas*.
- "A *polynomial Monte-Carlo Turing machine*", aka una
"*maquina de Turing de Monte-Carlo* polynomial" para el
idioma $L$, es una tal maquina tal que
- si $x\in L$, al menos la mitad de los $2^{p(|x|)}$ caminos
acceptan $x$
- si $x\not\in L$, *todas* los caminos rechazan $x$.
- La definicion corresponde exactamente a la definicion de
algoritmos de Monte-Carlo. La classe de idiomas reconocidos
por una *maquina de Turing de Monte-Carlo* polynomial es
$RP$.
- $P \subset BP \subset NP$:
- un algoritmo en $P$ accepta con todos sus caminos cuando
una palabra $x$ es en $L$, que es "al menos" la mitad.
- un algoritmo en $NP$ accepta con al menos un camino: un
algoritmo en $RP$ accepta con al menos la mitad de sus
caminos.
9.2 ZPP
========
- ZPP = RP \cap coRP
- Primes \in ZPP
9.3 PP
=======
- Maquina que, si $x\in L$, accepta en la mayoridad de sus
entradas.
- PP probablemente no en NP
- PP probablemente no en RP
9.4 BPP
========
- BPP = { L, \forall x,
- x\in L \implies 3/4 de los caminos acceptan x
- x\not\in L \implies 3/4 de los caminos rechazan x
- RP \subset BPP \subset PP
- BPP = coBPP
| Last Edit | 9 Nov 201009/11/10 at 11:302010-11-09 11:30:09 |
|---|---|
| Unique Views | 0 |
| Compartir |
