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
Respuestas:
Uno de cada tres 3SAT es NP-completo. En cuanto a la reducción, hereda la dureza APX de 3SAT. Puede formular uno de cada tres 3SAT como un programa entero binario con entradas binarias, por lo que su problema es APX-hard.
fuente