¿Es P igual a NP o es P distinto de NP? El dilema que acaba de leer admite la concesión o negación de cualquiera de sus dos premisas, y demostrar qué camino es el correcto está premiado con un millón de dólares por el Instituto Clay de Matemáticas desde el año 2000, siendo tal disyuntiva uno de los 7 Problemas del Milenio.

La Teoría de la complejidad computacional se dedica a clasificar problemas computacionales en función de su dificultad inherente, de forma que un problema se considera “fácil” y de la clase P si se conoce un algoritmo exacto capaz de resolverlo usando un tiempo y una memoria computacional razonables, si esto no sucede, el problema se considera “difícil” y se incluye en la clase NP. Así, la respuesta P=NP nos hace pensar en que “lo difícil será fácil de resolver”, mientras que la conjetura P≠NP implica que estamos destinados a resolver, por siempre y sin remedio, algunos problemas mediante algoritmos de aproximación.

Este libro trata de Metaheurísticas: una batería de algoritmos de aproximación para resolver problemas de optimización combinatoria sin garantizar soluciones óptimas. Renunciar a “lo mejor”, cosa inevitable ante problemas complejos de dimensión industrial, se compensa obteniendo “lo aproximado”, siendo el campo metaheurístico uno de los más fructíferos en las últimas décadas y, salvo que sea P=NP, es previsible que también lo sea en las futuras.

No hay notas del Autor