L. Trevisan and F. Xhafa.
The Parallel Complexity of Positive Linear Programming.
Submitted, January 1997.
Abstract
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.