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$ – user3483902 Aug 22 '17 at 10:22
  • $\begingroup$ Solving positive linear programming approximately is in NC. See for example, pdfs.semanticscholar.org/34f2/… $\endgroup$ – Thatchaphol Aug 22 '17 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$ – David Eppstein 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.

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

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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