Dado un programa entero (binario) de la forma:
Tenga en cuenta que el tamaño de no está fijo en ninguna de las dimensiones.
Creo que Garey & Johnson ha demostrado que este problema es difícil de aproximar (fuertemente -Complete) . Si es así, ¿sigue siendo así cuando tienen entradas binarias es una función lineal ( )?
complexity-theory
np-complete
approximation
integer-programming
Jonas Anderson
fuente
fuente
2
"Difícil de aproximar" y "fuertemente NP-completo" son dos nociones diferentes.
Tsuyoshi Ito
2
La respuesta a tu pregunta es sí.