Teoría de la Complejidad Computacional
Es la parte de la teoría de la computación que estudia los recursos necesarios durante el calculo para resolver un problema.
Estos recursos son el tiempo y el espacio.
Clases de Complejidad
Los problemas de desicion (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
b) Clase de complejidad NP
c) Clase de complejidad NP-Completo
Clase de complejidad P:
Es el conjunto de los problemas de desicion que pueden ser resueltos en tiempo polinomio por una maquina de Turing, lo que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos.
Clase de complejidad NP:
Es el conjunto de los problemas de desicion que pueden ser resueltos para una maquina de Turing no determinista en tiempo polinomio. Los problemas de esta clase tiene la propiedad de que su solución puede ser verificada.
Clase de complejidad NP-Completo
Es el subconjunto de los problemas de desicion de NP que se destacan por su extrema complejidad en la cueal algunos de ellos en la actualidad no han encontrado una respuesta satisfactoria.
-Diagrama de la relacion entre las clases de complejidad
No hay comentarios:
Publicar un comentario