# Are integer linear *feasibility* problems NP-hard?

I know that Integer Linear Programming problems are NP-hard. But it seems like this answer is only applicable to Integer Linear optimization problems.

It seems like integer linear feasibility problems should be able to be solved in polynomial time.

I was thinking that this would look something like this:

1. Solve the linear feasibility problem normally, and get the solution space.
2. Then, see if there is an integer solution point in this solution space.

This seems like it should be a polynomial time algorithm.

Does anyone know what I am missing here? Or have any papers that could help?

(Why? See https://cs.stackexchange.com/a/29916/755, Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?, which reduces the SAT problem to feasibility of ILP. Or, alternatively, note that if you could test feasibility of ILP in polynomial time, then you could solve all ILPs in polynomial time too. In particular you could find the optimal value of the objective function $$\Phi$$ by using binary search: add the inequality $$\Phi \ge c$$ for some constant $$c$$ to your ILP, and then use binary search on $$c$$ to find the largest $$c$$ for which this system is feasible.)