En complejidad computacional , un problema NP-completo (o NP-difícil ) es débilmente NP-completo (o débilmente NP-difícil) si hay un algoritmo para el problema cuyo tiempo de ejecución es polinomio en la dimensión del problema y las magnitudes de los datos involucrados (siempre que se den como números enteros ), en lugar de los logaritmos en base dos de sus magnitudes. Dichos algoritmos son funciones técnicamente exponenciales de su tamaño de entrada y, por lo tanto, no se consideran polinomios . [1]
Por ejemplo, el problema de la mochila NP-dura puede resolverse mediante un algoritmo de programación dinámica que requiera un polinomio de varios pasos en el tamaño de la mochila y el número de elementos (asumiendo que todos los datos se escalan para ser números enteros); sin embargo, el tiempo de ejecución de este algoritmo es un 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 pseudopolinomio-tiempoalgoritmo ... mostrará 'comportamiento exponencial' solo cuando se enfrente a instancias que contengan números 'exponencialmente grandes', [que] podrían ser raros para la aplicación que nos interesa. Si es así, este tipo de algoritmo podría servir para nuestros propósitos casi tan bien como algoritmo de tiempo polinomial ". Otro ejemplo de un problema NP-completo débil 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 permanecen 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]