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

Please provide a better solution

  • $\begingroup$ If I gave you what I claim is a solution (call me Oracle), how long would it take to check it? $\endgroup$ – gnasher729 Nov 4 '17 at 13:47
  • $\begingroup$ NP is equivalent to: "If the answer is YES, then you can show that it is YES in polynomial time, given the right hint". $\endgroup$ – gnasher729 Nov 4 '17 at 13:48
  • $\begingroup$ @gnasher729 I get your point, but I wouldn't ask my question if I wasn't stuck... can you help? $\endgroup$ – DeJaVo Nov 4 '17 at 13:50

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.

| cite | improve this answer | |
  • $\begingroup$ Is there a solution that uses a simplex method? $\endgroup$ – DeJaVo Nov 6 '17 at 20:18
  • $\begingroup$ I don't claim to be well-versed in linear programming, but I believe not, as the simplex method appears to have a worst case exponential time complexity. If you have to use a particular method, I suggest you ask about it in a new question. In the meantime, please keep this answer accepted if it answers your original question. $\endgroup$ – theyaoster Nov 6 '17 at 23:08
  • $\begingroup$ I agree with your observation $\endgroup$ – DeJaVo Nov 7 '17 at 6:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.