Sí, existen tales problemas, pero todas las instancias que conozco son de interés puramente teórico sin aplicaciones en la práctica.
El principal resultado teórico relacionado con esta pregunta es el teorema de aceleración de Blum.
Para ilustrar este teorema, he aquí una de sus consecuencias: hay una función [matemática] f [/ matemática] (un objeto matemático) con las siguientes propiedades:
- ¿Cuáles son algunos conceptos erróneos comunes sobre los algoritmos?
- ¿Abusaron los escritores de los límites de la ecuación 3.10 del CLRS?
- ¿Cómo analizar la complejidad de caso promedio de un algoritmo? ¿Hay alguna fuente para aprenderlo paso a paso de lo básico?
- ¿Por qué Google dice que 'Global University' es una de las mejores universidades?
- ¿Cuál es la solución / lógica para el patrón numérico dado?
- [math] f [/ math] es una función total: devuelve algún valor para cada entrada válida
- [math] f [/ math] es computable: hay algunos programas de computadora que computan [math] f [/ math]. Alimenta al programa con cualquier entrada válida y después de muchos pasos, el programa producirá la salida correcta.
- Ahora puede elegir cualquier programa de este tipo [matemáticas] P_1 [/ matemáticas]. Sin embargo, independientemente del programa que elija, siempre podré acelerarlo, es decir, podré encontrar otro programa [matemático] P_2 [/ matemático] que calcule la misma función pero lo haga más rápido. Por ejemplo, siempre puedo encontrar un programa de tal manera que su complejidad temporal sea asintóticamente como máximo igual al logaritmo de la complejidad temporal de su programa.
Por lo tanto, no hay un programa óptimo que calcule [math] f [/ math]. Para cualquier programa que lo haga, hay otro programa mucho más rápido.
Esto puede parecer una contradicción, pero no lo es. Todo el truco está en que todos esos programas son tan lentos que las mejoras realmente no importan. Para un ejemplo simple de lo que puede estar pasando, considere la siguiente secuencia de “complejidades del tiempo”: [matemáticas] 2 ^ n, \ quad 2 ^ n / n, \ quad 2 ^ n / n ^ 2, \ quad 2 ^ n / n ^ 3 [/ math], … Cada una de estas funciones crece mucho más lentamente que la anterior, pero nunca llegará a cero.
TL, DR: Sí, hay problemas que no tienen ningún algoritmo óptimo. Podemos construir algunos problemas muy, muy complicados con la propiedad de que para absolutamente cualquier algoritmo que resuelva el problema podemos encontrar otro algoritmo que sea asintóticamente más rápido.
