P-completo

En teoría de la complejidad computacional, la clase de complejidad P-completo es un conjunto de problemas de decisión de gran utilidad para identificar los problemas que pueden ser resueltos eficientemente en máquinas paralelas. Un problema de decisión está en P-completo si está en NP y todo problema de P puede ser reducido a él en tiempo polilogarítmico en una máquina paralela con un número polinómico de procesadores. En otras palabras, un problema A está en P-completo si para todo problema B en P, existen constantes c y k tales que B puede ser reducido en A en tiempo O((log n)^c) utilizando O(n^k) procesadores paralelos. En NC se da una definición de procesador paralelo.

Generalmente se admite que la clase P contiene todos los problemas "resolubles" por una máquina secuencial y contiene la clase NC, que consiste en aquellos problemas que se pueden resolver eficientemente en una máquina paralela. Esto se debe a que las máquinas paralelas pueden simularse con máquinas secuenciales. No se sabe si NC=P. En otras palabras, no se sabe si existen problemas resolubles que son inherentemente secuenciales. Como generalmente se acepta que P no es igual a NP, generalmente se acepta también que NC y P son distintos.

La clase NP-completo, que puede verse como la que contiene los problemas que probablemente no son resolubles eficientemente, fue introducida para analizar el problema P=NP, y la clase P-completo, que contiene los problemas "probablemente no paralelizables" o "probablemente inherentemente secuenciales" se utiliza igualmente para estudiar la pregunta NC=P. Si se encontrase una forma eficiente de paralelizar la solución de un problema P-completo se echaría por tierra la hipótesis de que NC y P son distintos.

El más básico problema P-completo es este: dada una máquina de Turing, una entrada para esa máquina y un entero T (escrito en notación unaria), determinar si la máquina se para en los primeros T pasos. Queda claro que el problema es P-completo: Si se pudiera paralelizar una simulación general de una máquina secuencial, se tendría un método general para paralelizar cualquier programa que corre en esa máquina. Si este problema está en NC, todo problema de P también estaría en NC.

Este problema ilustra una técnica común utilizada en la teoría de la P-completitud. El interés no está realmente en saber si un problema se puede resolver rápidamente en una máquina paralela. Solo interesa saber si la máquina paralela lo puede resolver muchísimo más rápidamente que la máquina secuencial. Por tanto, el problema también se puede replantear para que la versión secuencial esté en P. Es por ello que en este problema se requiere que T esté escrito en unario. Si un número 'T está escrito como un número binario, el algoritmo secuencial más obvio puede tomar tiempo 2ⁿ. En cambio, si T está escrito como un número unario (una cadena de n unos, para n=T), solo toma tiempo n. Al escribir T en unario en lugar de binario, se reduce el algoritmo obviamente secuencial de tiempo exponencial a lineal, lo cual coloca el problema en la categoría P. Por tanto estará en NC si y solo si es paralelizable.

Se ha probado que muchos otros problemas son P-completos y por tanto es una idea generalmente aceptada que se trata de los problemas inherentemente secuenciales. Los siguientes problemas están en P-completo, sea tal y como están expresados, sea transformándolos a la forma de un problema de decisión:

• Problema del valor de una compuerta en un circuito (Circuit Value Problem o CVP) - Dado un circuito booleano, sus entradas y una compuerta lógica en el circuito, calcular la salida de la puerta
• CVP restringido- Igual al anterior, excepto que cada compuerta tiene dos entradas y dos salidas (F y su negación), el resto son compuertas NAND, la entrada de una compuerta viene de la capa inmediatamente anterior
• Programación lineal - Maximizar una función lineal sujeta a restricciones expresadas como desigualdades
• Búsqueda ordenada en profundidad - Dado un grafo con adyacencias fijas ordenadas, y dos nodos u y v, saber si el nodo u será visitado antes del nodo v en una búsqueda en profundidad
• Pertenencia a una gramática libre de contexto - Dado una gramática libre de contexto y una palabra, saber si la palabra pertenece al lenguaje generado por la gramática
• Juego de la vida - Dado una configuración general del juego de la vida de John Conway, una celda particular, y un entero T (en notación unaria), ¿estará la celda viva luego de T pasos?

Para demostrar que un problema es P-completo, típicamente se intenta reducir a un problema P-completo, utilizando un algoritmo paralelo eficiente.

Existen problemas que no han podido ser clasificados ni en P ni en NP-completo. Uno de ellos es el problema de factorización entera. Similarmente existen problemas que no se sabe si están en NC o en P-completo, pero que se piensa que son difíciles de paralelizar. Uno de ellos es el problema de decisión asociado al máximo común divisor de dos enteros en notación binaria.

Bibliografía

• Greenlaw, Raymond, James Hoover, y Walter Ruzzo. 1995. Limits To Parallel computation; P-Completeness Theory. ISBN 0-19-508591-4 (desarrolla la teoría y cataloga muchos problemas en P-Completo)