Complejida P y NP

La relación entre las clases de complejidad P y NP es una pregunta que aún no se ha podido responder por la teoría de la complejidad computacional. En esencia, la pregunta ¿es P = NP ? significa: sies posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO (donde "rápidamente" significa "en tiempo polinómico"), ¿es que entonces también se pueden "obtener" las respuestasrápidamente?
Los recursos comúnmente estudiados en complejidad computacional son:
– El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver unproblema.
– El espacio: mediante una aproximación a la cantidad de memoria utilizada para resolver el problema.
Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P, PCompleto,NP, NP-Completo, NP Duro...).Nosotros nos vamos a centrar en las clases P y NP.
Se lo considera el problema más importante en este campo--el Clay Mathematics Institute ha ofrecido un premio de unmillón de dólares estadounidenses para quién desarrolle la primera demostración correcta.


La clase P
P es conocido por contener muchos problemas naturales, incluyendo las versiones de decisión deprograma lineal, cálculo del máximo común divisor, y encontrar una correspondencia máxima.
Problemas notables en P
Algunos problemas naturales son completos para P, incluyendo la conectividad (o laaccesibilidad) en grafos no dirigidos.
Una generalización de P es NP, que es la clase de lenguajes decidibles en tiempo polinómico sobre una máquina de Turing no determinista. De forma trivial, tenemosque P es un subconjunto de NP. Aunque no está demostrado, la mayor parte de los expertos creen que esto es un subconjunto estricto.
Aquí, EXPTIME es la clase de problemas resolubles en tiempoexponencial. De todas las clases mostradas arriba, sólo se conocen dos contenciones estrictas:
P estrictamente está contenido en EXPTIME.
L estrictamente está contenida en PSPACE.

Los problemas más...