Tiempo pseudopolinómico
En teoría de la complejidad computacional, un algoritmo numérico se ejecuta en tiempo pseudo-polinómico si su tiempo de ejecución es polinómico en el valor numérico de la entrada, pudiendo ser este valor exponencial en el largo de la entrada, es decir, en el número de dígitos que la conforman.
Los problemas NP-completos con algoritmos que se ejecutan en tiempo pseudo-polinómico se denominan NP-completos débiles. Un problema NP-completo se denomina NP-completo fuerte si se puede demostrar que no puede ser resuelto por algoritmos pseudo-polinómicos, salvo que se cumpla que P=NP. Las clases NP-hard débil y fuerte se definen de forma análoga.
Un famoso problema que puede ser resuelto en tiempo pseudo-polinómico, a través de programación dinámica, es el Problema de la mochila.
Bibliografía
- Garey, M. R.; Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company.