INTRODUCCIÓN

Hemos estudiado una amplia variedad de problemas y algoritmos. Algunos de los algoritmos son directos, mientras que otros son complicados y sutiles, donde n es el tamaño de las entradas debidamente definido. Sin embargo, la importancia de la teoría de los problemas NP-completos reside en que identifica un amplio tipo de problemas difíciles, cuya cota inferior parece ser del orden de una función exponencial. En otras palabras, reúne una serie de problemas que en apariencia carecen de algoritmos polinómicos, con objeto de resolverlos. Son problemas cuya resolución incluso con los mejores algoritmos conocidos requeriría muchos años o siglos de tiempo de computadora con entradas moderadamente grandes.

Presentaremos definiciones encaminadas a distinguir entre los problemas dóciles (es decir, "no tan difíciles") y los renuentes (es decir, "difíciles" o muy tardados).

No se han descubierto algoritmos razonablemente rápidos para estos problemas, pero tampoco se ha podido demostrar que los problemas requieren mucho tiempo. Dado que muchos de estos problemas son problemas de optimización que se presentan con frecuencia en aplicaciones, la falta de algoritmos eficientes tiene importancia real.

P y NP

"P" es una clase de problemas que se pueden resolver en "tiempo polinómico". La descripción de "NP" es más complicada.

Problemas de decisión

Básicamente, un problema de decisión es una pregunta que tiene dos posibles respuestas, sí y no. La pregunta se refiere a alguna entrada. Por lo regular, el planteamiento de un problema de decisión tiene dos partes:

1. La parte de descripción de ejemplar define la información que cabe esperar en la entrada.
2. La parte de pregunta plantea la pregunta tipo "sí o no" en sí; la pregunta contiene variables definidas en la descripción de ejemplar.

La salida de un problema de decisión es s¡ o bien no según sea la respuesta correcta de la pregunta, aplicada a una entrada dada.