2
$\begingroup$

Given an oracle that can solve in polynomial time:

$$a^Tx=b$$ $$x \geq 0$$

So it can solve the feasibility problem with one equality-constraint ($a$ is here a vector and $b$ is a constant, $x$ is required to be integer) and non negativity constraint for the solution. (This problem is also known as unbounded knapsack problem)

With this oracle how can this be solved in polynomial time: $$Ax=b$$ $$x \geq 0$$

where there are arbitrary many equality-constraints ($A$ is here a Matrix and $b$ an vector, $x$ is required to be integer) and non negativity constraint for the solution.

My thoughts:

Just finding a solution for every constraint is not enough. You need to somehow be able to find a solution which fulfills all constraints. But i don't see a way? But there has to be way, because both problems are NP-complete.

Improve this question
$\endgroup$
1
$\begingroup$

Hint: What do you know about the complexity class of the unbounded knapsack problem? Is it in P? Is it NP-hard?

Now what do you know about the complexity class of LP? Is it in NP?

Think a bit about your answers to those two questions and see if that helps you see one path forward. (There's a short proof of your desired result that doesn't require much detailed mathematics.)

Once you've figured that out: if I told you that I was giving you an oracle for some NP-complete problem, what other problems could you use it to solve (in polynomial time)? (Possible hint: Take a look at the definition of NP-complete and think about what the implications of that are...)

Once you've worked out that: you should now know there is a reduction. So look at the proofs of each of the steps of reasoning I walked you through. Review these proofs. Those proofs will construct a reduction for you. So, work out what reduction is implicit in the proofs. You should be able to take it from here!

Improve this answer
$\endgroup$
7
  • $\begingroup$ I already wrote that both problems are NP-complete. But i still don't see a way. $\endgroup$ – guest Feb 17 '15 at 18:28
  • $\begingroup$ @guest, OK, good, that's excellent progress! Now, if I told you that I was giving you an oracle for some NP-complete problem, what other problems could you use it to solve (in polynomial time)? (Possible hint: Take a look at the definition of NP-complete and think about what the implications of that are...) $\endgroup$ – D.W.♦ Feb 18 '15 at 6:42
  • $\begingroup$ yes i can solve all problems which are in np. But how can i find a reduction from unbounded knapsack to general integer programming? $\endgroup$ – guest Feb 18 '15 at 14:42
  • $\begingroup$ @guest, OK, so given your oracle, you can solve all problems in NP. Is integer programming in NP? $\endgroup$ – D.W.♦ Feb 18 '15 at 18:11
  • 1
    $\begingroup$ Then this all boils down to the first np-complness proof for 3SAT $\endgroup$ – guest Feb 18 '15 at 20:08

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.