next up previous contents
Next: Computación en paralelo Up: Sobre la Complejidad Previous: #P-Completitud

Algoritmos probabilísticos

El uso de números aleatorios para simular o aproximar procesos no aleatorios es muy natural en la práctica de la computación. Sin embargo, la idea de que las entradas aleatorias pueden servir para resolver problemas combinatorios determinísticos ha penetrado más lentamente en la comuninidad de las Ciencias de la Computación. Aquí, centraremos la atención en los algoritmos probabilísticos de tiempo polinomial que "resuelven" (en un sentido razonable) un problema para el que no se conoce ningún algoritmo deterministico en tiempo polinomial.

El primer ejemplo de estos algoritmos es el de Berlekamp (1970), para factorizar un polinomio f sobre el cuerpo de p elementos. Este algoritmo corre en tiempo polinomial sobre el grado de f y , y con probabilidad de al menos un medio de encontrar una factorización correcta. Dado que el algoritmo se puede repetir cualquier número de veces, y la probabilidad de fallo es siempre independiente, en la práctica el algoritmo siempre factoriza f en tiempo polinomial.

Otro ejemplo es el algoritmo para el reconocimiento de números primos de Slovay y Strassen (1977). Este algoritmo corre en tiempo polinomial sobre la longitud de la entrada m, y la salida es o bien "primo" o bien "compuesto". Si m es realmente primo, entonces la salida es primo, pero si m es compuesto, la salida puede ser primo con probabilidad a lo más un medio. El algoritmo puede ser repetido cualquier número de veces con resultados independientes. Así, si la respueta alguna vez es compuesto, sabemos que es compuesto, mientras que si la respuesta es siempre primo, despues de por ejemplo 100 veces, entonces podemos decir sin apenas riesgo de equivocarnos que es primo, dado que fijado un compuesto cualquiera m, la probabilidad de que se diera ese resultado es menor que . Rabin (1976) encontró un algoritmo similar pero más rapido. ¡Identificó como primo al número en pocos minutos!

Una aplicación interesante del reconocedor probabilístico de primos en el sentido de Solovay y Strassen se conoce como R (a veces RP) . Un conjunto estará en R si y solo si tiene un algoritmo reconocedor probabilístico que siempre para en tiempo polinomial y nunca comete un error para entradas que no estén en R, y tal que para cada entrada que esté en R la probabilidad de acertar sea de al menos . Así el conjunto de números compuestos está en R, y en general . Hay ejemplos de conjuntos interesantes que están en R, pero que no se ha podido demostrar que estén en P. Por ejemplo, Schwartz (1980) demostró que el conjunto de matrices no singulares cuyos elementos son polinomios en muchas variables esta en R.

La igualdad R=P es un interesante problema abierto. Si la respuesta fuese positiva, nos diría que el uso que los algoritmos probabilísticos no aportan nada nuevo en la computación. Una cuestión relacionada con esto es si un algoritmo probabilístico es, desde el punto de vista práctico, tan bueno como un algoritmo determinístico.

Finalizamos esta sección con un interesante teorema de Adleman (1978) sobre la clase R. Es fácil ver que si un conjunto está en P, entonces para cada n hay un circuito booleano de tamaño acotado por un polinomio fijo sobre n que determina si una entrada arbitraria de tamaño n está o no en el conjunto. Lo que Adleman provó es que lo mismo ocurre para la clase R.



next up previous contents
Next: Computación en paralelo Up: Sobre la Complejidad Previous: #P-Completitud




Thu Jan 11 11:00:25 WET 1996