¿Conoce algún problema (preferiblemente al menos algo bien conocido), donde, para un tamaño de problema práctico , un algoritmo exponencial se ejecuta mucho más rápido que una contraparte de tiempo polinomial más conocida.
Por ejemplo, suponga que un problema tiene un tamaño práctico * de y hay dos algoritmos conocidos: uno es 2 ny el otro es n c para alguna constante c . Claramente para cualquier c > 15 , se prefiere el algoritmo exponencial.
* Supongo que el tamaño práctico significaría algo que se encuentra comúnmente en el mundo real. Como la cantidad de trenes en una red.
Respuestas:
¿Qué tal el algoritmo simplex para programación lineal? En muchas ocasiones se usa en la práctica.
Editado para agregar: creo que es más un "algoritmo exponencial en el peor de los casos" que se ejecuta de manera eficiente en instancias prácticas / distribuciones en lugar de ejecutarse más rápido en instancias adversas de tamaño práctico .
fuente
fuente
Hay algunos ejemplos con detección / prueba de primalidad (no probabilística / exacta) . El algoritmo AKS fue el primer algoritmo para la prueba de primalidad que se mostró en P. No compite favorablemente en comparación con algunos algoritmos de tiempo exponencial para entradas "pequeñas". Los detalles son algo complicados porque mostrar esto generalmente requiere implementar los algoritmos, lo cual es un ejercicio desafiante y puede depender de aspectos específicos de la implementación.
Más información / detalles / referencias sobre esta pregunta cs.se:
fuente