# Prove that Integer linear programming (ILP) is in NP

Help is needed, I've tried to solve it by myself but I could find any reasonable solution which is solid enough. this is what I've wrote:

Consider a 0-1 ILP, where each variable x1,x2...,xn can assume values 0 or 1. The number of constraints is m.

We can choose all possible 2n assignments of x1, x2...xn in non-deterministic manner.

Checking the feasibility of each assignment takes O(nm) time, and Computing the value of the objective function for each feasible assignment takes O(n) time Since a nondeterministic manner considers all assignments simultaneously. Thus, we have a non-deterministic polynomial time.

Due to Karp

• If I gave you what I claim is a solution (call me Oracle), how long would it take to check it? Nov 4, 2017 at 13:47
• NP is equivalent to: "If the answer is YES, then you can show that it is YES in polynomial time, given the right hint". Nov 4, 2017 at 13:48
• @gnasher729 I get your point, but I wouldn't ask my question if I wasn't stuck... can you help? Nov 4, 2017 at 13:50
• cs.stackexchange.com/a/69427/755
– D.W.
Sep 15, 2023 at 22:03

As stated in the comments, you can show that a problem is in NP by demonstrating the existence of a polynomial time verifier. In this case, such a verifier would be provided the values of $x_1, x_2, \dots, x_n$, and would need to answer the question "do these values of $x_1, \dots, x_n$ form a solution"? In this case, all you need to do is check that all $m$ contraints are satisfied.
• What if $x_1,\ldots,x_n$ are of exponential size w.r. to given $A,b,c$? Oct 26, 2021 at 20:55