En la complejidad computacional , la NP-completitud fuerte es una propiedad de los problemas computacionales que es un caso especial de NP-completitud . Un problema computacional general puede tener parámetros numéricos. Por ejemplo, la entrada al problema de empaquetamiento 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 objetos y el tamaño de los contenedores 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 acotados 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 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 con un tamaño de entrada n puede contener parámetros cuyo tamaño sea exponencial en n . Si redefinimos el problema para que los parámetros se den en notación unaria , entonces los parámetros deben estar acotados por el tamaño de entrada. Por lo tanto, la NP-completitud fuerte o la NP-dureza también pueden definirse como la NP-completitud o la NP-dureza de esta versión unaria del problema.
Por ejemplo, el empaquetamiento de bins 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 del empaquetamiento de bins donde los tamaños del objeto y del bin son números enteros acotados por un polinomio sigue siendo NP-completo, mientras que la versión correspondiente del problema de la mochila se puede resolver en tiempo pseudo-polinomial mediante programación dinámica .
Desde una perspectiva teórica, cualquier problema de optimización fuertemente NP-hard 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 inverso falla: por ejemplo, si P no es igual a NP, la mochila con dos restricciones no es fuertemente NP-hard, 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.
Suponiendo que P ≠ NP, lo siguiente es cierto para problemas computacionales con números enteros: [5]