Is Integer Linear Programming a special case of Linear Programming

Question

As known, LP is solvable in polynomial time, and ILP seems to a special case of LP, why it is NP complete?

Answer 1

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.