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 ?
En otras palabras, es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO, ¿Es que entonces también se pueden obtener las respuestas rápidamente?
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.
Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP-completos, fue determinada por Richard E. Ladner
Solución
Aun no hay solución.