La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

La clase PP, computación democrática, y la cota de Chernoff

Posted by Carlos en junio 12, 2007

Hace tiempo hablamos de las clases de complejidad P y NP a cuento de la computación cuántica, y aunque sin duda estas dos clases son las más conocidas (incluso fuera del ámbito de la informática teórica) no son ni muchísimo menos las únicas. Hay todo un universo de diferentes clases que habitan tanto en el interior de P o de NP, como en su exterior, englobando a estas dos en parte, o totalmente. Esto último es precisamente el caso de la clase que nos ocupa: PP (Probabilistic Polynomial-Time). Antes de definirla, recapitulemos brevemente el significado de P y NP. Estamos considerando problemas de decisión, para los que la respuesta es SÍ o NO. Si tenemos un algoritmo que en un número polinómico de pasos (esto es, un número p(n) -donde n es el tamaño del problema- tal que asintóticamente p(n) < anc, donde a y c son dos constantes) es capaz de solucionar correctamente el problema, entonces dicho problema está en la clase P. Por otra parte, consideremos un programa no-determinista que en ciertos momentos lanza monedas al aire y toma decisiones al azar. Si dado un problema, siempre que la respuesta es SÍ existe al menos una secuencia de decisiones tales que el algoritmo anterior responde SÍ en tiempo polinómico, y siempre que la respuesta es NO, todas las secuencias de decisiones resultan en un NO, entonces el problema está en la clase NP. Análogamente, si siempre que la respuesta es NO, existe al menos una secuencia de decisiones tales que el algoritmo responde NO en tiempo polinómico, y siempre que la respuesta es SÍ, todas las secuencias de decisiones resultan en un SÍ, entonces el problema está en la clase co-NP. Un ejemplo de problema en NP (y de hecho, NP-completo) es el de la satisfacibilidad (SAT): dada una fórmula lógica, ¿existe una asignación de valores de verdad a las variables que la componen, tal que la fórmula sea cierta? Si en lugar de SAT consideramos VALIDITY (dada una formula lógica, ¿es cierta para todas las asignaciones de valores de verdad a las variables que la componen?), tenemos un problema en co-NP (y de hecho, co-NP-completo). Se sabe que P está contenido en NP ∩ co-NP, y se cree que la inclusión es estricta, y que NP ≠ co-NP.

Una vez definido lo anterior, podemos describir la clase PP como la colección de todos los problemas para los que si la respuesta es SÍ un algoritmo no-determinista da la solución correcta en tiempo polinómico y con probabilidad superior al 50%. Si nos imaginamos que el algoritmo no-determinista toma sus decisiones aleatorias de manera uniforme, esto quiere decir que la decisión mayoritaria de todas las ramas de computación es la correcta (motivo por el cual se ha propuesto también la denominación Majority-P). Por ejemplo, consideremos el problema MAJSAT: dada una fórmula lógica, ¿tiene más asignaciones de verdad que la hacen cierta que asignaciones que la hacen falsa? Un algoritmo que genere una asignación de verdad uniformemente al azar y compruebe si hace cierta o falsa la fórmula responderá SÍ con probabilidad mayor al 50% si y sólo si hay más asignaciones que hagan la fórmula cierta, que asignaciones que la hagan falsa.

En relación con las clases mencionadas anteriormente es fácil ver que NP está contenida en PP. Para ello, considérese el problema SAT y un algoritmo que genere una asignación al azar, y si hace cierta la fórmula responda SÍ, y si la hace falsa responda SÍ o NO al 50%. Si la formula no es satisfacible, el SÍ y el NO ocurrirán con el 50% de probabilidad, pero si es satisfacible, la probabilidad será superior. ¿Cuánto superior? Si las asignaciones de calculan al azar, y hay N asignaciones que hacen cierta la fórmula, la probabilidad del SÍ será p=1/2+N2n, donde n es el número de variables lógicas. La utilidad de que la probabilidad sea estrictamente mayor al 50% radica en el hecho de que al repetir la ejecución del algoritmo múltiples veces, se amplifica la probabilidad de que salga SÍ (si la respuesta es efectivamente esa). Obviamente, cuanto menor sea el margen por el que se supera el 50%, serán necesarias más ejecuciones del algoritmo para aumentar la probabilidad de que la solución que ha salido más veces sea la correcta. La cota de Chernoff nos dice cuántas ejecuciones tenemos que hacer para que la probabilidad de que respuesta mayoritaria sea incorrecta esté por debajo de un cierto ε. Concretamente, dicho número k es

k \geq  -\left(\ln\sqrt{\varepsilon}\right)/{(p-1/2)^2}

En el ejemplo anterior de SAT, en el caso extremo en el que N=1, tendríamos que el número de ejecuciones para un cierto ε sería

k \geq  -\left(\ln\sqrt{\varepsilon}\right)2^{2n}

esto es, exponencial en el tamaño del problema. Esto hace que en el fondo un algoritmo de este tipo no sea práctico. Si el margen por el que se supera el 50% resulta sin embargo no ser exponencialmente pequeño en n, sino constante, tendríamos un algoritmo mucho más útil, y también una clase de complejidad diferente, de la que hablaremos otro día.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Anuncios

Sorry, the comment form is closed at this time.

 
A %d blogueros les gusta esto: