Definición de problema.

DEFINICIÓN DE PROBLEMA.

Clasificación de 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.

Los problemas pueden clasificarse también atendiendo a su complejidad. Aquellos problemas para los que se conoce un algoritmo polinómico que los resuelve se denominan clase P. Los algoritmos que los resuelven son deterministas. Para otros problemas, sus mejores algoritmos conocidos son no deterministas. Esta clase de problemas se denomina clase NP. Por tanto, los problemas de la clase P son un subconjunto de los de la clase NP, pues sólo cuentan con una alternativa en cada paso.

Un cierto problema tiene solución algorítmica de complejidad lineal cuando el costo de la solución crece en forma proporcional con la cantidad de datos. Por ejemplo, en el método de búsqueda del máximo valor de un conjunto de números, la solución tarda un cierto tiempo promedio, que depende linealmente de la cantidad de elementos en la lista, porque le programa ocupa, por ejemplo, diez veces más tiempo en encontrar el número mayor en la lista de longitud 100 que en una de longitud 10. Un problema tiene solución algorítmica de complejidad polinominal (que es peor en términos generales que la lineal) cuando la ecuación que describe el costo de la solución es un polinomio (y no una simple variable o una constante), que suele crecer bastante más rápido que una ecuación lineal sencilla.

Un algoritmo es de complejidad exponencial cuando la ecuación que describe su comportamiento tiene exponentes variables, con lo que el costo de la ejecución del programa se puede disparar y hacerse inmanejable para ciertos tamaños en la longitud de los datos que maneja. Por último, los algoritmos inherentemente complejos exhiben tal velocidad de crecimiento en su costo de ejecución que resultan del todo impensables, aun para las más poderosas supercomputadoras.