Integer Linear Programming (ILP): NP-hard vs. NP-complete?

2.6k Views Asked by At

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.

1

There are 1 best solutions below

2
On BEST ANSWER

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.