<p>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.</p>

<p>Alon and Meggido (1994): <a href="http://theory.stanford.edu/~megiddo/pdf/alon.pdf" rel="noreferrer">Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time</a></p>

<p>Blelloch et al. (2016): <a href="https://www.cs.cmu.edu/~guyb/papers/BGSS16.pdf" rel="noreferrer">Parallelism in Randomized Incremental Algorithms</a></p>

CC BY-SA 3.0
2017-12-28T05:30:10.000Z
2017-12-28T05:30:10.000Z
xal
<p>Linear programming is $P$-complete.</p>

<p>However are there special situations where we know an $NC$ algorithm?</p>

CC BY-SA 3.0
2017-08-22T10:22:37.607Z
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.
user3483902
CC BY-SA 3.0
2017-08-22T17:24:02.583Z
Solving positive linear programming approximately is in NC. See for example, https://pdfs.semanticscholar.org/34f2/d1bc00866837d026729a7de0922adbbe087f.pdf
Thatchaphol
CC BY-SA 3.0
2017-12-28T06:17:35.063Z
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.
David Eppstein
<cc.complexity-theory><ds.algorithms><complexity-classes><linear-programming><dc.parallel-comp>
Cases of Linear programming known to be in $NC$?
Turbo
# Cases of Linear programming known to be in $NC$?

(Asked by: username_0 on 2017-08-18)

Linear programming is $P$-complete.

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

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes, linear-programming, dc.parallel-comp

> **Comments:**
> **username_1**: 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.  
> **username_2**: Solving positive linear programming approximately is in NC. See for example, https://pdfs.semanticscholar.org/34f2/d1bc00866837d026729a7de0922adbbe087f.pdf  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2017-12-28. Score: 5

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](http://theory.stanford.edu/~megiddo/pdf/alon.pdf)

Blelloch et al. (2016): [Parallelism in Randomized Incremental Algorithms](https://www.cs.cmu.edu/~guyb/papers/BGSS16.pdf)


---

