En la teoría de la complejidad computacional , un problema de decisión es P-completo ( completo para la clase de complejidad P ) si está en P y cada problema en P puede reducirse a él mediante una reducción apropiada.
La noción de problemas de decisión P-completos es útil en el análisis de:
- qué problemas son difíciles de paralelizar de manera efectiva,
- cuyos problemas son difíciles de resolver en un espacio limitado.
El tipo específico de reducción utilizado varía y puede afectar el conjunto exacto de problemas. Si usamos reducciones NC , es decir, reducciones que pueden operar en tiempo polilogarítmico en una computadora paralela con un número polinomial de procesadores, entonces todos los problemas P -completos se encuentran fuera de NC y, por lo tanto, no pueden ser paralelizados de manera efectiva, bajo el supuesto no probado de que NC ≠ P . Si usamos la reducción del espacio logarítmico más débil , esto sigue siendo cierto, pero además aprendemos que todos los problemas P -completos se encuentran fuera de L bajo la suposición no probada más débil de que L ≠ P. En este último caso, el conjunto P -completo puede ser menor.
Motivación
La clase P , que generalmente se considera que consta de todos los problemas "manejables" para una computadora secuencial, contiene la clase NC , que consiste en aquellos problemas que pueden resolverse eficientemente en una computadora paralela. Esto se debe a que las computadoras paralelas se pueden simular en una máquina secuencial. No se sabe si NC = P . En otras palabras, no se sabe si existen problemas manejables que sean inherentemente secuenciales. Del mismo modo que en general se sospecha que P no es igual a NP , por lo que se sospecha ampliamente que la NC no es igual a P .
De manera similar, la clase L contiene todos los problemas que pueden ser resueltos por una computadora secuencial en el espacio logarítmico. Estas máquinas funcionan en tiempo polinomial porque pueden tener un número polinomial de configuraciones. Se sospecha que L ≠ P ; es decir, que algunos problemas que se pueden resolver en tiempo polinomial también requieren más que espacio logarítmico.
De manera similar al uso de problemas NP-completos para analizar la pregunta P = NP , los problemas P -completos, vistos como problemas "probablemente no paralelizables" o "probablemente inherentemente secuenciales", sirven de manera similar para estudiar el NC = P pregunta. Encontrar una manera eficiente de paralelizar la solución a algunos P problema -Complete mostraría que NC = P . También se puede considerar como los "problemas que requieren un espacio superlogarítmico"; una solución log-espacio a un P problema -Complete (utilizando la definición basada en reducciones log-espacio) implicaría L = P .
La lógica detrás de esto es análoga a la lógica de que una solución de tiempo polinomial para un problema NP- completo probaría P = NP : si tenemos una reducción NC de cualquier problema en P a un problema A, y una solución NC para A, entonces NC = P . Del mismo modo, si tenemos una reducción de log-espacio de cualquier problema en P a un problema A, y una solución log-espacio para A, entonces L = P .
P-problemas completos
El problema P -completo más básico es este: dada una máquina de Turing , una entrada para esa máquina y un número T (escrito en unario ), ¿esa máquina se detiene en esa entrada dentro de los primeros T pasos? Está claro que este problema es P -completo: si podemos paralelizar una simulación general de una computadora secuencial, entonces podremos paralelizar cualquier programa que se ejecute en esa computadora. Si este problema se encuentra en Carolina del Norte , entonces también lo es cualquier otro problema en P . Si el número de pasos está escrito en binario, el problema es EXPTIME-complete . Este problema ilustra un truco común en la teoría de P -completitud. No estamos realmente interesados en si un problema se puede resolver rápidamente en una máquina paralela. Solo nos interesa saber si una máquina paralela lo resuelve mucho más rápido que una máquina secuencial. Por lo tanto, tenemos que reformular el problema para que la versión secuencial está en P . Es por eso que este problema requería que T se escribiera en unario. Si un número T se escribe como un número binario (una cadena de n unos y ceros, donde n = log T ), entonces el algoritmo secuencial obvio puede tardar 2 n . Por otro lado, si T se escribe como un número unario (una cadena de n unos, donde n = T ), entonces solo toma el tiempo n . Al escribir T en unario en lugar de binario, hemos reducido el algoritmo secuencial obvio de tiempo exponencial a tiempo lineal. Eso hace que el problema secuencial en P . Entonces, estará en NC si y solo si es paralelizable.
Se ha demostrado que muchos otros problemas son P -completos y, por lo tanto, se cree ampliamente que son inherentemente secuenciales. Estos incluyen los siguientes problemas, ya sea en forma dada o en forma de problema de decisión:
- Problema de valor de circuito (CVP): dado un circuito , las entradas al circuito y una puerta en el circuito, calcule la salida de esa puerta
- Caso restringido de CVP: como CVP, excepto que cada puerta tiene dos entradas y dos salidas (F y no F), todas las demás capas son solo puertas Y, el resto son puertas O (o, de manera equivalente, todas las puertas son puertas NAND o todas puertas son puertas NOR), las entradas de una puerta provienen de la capa inmediatamente anterior
- Programación lineal : maximice una función lineal sujeta a restricciones de desigualdad lineal
- Orden lexicográficamente de primera búsqueda en profundidad: dado un gráfico con listas de adyacencia ordenadas fijas y nodos u y v , ¿se visita el vértice u antes que el vértice v en una búsqueda en profundidad inducida por el orden de las listas de adyacencia?
- Membresía de gramática libre de contexto - Dada una gramática libre de contexto y una cadena, ¿puede esa cadena ser generada por esa gramática?
- Satisfacción de Horn : dado un conjunto de cláusulas de Horn , ¿hay una asignación variable que las satisfaga? Esta es la versión de P del problema de satisfacibilidad booleano .
- Juego de la vida: dada una configuración inicial del Juego de la vida de Conway , una celda en particular y un tiempo T (en unario), ¿esa celda está viva después de los pasos T ?
- LZW (algoritmo) (1978 paradigma) Compresión de datos - da cuerdas s y t , se comprime s con un LZ78 método add t al diccionario? (Tenga en cuenta que para la compresión LZ77 como gzip , esto es mucho más fácil, ya que el problema se reduce a "Is t in s ?".)
- Inferencia de tipo para tipos parciales: dado un término sin tipo del cálculo lambda , determine si este término tiene un tipo parcial.
Para probar que un problema dado en P es P-completo, normalmente se intenta reducir un problema P -completo conocido al problema dado.
En 1999, Jin-Yi Cai y D. Sivakumar, basándose en el trabajo por Ogihara, mostró que si existe un lenguaje escasa que es P -Complete, entonces L = P . [1]
Los problemas P-completos pueden resolverse con diferentes complejidades de tiempo . Por ejemplo, el problema del valor del circuito se puede resolver en tiempo lineal mediante una clasificación topológica . Por supuesto, debido a que las reducciones a un problema P-completo pueden tener diferentes complejidades de tiempo, este hecho no implica que todos los problemas en P también puedan resolverse en tiempo lineal.
Problemas que no se sabe que sean P-completos
Algunos NP -Problemas no son conocidos por ser ya sea NP -Complete o en P . Se sospecha que estos problemas (por ejemplo , factorización , isomorfismo gráfico , juegos de paridad ) son difíciles. De manera similar, hay problemas en P que no se sabe que sean P -completo o NC , pero se cree que son difíciles de paralelizar. Los ejemplos incluyen las formas de problemas de decisión de encontrar el máximo común divisor de dos números y determinar qué respuesta devolvería el algoritmo euclidiano extendido cuando se le den dos números.
Notas
- ^ Cai, Jin-Yi; Sivakumar, D. (1999), "Conjuntos duros dispersos para P: resolución de una conjetura de Hartmanis" , Journal of Computer and System Sciences , 58 (2): 280-296, doi : 10.1006 / jcss.1998.1615
Referencias
- Greenlaw, Raymond, James Hoover y Walter Ruzzo. 1995. Limits To Parallel computation; Teoría P-Completitud . ISBN 0-19-508591-4 . - Desarrolla la teoría, luego cataloga 96 P-Problemas completos.
- Satoru Miyano, Shuji Shiraishi y Takayoshi Shoudai. Una lista de problemas P-Complete . Universidad de Kyushu, RIFIS-TR-CS-17. Diciembre de 1990.