Algoritmos factibles, problemas tratables y la complejidad computacional de una variante del problema de la diversidad máxima

Resumen

La intención de este artículo es dar una demostración formal del carácter NP-duro de una nueva variante del conocido problema de  optimización  combinatoria  de  la  diversidad  máxima,  esta  nueva  variante  es  denominada  problema  del  máximo  promedio.  Además  se presenta una breve revisión de las nociones y conceptos relacionados con la NP-dureza, y la conjetura P vs.NP, con el fin de comprender la naturaleza de los problemas de optimización, y por qué algunos de ellos se pueden considerar fáciles y otros pueden llamarse difíciles.