P-completo

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 unaria), determinar si la máquina se para en los primeros T pasos. Queda claro que el problema es P-completo: Si se pudiera paralelizar una simulación general de una máquina secuencial, se tendría un método general para paralelizar cualquier programa que corre en esa máquina. Si este problema está en NC, todo problema de P también estaría en NC.

Este problema ilustra una técnica común utilizada en la teoría de la P-completitud. El interés no está realmente en saber si un problema se puede resolver rápidamente en una máquina paralela. Solo interesa saber si la máquina paralela lo puede resolver muchísimo más rápidamente que la máquina secuencial. Por tanto, el problema también se puede replantear para que la versión secuencial esté en P. Es por ello que en este problema se requiere que T esté escrito en unario. Si un número 'T está escrito como un número binario, el algoritmo secuencial más obvio puede tomar tiempo 2n. En cambio, si T está escrito como un número unario (una cadena de n unos, para n=T), solo toma tiempo n. Al escribir T en unario en lugar de binario, se reduce el algoritmo obviamente secuencial de tiempo exponencial a lineal, lo cual coloca el problema en la categoría P. Por tanto estará en NC si y solo si es paralelizable.

Se ha probado que muchos otros problemas son P-completos y por tanto es una idea generalmente aceptada que se trata de los problemas inherentemente secuenciales. Los siguientes problemas están en P-completo, sea tal y como están expresados, sea transformándolos a la forma de un problema de decisión:

  • Problema del valor de una compuerta en un circuito (Circuit Value Problem o CVP) - Dado un circuito booleano, sus entradas y una compuerta lógica en el circuito, calcular la salida de la puerta
  • CVP restringido- Igual al anterior, excepto que cada compuerta tiene dos entradas y dos salidas (F y su negación), el resto son compuertas NAND, la entrada de una compuerta viene de la capa inmediatamente anterior
  • Programación lineal - Maximizar una función lineal sujeta a restricciones expresadas como desigualdades
  • Búsqueda ordenada en profundidad - Dado un grafo con adyacencias fijas ordenadas, y dos nodos u y v, saber si el nodo u será visitado antes del nodo v en una búsqueda en profundidad
  • Pertenencia a una gramática libre de contexto - Dado una gramática libre de contexto y una palabra, saber si la palabra pertenece al lenguaje generado por la gramática
  • Juego de la vida - Dado una configuración general del juego de la vida de John Conway, una celda particular, y un entero T (en notación unaria), ¿estará la celda viva luego de T pasos?

Para demostrar que un problema es P-completo, típicamente se intenta reducir a un problema P-completo, utilizando un algoritmo paralelo eficiente.

Existen problemas que no han podido ser clasificados ni en P ni en NP-completo. Uno de ellos es el problema de factorización entera. Similarmente existen problemas que no se sabe si están en NC o en P-completo, pero que se piensa que son difíciles de paralelizar. Uno de ellos es el problema de decisión asociado al máximo común divisor de dos enteros en notación binaria.

Bibliografía

  • Greenlaw, Raymond, James Hoover, y Walter Ruzzo. 1995. Limits To Parallel computation; P-Completeness Theory. ISBN 0-19-508591-4 (desarrolla la teoría y cataloga muchos problemas en P-Completo)

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • completo — completo, ta adjetivo 1. (estar) Que tiene todas las partes que lo componen: La colección está completa. 2. (antepuesto / pospuesto) Que es total en todos sus aspectos: La fiesta ha sido un completo fracaso. La victoria ha sido completa. Sinónimo …   Diccionario Salamanca de la Lengua Española

  • completo — completo, ta adjetivo 1 entero*, íntegro, cabal, acabado, perfecto, lleno, cumplido, exacto. Íntegro equivale a entero; cabal reúne los matices de completo y entero. Cuando se trata de un trabajo u obra terminados, decimos que están completos,… …   Diccionario de sinónimos y antónimos

  • completo — completo, ta (Del lat. complētus, part. pas. de complēre, terminar, completar). 1. adj. Lleno, cabal. 2. Acabado, perfecto. por completo. loc. adv. completamente. ☛ V. dentición completo, flor completo, pensión completo …   Diccionario de la lengua española

  • completo — /kom plɛto/ [dal lat. completus, part. pass. di complēre compiere ; come s.m., nel sign. 2, dal fr. complet ]. ■ agg. 1. a. [che ha tutte le sue parti] ▶◀ compiuto, definitivo, finito, intero, perfetto, sano. ◀▶ imperfetto, incompiuto, incompleto …   Enciclopedia Italiana

  • Completo — puede referirse a: Algo íntegro, lleno, pleno, cumplido, acabado, perfecto. Espacio completo, en matemáticas. Completo, sándwich típico chileno, similar al hot dog. Véase también Completas, la última oración de la liturgia de las Horas… …   Wikipedia Español

  • completo — |é| adj. 1. A que não falta nada. 2. Que tem todas as qualidades exigidas. 3. Perfeito. 4. Que não admite mais, cheio. 5. Cabal; satisfeito. 6. Total; pleno. • s. m. 7. Estado do que se acha completo …   Dicionário da Língua Portuguesa

  • completo — (Del lat. completus, lleno.) ► adjetivo 1 Que tiene todos los elementos o partes que normalmente lo componen: ■ me han regalado una cubertería completa. SINÓNIMO entero íntegro ANTÓNIMO incompleto 2 Que está lleno: ■ la sala está completa …   Enciclopedia Universal

  • Completo (gastronomía) — Un completo italiano siendo degustado. El completo es un sándwich que corresponde a una variación chilena del perrito caliente. Consiste en un pan alargado con una salchicha en el medio, acompañada de distintos ingredientes. Es el sándwich más… …   Wikipedia Español

  • completo — com·plè·to agg., s.m. FO I. agg. I 1. di qcs., che ha tutti gli elementi che deve o può avere: un elenco, un resoconto completo; aspirapolvere completo di accessori; opera completa di un autore, edizione che comprende tutti i suoi scritti; avere… …   Dizionario italiano

  • Completo — Chilean Completo A completo italiano Origin Place of origin Chile Dish details …   Wikipedia

  • completo — adj 1 Que tiene todas sus partes o elementos, que contiene todo lo que debe contener: un aparato completo, cupo completo 2 Que está terminado o que ha alcanzado su carácter definitivo: una obra completa, un éxito completo, un completo acuerdo,… …   Español en México

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”