NP-hard problems in combinatorial optimization can usually be expressed as 0-1
linear programs with natural linear programming (LP) relaxations. Solutions to
these relaxations are useful for computing exact optimal solutions (by
branch-and-bound methods using the LP relaxation to compute lower bounds),
approximate solutions (by rounding schemes), or exact optimal solutions for
tractable problem subclasses (those with zero integrality gap). Although the LP
relaxation can be solved in polynomial time, solving it for large-scale
instances can be inefficient or impossible.

We show that there are several NP-hard problems (constraint satisfaction,
multiway cut, set cover, maximum independent set, maximum satisfiability) whose
LP relaxations are as hard as solving the general LP problem. Precisely, the
general LP can be reduced in linear time to the LP relaxation of each of these
problems. This result poses a fundamental limitation for designing efficient
algorithms to solve the LP relaxations, because finding such an algorithm might
improve the complexity of best known algorithms for general LP.