La viabilidad de la programación entera es NP-qué

Question

¿Cuál es la clase de complejidad del general problema de programación entera viabilidad ?

Las fuentes que he consultado son, en mi opinión, muy confusas. Algunas dicen NP-duro, otras dicen NP-completo. Algunas no distinguen entre el problema general y el caso binario. Algunos no distinguen entre el problema de optimización y el problema de viabilidad. Hasta donde yo sé, no parece haber ninguna correlación entre estos tres factores. Sólo he visto una prueba real de cualquier afirmación en el caso de viabilidad binaria, que es NP-completo.

Si he entendido bien, la completitud NP es una condición más fuerte que la dureza NP, ya que los problemas difíciles NP no necesitan ser NP (o problemas de decisión, pero puedo ignorar eso porque sólo me interesa la viabilidad). Así que no me sorprende que los dos se usen indistintamente para el caso binario.

Una referencia también sería muy apreciada.

Answer 1

Editar 29 de marzo de 2015: Como señala D.W. en un comentario, "P-duro" y "P-completo" de Sahni no significan lo que uno podría esperar del uso moderno. Sus términos son (aproximadamente) condicionales a P=NP. Su sección 1.1, definición 4, es un claro ejemplo: "Un problema $L$ es P-Duro si un algoritmo polinómico para $L$ implica P = NP". Como afirma D.W., esto elimina la discrepancia entre Sahni y G&J: el problema es NP-duro/completo, dependiendo de los signos de los coeficientes de las restricciones.

P-duro/completo, dependiendo de los signos de los coeficientes de las restricciones. Véase Sahni, S., "Computationally Related Problems" SIAM J. Computing vol. 3, pp. 262-279, 1974. También aquí (Sección 2.5, I1 y I2).

Referenciado como "A6 MP1" en Garey y Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness", 1979. Sin embargo, debe haber un error en esta referencia, G&J afirman NP-duro/completo, pero Sahni afirma P-duro (coeficientes de restricción positivos o negativos) y P-completo (restricciones positivas).