SOLVING LP RELAXATIONS OF SOME NP-HARD PROBLEMS IS AS HARD AS SOLVING ANY LINEAR PROGRAM

We show that the general linear programming (LP) problem reduces in nearly linear time to the LP relaxations of many classical NP-hard combinatorial problems, assuming sparse encoding of instances. We distinguish two types of such reductions. In the first type (shown for set cover/packing, facility location, maximum satisfiability, maximum independent set, and multiway cut), the input linear program is feasible and bounded iff the optimum value of the LP relaxation attains a threshold, and then optimal solutions to the input linear program correspond to optimal solutions to the LP relaxation. In the second type (shown for exact set cover, three-dimensional matching, and constraint satisfaction), feasible solutions to the input linear program correspond to feasible solutions to the LP relaxations. Thus, the reduction preserves objective values of all (not only optimal) solutions. In polyhedral terms, every polytope in standard form is a scaled coordinate projection of the optimal or feasible set of the LP relaxation. Besides nearly linear-time reductions, we show that the considered LP relaxations are P-complete under log-space reductions, and therefore also hard to parallelize. These results pose a limitation on designing algorithms to compute exact or even approximate solutions to the LP relaxations, as any lower bound on the complexity of solving the general LP problem is inherited by the LP relaxations.