1.1 Concepto de Complejidad de Algorítmos

TEORIA DE LA COMPLEJIDAD COMPUTACIONAL.- Es la parte de la teoría de la omputación que estudia los recursos necesarios durante el cálculo para resolver un problema.

=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 decision que pueden ser resultos en timepo polinomico por una maquina de turing, lo que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos.
Ejemplos:
*Camino Optimo de un cartero
*Saber si un numero entero es primo. Programa 1
*Decidir si una grace pertenece a un conjunto dado de fraces.

a)Clase de complejidad NP: Es el conjunto de los problemas de decision 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 puede ser cerificada
Ejemplos:
*El problema del Agente Viajero. Programa 2
*El problema de Satisfactibliidad Boolenana.
a)Clase de complejidad NP: Es el subconjunto de los problemas de decision NP que se destacan por su complejidad en la cual algunos de ellos en la actualidad no han encontrado una solucion satisfactoria.
Ejemplos:
*La suma de subconjuntos dado un "S" de enteros, Existe un conjunto no vacío cuyos elementos sumen 0?
*2 grafos son isomorfos si se puede transformar uno en el otro simplemente renombrando sus vértices?

=Diagrama de la Relación entre las clases de Complejidad=
Problemas de Decisión:

Pregunta: Las clases P y NP son diferentes o No?

El Clay Matematics Institute ofrece $1,000,000 de dlls a quien sea capaz de responder satisfactoriamente a esta pregunta.