Complejidad computacional

La complejidad computacional considera globalmente todos los posibles algoritmos para resolver un problema dado.

Estamos interesados en la distinción que existe entre los problemas que pueden ser resueltos por un algoritmo en tiempo polinómico y los problemas para los cuales no conocemos ningún algoritmo polinómico, es decir, el mejor es no-polinómico.

La teoría de la NP-Completitud no proporciona un método para obtener algoritmos de tiempo polinómico, ni dice que que estos algoritmos no existan. Lo que muestra es que muchos de los problemas para los cuales no conocemos algoritmos polinómicos están computacionalmente relacionados.

De esta forma se presentarán definiciones que pretenden distinguir entre los problemas tratables (aquellos que no son tan duros) y los problemas intratables (duros o que consumen mucho tiempo). La mayoría de estos problemas ocurren como problemas de optimización combinatoria.

• Complejidad del mejor caso: Se entiende como el mejor de los casos aquel en que se realizan la menor cantidad de operaciones para resolver un problema.

• Complejidad del caso promedio: Se entiende como caso promedio aquel en que se realizan el número promedio de operaciones para dar solución a un problema.

• Complejidad del peor caso: Se entiende como el peor de los casos aquel en que se realizan la mayor cantidad de operaciones para dar solución a un problema dado.

¿Cómo se mide la complejidad?

La complejidad se mide por la notación asintótica O (log n) y esta a su vez determina el grado de complejidad del algoritmo, el cual se mide por tiempo de procesamiento, espacio de memoria, etc.

Clasificación de los problemas

Los problemas matemáticos se pueden dividir en primera instancia en dos grupos:

• Problemas indecidibles: aquellos que no se pueden resolver mediante un algoritmo.

• Problemas decidibles: aquellos que cuentan al menos con un algoritmo para su cómputo.

Sin embargo, que un problema sea decidible no implica que se pueda encontrar su solución, pues muchos problemas que disponen de algoritmos para su resolución son inabordables para un computador por el elevado número de operaciones que hay que realizar para resolverlos. Esto permite separar los problemas decidibles en dos: 

• Intratables: aquellos para los que no es factible obtener su solución.

•  Tratables: aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable.

Clases de los problemas

Clase P

Los problemas clase P son aquellos que pueden ser abordados durante la práctica y tratados mediante el uso de una máquina determinista en tiempo polinómico; es decir, son aquellos problemas en que su mejor solución es de complejidad superior a la polinómica.

Ejemplos: Todos los algoritmos a los que se les ha podido establecer su tiempo de ejecución.

Clase NP

Algunos de estos problemas intratables pueden caracterizarse por el curioso hecho de que puede aplicarse un algoritmo polinómico para comprobar si una posible solución es válida o no. Esta característica lleva a un método de resolución no determinista consistente en aplicar heurísticos para obtener soluciones hipotéticas que se van desestimando (o aceptando) a ritmo polinómico. Los problemas de esta clase se denominan NP (la N de no-deterministas y la P de polinómicos). Los problemas de la clase P son subconjunto de los de clase NP.

Ejemplos: Torres de Hanoi, Ordenación por el método Shell.

Clase NP Completos

Los problemas np completos son los peores que existe pues no cuentan con un algoritmo capaz de darles solución y, en caso de que llegasen a tenerlo, esto provocaría que los problemas np dejarán de existir. Esta clase de problemas se basan en la transformación polinomial, la cual consiste en trasformar un problema D1 a otro problema D2 mediante el uso de un algoritmo determinista de tiempo polinomial.

Ejemplos: Vendedor Viajero, Mochila.