Linear programming is $P$-complete.

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

  • $\begingroup$ 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. $\endgroup$ Commented Aug 22, 2017 at 10:22
  • $\begingroup$ Solving positive linear programming approximately is in NC. See for example, pdfs.semanticscholar.org/34f2/… $\endgroup$ Commented Aug 22, 2017 at 17:24
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Dec 28, 2017 at 6:17

1 Answer 1


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.

Alon and Meggido (1994): Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time

Blelloch et al. (2016): Parallelism in Randomized Incremental Algorithms


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.