Complejidad computacionalLa complejidad computacional considera globalmente todos los posibles algoritmos para resolver un problema dado.Estamos interesados en la distincin que existe entre los problemas que pueden ser resueltos por un algoritmo en tiempo polinmico y los problemas para los cuales no conocemos ningn algoritmo polinmico, es decir, el mejor es no-polinmico.La teora de la NP-Completitud no proporciona un mtodo para obtener algoritmos de tiempo polinmico, ni dice que que estos algoritmos no existan. Lo que muestra es que muchos de los problemas para los cuales no conocemos algoritmos polinmicos estn computacionalmente relacionados.De esta forma se presentarn definiciones que pretenden distinguir entre los problemas tratables (aquellos que no son tan duros) y los problemas intratables (duros o que consumen mucho tiempo). La mayora de estos problemas ocurren como problemas de optimizacin combinatoria. Complejidad del mejor caso:Se entiende como el mejor de los casos aquel en que se realizan la menor cantidad de operaciones para resolver un problema. Complejidad del caso promedio:Se entiende como caso promedio aquel en que se realizan el nmero promedio de operaciones para dar solucin a un problema. Complejidad del peor caso:Se entiende como el peor de los casos aquel en que se realizan la mayor cantidad de operaciones para dar solucin a un problema dado.Cmo se mide la complejidad?La complejidad se mide por la notacin asinttica O (log n) y esta a su vez determina el grado de complejidad del algoritmo, el cual se mide por tiempo de procesamiento, espacio de memoria, etc.Clasificacin de los problemasLos problemas matemticos se pueden dividir en primera instancia en dos grupos: Problemas indecidibles: aquellos que no se pueden resolver mediante un algoritmo. Problemas decidibles: aquellos que cuentan al menos con un algoritmo para su cmputo.Sin embargo, que un problema sea decidible no implica que se pueda encontrar su solucin, pues muchos problemas que disponen de algoritmos para su resolucin son inabordables para un computador por el elevado nmero de operaciones que hay que realizar para resolverlos. Esto permite separar los problemas decidibles en dos: Intratables: aquellos para los que no es factible obtener su solucin. Tratables: aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable.Clases de los problemasClase PLos problemas clase P son aquellos que pueden ser abordados durante la prctica y tratados mediante el uso de una mquina determinista en tiempo polinmico; es decir, son aquellos problemas en que su mejor solucin es de complejidad superior a la polinmica.Ejemplos: Todos los algoritmos a los que se les ha podido establecer su tiempo de ejecucin.Clase NPAlgunos de estos problemas intratables pueden caracterizarse por el curioso hecho de que puede aplicarse un algoritmo polinmico para comprobar si una posible solucin es vlida o no. Esta caracterstica lleva a un mtodo de resolucin no determinista consistente en aplicar heursticos para obtener soluciones hipotticas que se van desestimando (o aceptando) a ritmo polinmico. Los problemas de esta clase se denominan NP (la N de no-deterministas y la P de polinmicos). Los problemas de la clase P son subconjunto de los de clase NP.Ejemplos: Torres de Hanoi, Ordenacin por el mtodo Shell.Clase NP CompletosLos problemas np completos son los peores que existe pues no cuentan con un algoritmo capaz de darles solucin y, en caso de que llegasen a tenerlo, esto provocara que los problemas np dejarn de existir. Esta clase de problemas se basan en la transformacin polinomial, la cual consiste en trasformar un problema D1 a otro problema D2 mediante el uso de un algoritmo determinista de tiempo polinomial.Ejemplos: Vendedor Viajero, Mochila.