NP-completo

Es fácil verificar si una respuesta es correcta, pero no se conoce mejor solución que explorar todos los 2n-1 subconjuntos posibles hasta encontrar uno que cumpla con la condición.Al principio parecía sorprendente que existieran problemas NP-completos, pero Cook demostró (teorema de Cook) que el problema de satisfacibilidad booleana es NP-completo.John Hopcroft llevó a todos los asistentes de la conferencia a consenso concluyendo que el estudio sobre si los problemas NP-completos son resolubles en tiempo polinómico debería ser pospuesto ya que nadie había conseguido probar formalmente sus hipótesis ni en un sentido ni en otro.Se trata de un problema difícil, pero no tanto como para estar en NP-completo.Nótese que este diagrama puede resultar engañoso al llevarnos a pensar que muestra una descripción de la relación matemática entre esos problemas, ya que existe una relación de reducción de tiempo polinómico entre dos problemas NP-completos cualesquiera; pero esto indica que demostrar estas reducciones de tiempo polinómicas ha sido más fácil.A menudo hay solo una pequeña diferencia entre un problema P y uno NP-completo.Actualmente, todos los algoritmos conocidos para problemas NP-completos utilizan tiempo exponencial con respecto al tamaño de la entrada.Esto contrasta con el uso del término reducción del que hablábamos al principio ya que este tiene la restricción de que el programa solamente puede llamar una vez al subalgoritmo y el valor retornado por este debe ser el valor de retorno del programa.Si los dos conceptos fuesen lo mismo, se seguiría que NO = Co-NP.Aunque la cuestión de si NP = co-NP es una pregunta abierta se considera muy poco probable porque también es muy poco probable que las dos definiciones de NP-completitud sean equivalentes.