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 tengan 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 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.