Comment by ColinWright

Graph vertex 3-colouring (G3C) is NP and NP-Hard, therefore NP-Complete (NPC).

There is a result that say that if you can solve general ILP problems then you can solve general G3C.

Satisfiability is NP and NP-Hard, therefore NP-Complete (NPC). It is therefore equivalent (under some definition of "equivalent") to G3C.

There is a result that say that if you can solve general ILP problems then you can solve general G3C.

There is a known result that if you can solve arbitrary G3C problems then you can factor integers. While the problem of factoring integers (FAC) is not NPC, clearly factoring integers is very important in today's computing environment.

So if you can solve arbitrary ILP problems you can break several current encryption algorithms that are thought to be secure.

So we can deduce that ILP is a fairly tricky problem to solve.

The thing that fools a lot of people is that random instances of NPC problems tend to be easy. The core of difficult instances gets smaller (in relative terms) as the problems get bigger, so if, say, you pick a random graph, it's probably trivial to find a vertex 3-colouring, or show that none such exists.