0
$\begingroup$

I studied that Integer problems are properly NP-HARD problems. I know that NP-HARD include problems that arent solvable, like the halting problem. This mean that there are instances of Integer problems that arent solvable ?

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Mar 2 '18 at 11:06
  • 1
    $\begingroup$ What do you mean by "Integer problems"? $\endgroup$ – David Richerby Mar 2 '18 at 11:12
1
$\begingroup$

No, it doesn't mean that.

The set of NP-hard problems is upward-closed in the sense that there is no upper bound on the hardness of problems in it. You are correct to say that the class of NP-hard problems contains undecidable problems.

That does not imply, however, that every NP-hard problem has "unsolvable instances".

  1. There is no such thing as an "unsolvable instance" in integer programming. There always is an answer, true or false (considering the decision version). Every finite set of instances is trivially computable. Only infinite sets can be undecidable.
  2. We do know upper bounds on integer programming. For the decision version, we know that it's in NP; the optimization version is in NPO. Therefore, we know IP is decidable.
$\endgroup$

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.