# Cases of Linear programming known to be in $NC$?

Linear programming is $P$-complete.

However are there special situations where we know an $NC$ algorithm?

• Just an aside, are there possibly schemes in which there are BFS (Breadth First Search) type searches that make for an NC algorithm? Possibly reduce search space, in special scenarios.that allow for NC algorithms. Aug 22 '17 at 10:22
• Solving positive linear programming approximately is in NC. See for example, pdfs.semanticscholar.org/34f2/… Aug 22 '17 at 17:24
• Minimum spanning trees and shortest paths in weighted graphs are both expressible as linear programs, and have both long been known to be in NC. Dec 28 '17 at 6:17

Fixed dimensional linear programming (for any constant dimension $d$) is known to be in $\mathsf{NC}$; in fact, it can be done work-efficiently (in the same amount of work as the fastest sequential algorithm). The more recent paper by Blelloch et al. shows that the randomized-incremental approach for constant-dimensional LP can actually be parallelized efficiently.