As known, LP is solvable in polynomial time, and ILP seems to a special case of LP, why it is NP complete?
Asked
Active
Viewed 147 times
1 Answers
2
Because you have to make sure your solutions are integers. Relaxing your constraints gives you an easier problem, not strengthening them.
As an example, find a real solution to $x^2 + 7y^2 = 37$. Now find one where $x$ and $y$ are integers. It's much harder, and in some cases impossible: $x^2 + 7y^2 = 39$ has real solutions, but no integer ones.
Henry Swanson
- 12,972
-
Linear equations as examples would be cleaner. – Kyle Jones Apr 30 '13 at 19:56