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 todos los problemas en P pueden reducirse a él mediante una reducción adecuada.
El tipo específico de reducción utilizado varía y puede afectar el conjunto exacto de problemas. Genéricamente, se utilizan reducciones más fuertes que las reducciones de tiempo polinómico, 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 polinómico. Si utilizamos reducciones NC , es decir, reducciones que pueden operar en tiempo polilogarítmico en una computadora paralela con un número polinómico de procesadores, entonces todos los problemas P -completos quedan fuera de NC y, por lo tanto, no pueden paralelizarse efectivamente, bajo el supuesto no probado de que NC ≠ PAG . Si utilizamos la reducción logarítmica más fuerte , esto sigue siendo cierto, pero además aprendemos que todos los problemas P -completos se encuentran fuera de L bajo el supuesto más débil no probado de que L ≠ P. En este último caso el conjunto P -completo puede ser menor.
La clase P , que normalmente se considera que consta de todos los problemas "tratables" para una computadora secuencial, contiene la clase NC , que consta de aquellos problemas que se pueden resolver 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 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 aP.
De manera similar, la clase L contiene todos los problemas que pueden resolverse mediante una computadora secuencial en un espacio logarítmico. Estas máquinas funcionan en tiempo polinómico porque pueden tener un número polinómico de configuraciones. Se sospecha que L ≠ P ; es decir, que algunos problemas que pueden resolverse en tiempo polinomial también requieren más que un 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 la pregunta NC = P. pregunta. Encontrar una manera eficiente de paralelizar la solución a algún problema P -completo mostraría que NC = P. También se puede considerar como los "problemas que requieren espacio superlogarítmico"; una solución en espacio logarítmico para un problema P completo ( usando 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 polinómico a un problema NP completo demostraría que 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 el espacio logarítmico de cualquier problema en P a un problema A, y una solución en el espacio logarítmico para A, entoncesL = P.