En complejidad computacional , un problema NP-completo (o NP-duro ) es débilmente NP-completo (o débilmente NP-duro) si existe un algoritmo para el problema cuyo tiempo de ejecución es polinomial en la dimensión del problema y las magnitudes de los datos involucrados (siempre que estos se den como números enteros ), en lugar de los logaritmos en base dos de sus magnitudes. Dichos algoritmos son técnicamente funciones exponenciales de su tamaño de entrada y, por lo tanto, no se consideran polinomiales . [1]
Por ejemplo, el problema de la mochila NP-hard se puede resolver mediante un algoritmo de programación dinámica que requiere un número de pasos polinomial en el tamaño de la mochila y el número de elementos (suponiendo que todos los datos se escalan para ser enteros); sin embargo, el tiempo de ejecución de este algoritmo es tiempo exponencial ya que los tamaños de entrada de los objetos y la mochila son logarítmicos en sus magnitudes. Sin embargo, como observaron Garey y Johnson (1979), "Un algoritmo de tiempo pseudo-polinomial ... mostrará un 'comportamiento exponencial' solo cuando se enfrente a instancias que contengan números 'exponencialmente grandes', [lo que] podría ser raro para la aplicación en la que estamos interesados. Si es así, este tipo de algoritmo podría servir a nuestros propósitos casi tan bien como un algoritmo de tiempo polinomial". Otro ejemplo de un problema débilmente NP-completo es el problema de la suma de subconjuntos .
El término relacionado fuertemente NP-completo (o NP-completo unario) se refiere a aquellos problemas que siguen siendo NP-completos incluso si los datos están codificados en unario , es decir, si los datos son "pequeños" en relación con el tamaño de entrada general. [2]
Suponiendo que P ≠ NP, lo siguiente es cierto para problemas computacionales con números enteros: [3]