Completitud NP fuerte

En complejidad computacional , la NP-completitud fuerte es una propiedad de los problemas computacionales que constituye un caso especial de la 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 el tamaño de los contenedores que deben contenerlos; 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 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-difícil si un problema fuertemente NP-completo tiene una reducción pseudopolinómica. Esta reducción pseudopolinómica es más restrictiva que la reducción polinómica habitual utilizada para las pruebas de NP-dureza. En particular, la reducción pseudopolinómica no puede generar un parámetro numérico que no esté acotado polinómicamente por el tamaño y el valor de los números en la entrada. ^{[ 2 ]}

Normalmente, los parámetros numéricos de un problema se expresan en notación posicional , por lo que un problema con entrada de tamaño n podría contener parámetros cuyo tamaño sea exponencial en n . Si redefinimos el problema para que los parámetros se expresen en notación unaria , entonces los parámetros deben estar acotados por el tamaño de la 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 problema de empaquetamiento de 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 del problema de empaquetamiento de contenedores donde los tamaños de los objetos y los contenedores son enteros acotados por un polinomio sigue siendo NP-completa, 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-difícil con una función objetivo acotada polinomialmente no puede tener un esquema de aproximación totalmente polinomial (o FPTAS ) a menos que P  =  NP. ^{[ 3 ] [ 4 ]} Sin embargo, lo contrario no se cumple: por ejemplo, si P no es igual a NP, el problema de la mochila con dos restricciones no es fuertemente NP-difícil, pero no tiene FPTAS incluso cuando la función objetivo óptima está acotada polinomialmente. ^{[ 5 ]}

Algunos problemas fuertemente NP-completos pueden ser fáciles de resolver en promedio , pero es más probable que en la práctica se encuentren casos difíciles.

Suponiendo que P ≠ NP, lo siguiente es cierto para problemas computacionales sobre enteros: ^{[ 6 ]}

• Si un problema es débilmente NP-difícil , entonces no tiene un algoritmo de tiempo débilmente polinomial (polinomial en el número de enteros y el número de bits en el entero más grande), pero puede tener un algoritmo de tiempo pseudopolinomial (polinomial en el número de enteros y la magnitud del entero más grande). Un ejemplo es el problema de partición . Tanto la NP-dificultad débil como el tiempo débilmente polinomial corresponden a la codificación de los enteros de entrada en 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 totalmente polinomial . Un ejemplo es el problema de la 3-partición . Tanto la fuerte NP-dificultad como el tiempo pseudopolinomial corresponden a la codificación de los enteros de entrada en codificación unaria .