patternMajor
Why is linear programming in P but integer programming NP-hard?
Viewed 0 times
whylinearprogrammingbuthardinteger
Problem
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?
Solution
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 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.
Context
StackExchange Computer Science Q#40366, answer score: 28
Revisions (0)
No revisions yet.