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

Abstract

The  purpose  of  this  article  is  to  give  a  formal  proof  of  the  NP-hard nature of a new variant of the classical maximum diversity problem,  this  new  variant  is  called  average  maximum  problem.  It  also  presents  a  brief  review  of  the  notions  and  concepts  related  to  the  NP-hardness,  and  conjecture  P  vs.NP,  in  order  to  understand  the  nature  of  the  optimization  problems,  and  why  some  of  them  can  beconsidered easy and others may call difficult.