U1-1.1Concepto de Complejidad

Unidad 1-Analisis de algoritmos

1.1Concepto de complejidad

Las respuestas posibles son Si o No se clasifican en conjuntos de complejidad comparable:

P: Es el conjunto de los problemas de decision que pueden ser resueltos en tiempo polinomico calculado en una maquina de Turing determinista, los cuales pueden ser resueltod aun en el peor de los casos. Ejemplos.

a)Saber si un numero es primo
b)Saber si cierta frase pertenece a un conjunto dado

NP: Es el conjunto de los problemas de decision que pueden ser resueltos en tiempo polinomico en maquina de turing, todos los problemas de esta clase tienen la propiedad de poder ser verificados, ejemplo.

a)Problema del agente viajero
b)Problema de satisfactibilidad booleana

NP Completo: es el subconjunto de problemas de decision en NP que destacan por su extrema complejidad y graficamente se encuentran en la frontera externa de la clase NP, ejemplo.

a)Suma de subconjuntos
b)Isomorfosis de grafos