The Parallel complexity of positive linear programming

In this paper we study the parallel complexity of Positive Linear Programming (PLP), i.e. the special case of Linear Programming in packing/covering form where the input constraint matrix and constraint vector consist entirely of positive entries. We show that the problem of exactly solving PLP is P-complete. Luby and Nisan gave an NC approximation algorithm for PLP, and their algorithm can be used to approximate the size of the largest matching in bipartite graphs, or to approximate the size of the set cover to within a factor $(1+epsilon) ln Delta$, where $Delta$ is the maximum degree in the set system. Trevisan used positive linear programming in combination with Luby and Nisan's algorithm to obtain an NC $(3/4-epsilon)$-approximate algorithm for Max SAT. An important implication of our result is that, by using the Linear Programming technique, we cannot exactly compute in NC the cardinality of Maximum Matching in bipartite graphs or finding a $(ln Delta)$-approximation for Minimum Set Cover, or a 3/4-approximation of an instance of Maximum SAT, unless P=NC