Un algoritmo que resuelve un problema en tiempo exponencial es de utilidad muy limitada. El tiempo de ejecución de este tipo de algoritmos crece exponencialmente con el tamaño de la entrada, de ahí que ocupe demasiado tiempo en resolver inclusive instancias pequeñas. Entonces, ¿por qué no buscar un algoritmo cuyo tiempo de ejecución no crezca tan rápido y que sea eficiente? Más adelante se verá que estos algoritmos eficientes son los llamados de tiempo polinomial, y se utilizan todo el tiempo. La clase de problemas que resuelven los algoritmos polinomiales se denomina tipo P.
Pero, ¿será posible que no exista un algoritmo eficiente para resolver cierto tipo de problemas? En efecto, los computólogos han logrado demostrar que existen problemas tan difíciles que no existe manera de resolverlos en tiempo polinomial mediante una computadora. Por cierto, también existe una clase muy importante de problemas, los llamados NP, para los cuales no se sabe si existen algoritmos polinomiales. Además, en el otro extremo, también existen problemas para los que no hay ningún algoritmo.
Estos últimos se tocarán posteriormente; en esta sección sólo se mencionarán problemas difíciles que sí se pueden resolver y para los cuales el tiempo requerido para resolverlos es exponencial.
Curiosidades
Flops es un acrónimo en inglés que significa operaciones de punto flotante por segundo (floating point operations per second). Es utilizado para medir el desempeño de las computadoras, especialmente en áreas científicas en las que se realiza una gran cantidad de cálculos de punto flotante. El punto flotante es un sistema para representar números reales en la computadora.
