Stupid question: In theory linear programming is in P and integer programming 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?
|
The short answer: because you can use Integers to simulate Booleans for SAT, but when you don't restrict yourself to this, then you can't actually simulate SAT. You'll get a feasible answer, but it no longer carries any meaning in terms of whatever SAT instance you were trying to simulate. The tough answer to this is that we don't know that they aren't in the same complexity class. Nobody has a proof that $P \neq NP$. If we understood the deeper reasons why the problems were so different, that would require that we understood why the complexity classes were different, which we don't. |
||||
|
The reason linear programming is "efficient" is that the solution space may be represented by a single convex polyhedron. If one is trying to find the "highest" vertex on that polyhedron (one may apply a linear transform to any linear programming problem to make "height" correspond to the quantity to be maximized), then from any vertex one may travel along edges to the highest point without ever having to go "downhill". What makes integer programming "hard" is that there isn't a continuous solution space, but there are instead many disjoint solution spaces, and no way to work incrementally toward the optimal solution. |
|||
|
The other answers are correct, but I find them a bit technical. Suppose you have swept (eliminated) a matrix and are looking for any solution and the matrix looks like this:
In lineair programming, you can now set the non-pivot columns (x5,x6) to 0, and set x4 to 0.5 and find a trivial solution. In integer programming, you cannot just set the non-pivot columns to 0. The solution is harder (NP-hard) to find. Note also that the solutions are in $Q$, so this is not directly related to finite/infinite precision. |
||||
|