COMPLEJIDAD DE ALGORITMOS

Es la parte de la teoría de la computación que estudia los recursos requeridos durante el calculo para resolver un problema los cuales se dividen en: el tiempo y el espacio.

Los problemas de decisión se clasifican en conjuntos de complejidad llamadas clases de complejidad:

- Clase de complejidad P: Es el conjunto de los problemas de decisión que puedan ser resueltos en tiempo polinómico calculado a partir de la entrada por una maquina de turins determinista y que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos.

Ejemplo:

  1. Saber si un numero entero es primo.
  2. Saber si una frase pertenece a un conjunto de frases.

- Clase de complejidad NP:

Es el conjunto de los problemas de decisión que pueden ser resueltos por una maquina de turins no determinista en tiempo polinómico las cuales tienen la propiedad de que su solución puede ser verificada.

- Clase de complejidad NP-Completo:

Es el subconjunto de los problemas de decisión en NP que destacan por su extrema complejidad y que decimos se hayan en la frontera externa de la clase NP.

Politica de Privacidad