Fuerte NP-completitud - Strong NP-completeness
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. Se dice que un problema es fuertemente NP-difícil 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 la dureza NP fuerte también se puede definir como el NP-completo o la dureza NP 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 limitados 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. 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.
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:
- 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 .