Tipos de problemas

Luis GuzmánDocente: Pilar Pardo

Análisis de algoritmo - Inacap

Complejidad computacional.• La complejidad computacional considera

todos los posibles algoritmos para resolver un problema dado.

• Existen problemas denominados PROBLEMA TRATABLES y PROBLEMAS INTRATABLES,

Clasificación.

• Problemas Indecibles (no se pueden resolver con un algoritmo).

• Problemas Decidibles (cuentan con al menos un algoritmo para su cómputo).

“No todo problema decidible tiene una solución.”

Característica que permite dividir los problemas decidibles en 2 tipos:

- Intratables (no poseen solución) No admite algoritmos razonables.

- Tratables (existe al menos un algoritmo capaz de resolverlo) Admite algoritmos razonables.

Clasificación de problemas por complejidad.

- Problemas de Clase P.

- Problemas de Clase NP.

- Problemas de Clase NP Completos.

La clase P.

• En esta categoría están los problemas que son tratables (suelen ser abordables en la práctica). Es decir, problemas que pueden ser resueltos por algoritmos de complejidad polinominal.

• Problemas que pueden ser resueltos en un tiempo polinómico.

La clase NP.

• A algunos de estos problemas se les puede aplicar un algoritmo polinómico para ver si una posible solución es válida o no.

• Problemas que no pueden ser resueltos en un tiempo polinómico.

La clase NP-Completos.

• La característica de estos problemas es que si existiera al menos una solución para uno de ellos podría aplicarse para todos los demás.