Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was thinking about examples where a problem is NP-hard but was not NP-complete and ILP came to mind.

It is obviously NP-hard but is it NP-complete? I.e., is it in NP? Given a certificate (the alleged minimum), we certainly cannot check if it is the minimum in polynomial time. Therefore, I don't see how we can convert this into a decision problem.

So is ILP NP-hard but not NP-complete?

Also feel free to include examples (apart from the halting problem) of problems which are NP-hard but not NP-complete.

share|cite|improve this question
up vote 3 down vote accepted

It depends on exactly what you mean by ILP. The standard decision problem formulation of Integer Programming is "there exists an integer solution with objective less than $k$". This is NP complete (google is your friend). If you have some different decision problem, it may or may not be, you have to specify the problem before we can tell.

share|cite|improve this answer
I see. That decision problem is certainly in NP. But is there a polynomial-time algorithm which can use this decision problem to solve the optimization problem? For example, how do you handle unboundedness, and feasibility? – Jacob Jun 2 '13 at 18:11
Yes, I believe so. Essentially use divide and conquer on each variable. You can get bounds, etc, from LP. – deinst Jun 2 '13 at 18:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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