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 polinomial 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. Tales 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 a 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]
Dureza NP fuerte y débil frente a algoritmos de tiempo polinómico fuerte y débil
Suponiendo que P! = NP, lo siguiente es cierto para problemas de cálculo con números enteros: [3]
- Si un problema es débilmente NP-difícil , entonces no tiene un algoritmo de tiempo débilmente polinomial (polinomio en el número de números enteros y el número de bits en el número entero más grande), pero puede tener un algoritmo de tiempo pseudopolinomial (polinomio en el número de enteros y la magnitud del entero más grande). Un ejemplo es el problema de la partición . Tanto la dureza NP débil como el tiempo polinómico débil corresponden a la codificación de los agentes de entrada en la codificación binaria .
- Si un problema es fuertemente NP-difícil , entonces ni siquiera tiene un algoritmo de tiempo pseudopolinomial . Tampoco tiene un esquema de aproximación de tiempo completamente polinomial . Un ejemplo es el problema de las 3 particiones . Tanto la dureza NP fuerte como el tiempo pseudopolinomial corresponden a la codificación de los agentes de entrada en la codificación unaria .
Referencias
- ^ MR Garey y DS Johnson. Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . WH Freeman, Nueva York, 1979.
- ^ L. Hall. Complejidad computacional . La Universidad Johns Hopkins.
- ^ Demaine, Erik. "Límites inferiores algorítmicos: diversión con pruebas de dureza, Conferencia 2" .