-1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\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, 2017 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, 2017 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, 2017 at 13:50
  • $\begingroup$ cs.stackexchange.com/a/69427/755 $\endgroup$
    – D.W. ♦
    Sep 15 at 22:03

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Is there a solution that uses a simplex method? $\endgroup$
    – DeJaVo
    Nov 6, 2017 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, 2017 at 23:08
  • $\begingroup$ I agree with your observation $\endgroup$
    – DeJaVo
    Nov 7, 2017 at 6:36
  • $\begingroup$ What if $x_1,\ldots,x_n$ are of exponential size w.r. to given $A,b,c$? $\endgroup$
    – Michal Dvořák
    Oct 26, 2021 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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