P-completo

Carta Rara · N.º 64174

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…

Leer en Wikipedia