[Solved]: Complexity of solving LP with a non-linear growth in variables/constraints

Problem Detail: 

It has been shown that any Linear Program (LP) can be solved in a polynomial number of steps. An example of such algorithm is the ellipsoid method.

To solve a problem which has $k$ variables and can be encoded in $L$ input bits, this algorithm uses $O(k^4L)$ pseudo-arithmetic operations on numbers with $O(L)$ digits.

I have a problem that can be formulated as a LP, but yet has been proven to be NP-hard. The proof is rather hard and complicated for my understanding, so I just want to argue why it is, at least, not in P.

Consider the following excerpts from here.

I can see why the ellipsoid algorithm (or any LP solving algorithm) would take exponential amount of steps because the number of variables $k$ is exponential in $n$ ($k = m^n$).

Now the number of variables is not exponential anymore ($k = nm^2$) and I can not argue why solving the Dual LP would take an exponential number of steps. The only thing I could come up with is that $L$ (number of input bits) could be exponential in size because of the exponential number of constraints ($m^n$). But that is just a wild guess.

Additionally, if the statement about $L$ is true, than it is exponential in the primal LP as well, meaning that both $k$ and $L$ in $O(k^4L)$ are exponential. Does that mean that solving the dual LP is more efficient than solving the primal one, in which only $L$ is exponential but not $k$?

NB: The context is finding optimal correlated equilibria in succinct games.

Asked By : Auberon

Answered By : Yuval Filmus

The running time of algorithms for linear programming depends not only on the number of variables but also, unsurprisingly, on the number of constraints. This is hidden in the parameter $L$ which is the input size; clearly $L$ is at least the number of constraints. If there are exponentially many constraints, then any generic algorithms must take exponential time, since it has to consider all the constraints.

In some cases it is possible to solve linear programs with exponentially many constraints efficiently. This is the case if there is a separation oracle which, given a variable assignment, outputs a violated constraint (if any). If this can be done efficiently, then the ellipsoid algorithm can solve the linear program efficiently (at least approximately). If your problem is NP-hard then there is (probably) no efficient separation oracle for the dual LP. (Another possible reason for your problem to be hard is that rounding a solution could be hard or, perhaps, impossible.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51580

3.2K people like this

 Download Related Notes/Documents