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(nk) 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...