1.1 Concepto de la complejidad de algoritmos
*Teoría de la complejidad computacional
Es la parte de la teoría de la computación que estudia los recursos necesarios durante el cálculo para resolver un problema.
Estos recursos son: el tiempo y el espacio.
*Clases de Complejidad
Los problemas de decisión (aquellos donde la respuesta posible es si o no) se clasifican en conjuntos de complejidad comparable que son llamados clases de complejidad.
a) Clase de complejidad P. Es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinomico por una maquina de TURING lo que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos.
b) Clase de complejidad NP. Es el conjunto de los problemas de decisión que pueden ser resueltos por una maquina de TURING no determinista en tiempo polinomico. Los problemas de esta clase tienen la propiedad de que su solución es verificable. (problema del agente viajero)
c) Clase de Complejidad NP-completo. Subconjunto de los problemas NP destacado por su complejidad, en la cual algunos de ellos en la actualidad no han encontrado una solución satisfactoria (La suma de subconjutnos dado un conjunto S de enteros ¿existe un subconjunto novacio cuyos elementos sumen 0?|| ¿Dos grafos son isomorfos si se pueden transformar uno en el otro simplemente renombrando sus vértices?)
*Diagrama de relación entre las clases de complejidad
Problemas de decisión
Pregunta:¿Las clases P y NP son diferentes o no?
El Clay Mathematics Institute ofrece 1 millon de dlls a quien sea capaz de responder satisfactoriamente a esa pregunta.
