P-completo

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 todo problema en P puede reducirse a él mediante una reducción apropiada.

La noción de problemas de decisión P-completos es útil para analizar qué problemas son difíciles de paralelizar de manera efectiva y qué problemas son difíciles de resolver en un espacio limitado, especialmente cuando se consideran nociones de reducibilidad más estrictas que la reducibilidad en tiempo polinomial.

El tipo específico de reducción utilizado varía y puede afectar el conjunto exacto de problemas. En general, se utilizan reducciones más estrictas que las reducciones de tiempo polinomial, ya que todos los lenguajes en P (excepto el lenguaje vacío y el lenguaje de todas las cadenas) son P -completos bajo reducciones de tiempo polinomial. Si utilizamos 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 quedan fuera de NC y, por lo tanto, no pueden paralelizarse eficazmente, bajo el supuesto no demostrado de que NC  ≠ P. Si utilizamos la reducción de espacio logarítmico más fuerte , esto sigue siendo cierto, pero además aprendemos que todos los problemas P -completos quedan fuera de L bajo el supuesto no demostrado más débil de que L ≠ P. En este último caso, el conjunto P -completo puede ser más pequeño.   

La clase P , que generalmente se considera que comprende todos los problemas "tratables" para una computadora secuencial, contiene la clase NC , que comprende aquellos problemas que pueden resolverse eficientemente en una computadora paralela. Esto se debe a que las computadoras paralelas pueden simularse en una máquina secuencial. Se desconoce si NC  = P. En otras palabras, se desconoce si existen problemas tratables que sean inherentemente secuenciales. Así como se sospecha ampliamente que P no es igual a NP , también se sospecha ampliamente que NC no es igual a P. 

De forma similar, la clase L engloba todos los problemas que pueden resolverse mediante una computadora secuencial en espacio logarítmico. Estas máquinas se ejecutan en tiempo polinomial porque solo pueden tener un número polinomial de configuraciones diferentes. Se sospecha que L  ≠ P ; es decir, que algunos problemas que pueden resolverse en tiempo polinomial también requieren más que espacio logarítmico. 

De forma similar al uso de problemas NP-completos para analizar la cuestión P  = NP , los problemas P -completos, considerados como problemas "probablemente no paralelizable" o "probablemente inherentemente secuenciales", sirven de manera similar para estudiar la cuestión NC = P. Encontrar una forma eficiente de paralelizar la solución de algún problema P -completo demostraría que NC = P. También puede pensarse como los "problemas que requieren espacio superlogarítmico"; una solución en espacio logarítmico para un problema P -completo (utilizando la definición basada en reducciones en espacio logarítmico) implicaría L = P.       

La lógica detrás de esto es análoga a la lógica de que una solución en 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. De manera similar, si tenemos una reducción en espacio logarítmico de cualquier problema en P a un problema A , y una solución en espacio logarítmico para A , entonces L = P.     

Existen muchas reducciones de muchos a uno diferentes que se utilizan al definir la P -completitud, con intensidades variables. ^{[ 1 ] : Sección 3.3}

En el nivel más bajo está NC ¹ -reducción, luego L -reducción, luego NC ² -reducción, NC ³ -reducción, y así sucesivamente. Su unión es NC -reducción. Están ordenados desde${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {L}}\subseteq {\mathsf {NC}}^{2}\subseteq {\mathsf {NC}}^{3}\subseteq \dots \subseteq {\mathsf {NC}}}$.

Para la reducción NC ^k y la reducción NC , se impone la uniformidad, porque la intención de la teoría de la P- completitud es demostrar cotas superiores. La no uniformidad es útil para demostrar cotas inferiores, pero para las cotas superiores, la no uniformidad es insatisfactoria, ya que son demasiado potentes para este propósito. La condición de uniformidad estándar es la L- uniformidad, lo que significa que la familia de circuitos debe ser construible por una máquina de Turing, de tal manera que dado${\displaystyle 1^{n}}$como entrada, genera una descripción de la${\displaystyle n}$circuito -ésimo usando${\displaystyle O(\log n)}$cinta de trabajo. ^{[ 1 ]}

Dados dos idiomas${\displaystyle L,L'}$, definir${\displaystyle L\leq _{m}^{{\mathsf {NC}}^{k}}L'}$si y solo si existe una familia de circuitos booleanos NC ^k L -uniformes que en conjunto calculan una función${\displaystyle f:\{0,1\}^{*}\to \{0,1\}^{*}}$, de tal manera que${\displaystyle x\in L}$si y solo si${\displaystyle f(x)\in L'}$.

Definir${\displaystyle L\leq _{m}^{\mathsf {NC}}L'}$si y solo si${\displaystyle L\leq _{m}^{{\mathsf {NC}}^{k}}L'}$para algunos${\displaystyle k\geq 1}$.

Definir${\displaystyle L\leq _{m}^{\mathsf {L}}L'}$si y solo si existe una función${\displaystyle f:\{0,1\}^{*}\to \{0,1\}^{*}}$que es implícitamente computable en el espacio logarítmico , de tal manera que${\displaystyle x\in L}$si y solo si${\displaystyle f(x)\in L'}$.

El problema P -completo más básico bajo reducciones muchos a uno en espacio logarítmico es el siguiente: dada una máquina de Turing${\displaystyle M}$, una entrada para esa máquina x , y un número T (escrito en unario ),${\displaystyle \langle M,x,T\rangle }$¿Esa máquina se detiene en esa entrada dentro de los primeros T pasos? Para reducir un${\displaystyle L\in {\mathsf {P}}}$Para este problema, tomemos una máquina de Turing.${\displaystyle M_{L}}$decidir${\displaystyle L}$en un tiempo acotado por el polinomio p . Entonces, para cualquier ${\displaystyle x\in L}$, generar la codificación de${\displaystyle M_{L}}$, la codificación de x misma y una serie de pasos${\displaystyle T=p(|x|)}$La máquina M se detiene en x dentro de${\displaystyle p(|x|)}$pasos si y solo si x está en L.

Claramente, si podemos paralelizar una simulación general de una computadora secuencial (es decir, la simulación de máquinas de Turing), entonces podremos paralelizar cualquier programa que se ejecute en esa computadora. Si este problema está en NC , entonces también lo está cualquier otro problema en P. Si el número de pasos se escribe en binario, el problema es EXPTIME-completo . Este problema ilustra un truco común en la teoría de la P -completitud. Realmente no nos interesa si un problema se puede resolver rápidamente en una máquina paralela. Solo nos interesa 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. Por eso 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 tomar tiempo 2 ⁿ . Por otro lado, si T se escribe como un número unario (una cadena de n unos, donde n = T ), entonces solo requiere un tiempo n . Al escribir T en unario en lugar de binario, hemos reducido el algoritmo secuencial obvio de tiempo exponencial a tiempo lineal. Esto coloca 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 que son P -completos bajo al menos reducciones de espacio logarítmico, ya sea tal como se presentan o en forma de problema de decisión:

• Problema de valor de circuito (CVP): dado un circuito , las entradas del circuito y una puerta en el circuito, calcule la salida de esa puerta.
• Caso restringido de CVP: similar a CVP, excepto que cada puerta tiene dos entradas y dos salidas (F y Not F), cada dos capas son solo puertas AND, el resto son puertas OR (o, equivalentemente, todas las puertas son puertas NAND, o todas las puertas son puertas NOR), las entradas de una puerta provienen de la capa inmediatamente anterior.
• Programación lineal : maximizar una función lineal sujeta a restricciones de desigualdad lineal.
• Ordenación de búsqueda en profundidad lexicográficamente primero: dado un grafo 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? ^{[ 2 ]}
• Pertenencia a una gramática libre de contexto: dada una gramática libre de contexto y una cadena de caracteres, ¿puede esa cadena ser generada por esa gramática?
• Satisfacibilidad de Horn : dado un conjunto de cláusulas de Horn , ¿existe una asignación de variables que las satisfaga? Esta es la versión de P del problema de satisfacibilidad booleana .
• Juego de la vida: dada una configuración inicial del Juego de la Vida de Conway , una célula en particular y un tiempo T (en notación unaria), ¿esa célula sigue viva después de T pasos?
• LZW (algoritmo) (paradigma de 1978) compresión de datos: dadas las cadenas s y t , ¿al comprimir s con un método LZ78 se añadirá t al diccionario? (Tenga en cuenta que para la compresión LZ77 , como gzip , esto es mucho más sencillo, ya que el problema se reduce a "¿Está t en s ?").
• Inferencia de tipos para tipos parciales: dado un término sin tipo del cálculo lambda , determine si este término tiene un tipo parcial.

La mayoría de los lenguajes mencionados anteriormente son P -completos incluso bajo nociones de reducción más fuertes, como la uniforme.${\displaystyle AC^{0}}$reducciones de muchos a uno, reducciones DLOGTIME o proyecciones polilogarítmicas.

Para demostrar 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 de Ogihara, demostraron que si existe un lenguaje disperso que es P -completo, entonces L  = P. ^{[ 3} ] 

Los problemas P -completos pueden resolverse con diferentes complejidades temporales . Por ejemplo, el problema del valor del circuito puede resolverse en tiempo lineal mediante una ordenación topológica . Por supuesto, dado que las reducciones a un problema P -completo pueden tener diferentes complejidades temporales, esto no implica que todos los problemas en P también puedan resolverse en tiempo lineal.

• Greenlaw, Raymond, James Hoover y Walter Ruzzo. 1995. Límites de la computación paralela; Teoría de la P-completitud . ISBN 0-19-508591-4— Desarrolla la teoría y luego cataloga 96 problemas P-completos.
• Satoru Miyano, Shuji Shiraishi y Takayoshi Shoudai. Una lista de problemas P-completos . Universidad de Kyushu, RIFIS-TR-CS-17 . Diciembre de 1990.