Tiempo pseudopolinómico
En teoría de la complejidad computacional, un algoritmo numérico se ejecuta en tiempo pseudopolinómico o tiempo seudopolinó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 pseudopolinó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 pseudopolinó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 pseudopolinómico, a través de programación dinámica, es el Problema de la mochila.
Bibliografía
[editar]- Garey, M. R.; Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company.
| Control de autoridades |
|
|---|
Datos: Q155291