## UNIDAD III COMPLETITUD NP

## INTRODUCCIÓN

##

UNIDAD DE COMPETENCIA: Establece cotas de rendimiento de algoritmos de aproximación con base en herramientas teóricas y heurísticas de diseño de algoritmos.

> > > > La complejidad computacional considera globalmente todos los posibles algoritmos para resolver un problema dado. En la presente unidad haremos la distinción que existe entre los problemas que pueden ser resueltos por un algoritmo en tiempo polinómico y los problemas para los cuales no conocemos ningún algoritmo polinómico, es decir, el mejor es no-polinómico.

> > > > La teoría de la NP-Completitud no proporciona un método para obtener algoritmos de tiempo polinómico, ni dice que que estos algoritmos no existan. Lo que muestra es que muchos de los problemas para los cuales no conocemos algoritmos polinómicos están computacionalmente
> > > > relacionados.

###