The INFORMS Computing Society has a collection of myths and counterexamples in math programming by Harvey Greenberg. Here’s one of the IP myths:

IP Myth 21. Determining if Ax=b has an integer solution is NP-complete for integral A, b.

My thanks to Heiko Vogel for pointing this out. The key to this myth is that there are no bounds on x. (If we restrict x to be nonnegative, we have the standard form of a linear integer program, which is NP-complete.) This is the problem of solving linear diophantine equations for which Brown provides simple, polynomial-time algorithms. Also, see Aardal, Hurkens, and Lenstra.

I’d like to add that this problem **might be** NP-complete. However, this would imply that P=NP, so it’s not very likely.

### Like this:

Like Loading...

*Related*