En la complejidad computacional , la completitud NP fuerte es una propiedad de los problemas computacionales que es un caso especial de completitud NP . Un problema computacional general puede tener parámetros numéricos. Por ejemplo, la entrada al problema de embalaje de contenedores es una lista de objetos de tamaños específicos y un tamaño para los contenedores que deben contener los objetos; estos tamaños de objeto y tamaño de contenedor son parámetros numéricos.
Se dice que un problema es fuertemente NP-completo (NP-completo en el sentido fuerte), si permanece NP-completo incluso cuando todos sus parámetros numéricos están limitados por un polinomio en la longitud de la entrada. [1] Se dice que un problema es fuertemente NP-duro si un problema fuertemente NP-completo tiene una reducción polinomial; en la optimización combinatoria, en particular, la frase "fuertemente NP-duro" se reserva para problemas que no se sabe que tienen una reducción polinomial a otro problema fuertemente NP-completo.
Normalmente, los parámetros numéricos de un problema se dan en notación posicional , por lo que un problema de tamaño de entrada n puede contener parámetros cuyo tamaño es exponencial en n . Si redefinimos el problema para que los parámetros se den en notación unaria , entonces los parámetros deben estar delimitados por el tamaño de entrada. Por tanto, el NP-completo o dureza NP fuerte también puede definirse como el NP-completo o NP-dureza de esta versión unaria del problema.
Por ejemplo, el empaquetado en contenedores es fuertemente NP-completo mientras que el problema de la mochila 0-1 es solo débilmente NP-completo . Por lo tanto, la versión de empaquetado de contenedores donde el objeto y los tamaños de contenedor son números enteros delimitados por un polinomio permanece NP-completo, mientras que la versión correspondiente del problema de la mochila se puede resolver en tiempo pseudopolinomial mediante programación dinámica .
Desde una perspectiva teórica, cualquier problema de optimización fuertemente NP-duro con una función objetivo acotada polinomialmente no puede tener un esquema de aproximación de tiempo polinomial completo (o FPTAS ) a menos que P = NP. [2] [3] Sin embargo, lo contrario falla: por ejemplo, si P no es igual a NP, la mochila con dos restricciones no es fuertemente NP-dura, pero no tiene FPTAS incluso cuando el objetivo óptimo está acotado polinomialmente. [4]
Algunos problemas fuertemente NP-completos aún pueden ser fáciles de resolver en promedio , pero es más probable que se encuentren casos difíciles en la práctica.
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: [5]
- 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
- ^ Garey, MR ; Johnson, DS (julio de 1978). " Resultados NP-completitud ' fuerte': motivación, ejemplos e implicaciones". Revista de la Asociación de Maquinaria Informática . Nueva York, NY: ACM. 25 (3): 499–508. doi : 10.1145 / 322077.322090 . ISSN 0004-5411 . Señor 0478747 .
- ^ Vazirani, Vijay V. (2003). Algoritmos de aproximación . Berlín: Springer. págs. 294–295. ISBN 3-540-65367-8. Señor 1851303 .
- ^ Garey, M. R .; Johnson, D. S. (1979). Victor Klee (ed.). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . Una serie de libros sobre ciencias matemáticas. San Francisco, California: W. H. Freeman and Co. págs. X + 338 . ISBN 0-7167-1045-5. Señor 0519066 .
- ^ H. Kellerer y U. Pferschy y D. Pisinger (2004). Problemas con la mochila . Saltador.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Demaine, Erik. "Límites inferiores algorítmicos: diversión con pruebas de dureza, Conferencia 2" .