Why is linear programming in P but integer programming NP-hard?

Answered By : Benjamin Lindqvist

I can't comment since it requires 50 rep, but there are some misconceptions being spread about, especially Raphael's comment "In general, a continous domain means there is no brute force (and no clever heuristics to speed it up)."

This is absolutely false. The key point is indeed convexity. Barring some technical constraint qualifications, minimizing a convex function (or maximizing a concave function) over a convex set is essentially trivial, in the sense of polynomial time convergence.

Loosely speaking, you could say there's a correspondence between convexity of a problem in "mathematical" optimization and the viability of greedy algorithms in "computer science" optimization. This is in the sense that they both enable local search methods. You will never have to back-track in a greedy algorithm and you will never have to regret a direction of descent in a convex optimization problem. Local improvements on the objective function will ALWAYS lead you closer to the global optimum.

This is not so in the non-convex case. Here, there may be a global minimimum, but several local minima that a local descent algorithm will always be drawn to, in the same way greedy algorithms do when applied to NP-problems. Sometimes they find the true optimum, most of the time not.

Problem Detail: 

Linear programming (LP) is in P and integer programming (IP) is NP-hard. But since computers can only manipulate numbers with finite precision, in practice a computer is using integers for linear programming. Because of this, shouldn't LP and IP be in the same complexity class?

Asked By : Sasha the Noob

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40366