1.1 Concepto de complejidad de algoritmos.

1.1 Concepto de 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 conjunto de complejidad comparable que son (llamados clases de complejidad).

a) Clase de complejidad P:

El conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinomico de una maquina de turning, lo que corresponde al problema que puede ser resuelto a aun en el peor de sus casos.

b) Clases de complejidad NP:

Es el conjunto de los problemas de decisión que pueden ser resueltos por una maquina de turning no determinista en tiempo polinomico la propiedad de que su solución puede ser verificada.

El problema de satisfacción booleana el programa es poco satisfactoria.

c) Clase de complejidad NP-completo:

Es le subconjunto de los problemas NP que se destacan por su extrema complejidad en la cual algunos de ellos en la actualidad no han encintrado una solución satisfactoria.

La suma de subconjuntos dado un conjunto S de enteros ¿existe un subconjunto no vació cuyo electos sumen 0?dos grafos son isomorfos.

Diagrama de la relación entre las clases de complejidad

Problemas de decisión

Presenta à¿las clases p y NP son diferentas o no?