Totalmente NP-completo

En la teoría de la complejidad computacional, la fuerte NP-completitud 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 para el problema de empaquetado binario es una lista de objetos de tamaños específicos y un tamaño para los contenedores de los objetos (estos tamaños son parámetros numéricos).

Un problema se dice que es fuertemente NP-completo si sigue siéndolo incluso cuando todos sus parámetros numéricos están acotados por un polinomio en función de 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 polinómica a este; en la optimización combinatoria, en particular, la frase fuertemente NP-difícil se reserva para los problemas que no se sabe si tienen una reducción a otro problema fuertemente NP-completo.

Los parámetros numéricos de un problema normalmente se dan en la notación binaria, por lo que un problema de tamaño de entrada n pueden contener parámetros cuyo tamaño es exponencial en n. Si se redefine el problema para tener los parámetros dados en notación unaria, entonces los parámetros deben ser acotados por el tamaño de entrada. Por lo tanto, la fuerte NP-completitud o NP-dureza también se pueden definir como NP-completitud o NP-dureza de la versión unaria del problema.

Por ejemplo, el empaquetado binario es fuertemente NP-completo, mientras que el Problema de la Mochila 0-1 es sólo débilmente NP-completo. Así, la versión de empaquetado binario donde los tamaños de objeto y tamaño binario son números enteros asociados a un polinomio es NP-completa, mientras que la versión correspondiente del Problema de la Mochila puede ser resuelto en tiempo polinómico mediante el uso de la programación dinámica.

Mientras que los problemas débilmente NP-completos pueden admitir soluciones eficientes en la práctica siempre que sus entradas son de magnitud relativamente pequeña, los problemas fuertemente NP-completos no admiten soluciones eficientes en estos casos. Desde el punto de vista teórico, cualquier problema de optimización fuertemente NP-duro con una función objetivo polinómica asociada, no puede tener un esquema de aproximación de tiempo totalmente polinómico, a menos que P = NP.[2]​ 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-duro, pero no tiene un esquema de aproximación de tiempo totalmente polinómico, incluso cuando el óptimo es acotado polinómicamente.[3]​

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

A menos que P = NP, no hay un esquema de aproximación de tiempo totalmente polinómico para los problemas fuertemente NP-completos.[4]​

Véase también

Referencias

  1. ↑ Garey, M. R.; Johnson, D. S. (julio de 1978). 'Strong' NP-Completeness Results: Motivation, Examples, and Implications 25 (3). New York, NY: ACM. pp. 499-508. ISSN 0004-5411. MR 478747. doi:10.1145/322077.322090. 
  2. ↑ Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8. MR 1851303. 
  3. ↑ H. Kellerer and U. Pferschy and D. Pisinger (2004). Knapsack Problems. Springer. 
  4. ↑ Garey, M. R.; Johnson, D. S. (1979). Victor Klee, ed. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5. MR 519066.