Linear Programming (LP)

Input

An integer $n \times d$ matrix $A$, an integer $n \times 1$ vector $b$, and an integer $1 \times d$ vector $c$.

Problem

Find a rational $d \times 1$ vector $x$ such that $Ax \leq b$ and $cx$ is maximized.

Status

$\P$-hard (Dobkin, Lipton, and Reiss [1], Dobkin and Reiss [2], Khachian [3], Valiant [4]).

Remarks

The original reduction in [1] is from HORN to LP. In [2], LP and LI are shown to be logarithmic space equivalent by reducing LP to LI using rational binary search (Papadimitriou [5], Reiss [6]) to find the value of the maximum and an $x$ that yields it. However, it is not clear how to perform this reduction in $\NC^1$. Since LP and LI are complete via $\NC^1$ reductions though, there must be an $\NC^1$ reduction between the two problems. Although we know that LP and LI are $\NC^1$ equivalent, the $\NC^1$ reduction between them is not an obvious one.

Serna shows it is $\P$-complete to approximate a solution approximation, which requires finding an $x’$ close to the optimal solution, and to approximate a value approximation, which requires finding an $x’$ such that $cx’$ is close to $cx$ [7]. Megiddo gives a reduction of LP to Serna’s approximate problem [8]. It is also $\P$-hard to approximate $cx$ to within any constant fraction, even given a feasible solution $x’$ [11]; reduction is from DMDP. See Lin-Kriz and Pan [9] for some results on two variable linear programming. Dahlhaus observes that for $d$ equal to 3 and values over the reals the problem is $\P$-complete, whereas for $d$ equal to 2, the problem is in $\NC$ [10].