<p>I am not sure, but you may be interested - if not, I beg your pardon - to the following <a href="http://onlinelibrary.wiley.com/doi/10.1002/net.10027/abstract" rel="nofollow">paper</a>, which is not related to a natural kind of optimization problem, but deals with a problem which can be reduced to a particular optimization problem, whose solution is in NC. </p>

<p>Igor Averbakh, Oded Berman, "Parallel NC-algorithms for multifacility location problems with mutual communication and their applications", Networks, Volume 40, Issue 1, pages 1–12, August 2002, Wiley</p>

<p>DOI: 10.1002/net.10027</p>

<p>Abstract</p>

<p>The generic problem studied is to locate p distinguishable facilities on a tree to satisfy upper-bound constraints on distances between pairs of facilities, given that each facility must be located within its own feasible region, which is defined as a subtree of the tree. We present a parallel location scheme (PLS) for solving the problem that can be implemented as an NC-algorithm. We also introduce parallel NC-algorithms based on the PLS for the minimax versions of the problem, including the distance-constrained p-center problem with mutual communication. Combining the PLS and the improved Megiddo's parametric technique, we develop strongly polynomial serial algorithms for the minimax problems; the algorithms have the best complexities currently available in the literature. Efficient parallel algorithms are given for obtaining optimal regions of the facilities.</p>

CC BY-SA 3.0
2012-06-03T18:17:10.573Z
2012-06-03T18:17:10.573Z
Massimo Cafaro
<p>Are you aware of the work on positive LPs/SDPs? There are a bunch of results in the area, mostly along the lines of "if the constraints of the LP/SDP are positive, then the problem can be solved in NC."</p>

<p>Some important references in this line of work are <a href="http://dl.acm.org/citation.cfm?id=167211">Luby-Nisan 93</a> and <a href="http://arxiv.org/abs/1104.2502">Jain-Yao 11</a>. Another excellent resource is <a href="http://www.youtube.com/watch?v=_Mf-KQmUJwA&amp;t=7m0s">this slide of Rahul Jain's talk</a> at the "Recent Progress in Quantum Algorithms" conference at IQC. The entire talk is available on youtube.</p>

CC BY-SA 3.0
2013-05-23T17:27:45.933Z
More precisely, Positive Linear Programming and Positive Semidefinite Programming are optimization problems that are not only exactly solvable in polynomial time (that is, they are in $\mathsf{PO}$), but also admit $\mathsf{NC}$ approximation schemes. They are not solvable exactly in $\mathsf{NC}$ (that is, in $\mathsf{NCO}$) unless $\mathsf{P} = \mathsf{NC}$.
argentpepper
CC BY-SA 3.0
2018-04-13T17:48:30.380Z
@argentpepper where is reference that positive SDP and LP is $P$-complete?
Turbo
CC BY-SA 3.0
2012-06-03T18:51:30.077Z
2012-06-03T18:51:30.077Z
Robin Kothari
<p>When learning optimization problems, we usually consider linear programming (or more generally: convex optimization) as the simplest example. It is solvable in polynomial time, and has relatively easy to understand algorithms. However, the decision version of LP is <span class="math-container">$\mathsf{P}$</span>-complete. This suggests that it is one of the hardest problems we can solve in polynomial time.</p>
<p>Under the assumption that <span class="math-container">$\mathsf{NC} \neq \mathsf{P}$</span>. <strong>What is the 'hardest' natural kind of optimization problems with decision problems in <span class="math-container">$\mathsf{NC}$</span>?</strong></p>
<p>If this is too vague, then we can restrict to restrictions. <strong>What is the minimal set of restrictions we need to place on linear programs (or more generally: convex programs) to allow the decision problem associated with the restricted programs to be solvable in <span class="math-container">$\mathsf{NC}$</span>?</strong></p>
<hr />
<h3>Motivation</h3>
<p>To a large extent, this is idle curiosity. However, it was brought about by Cosma Shalizi's &quot;<a href="http://crookedtimber.org/2012/05/30/in-soviet-union-optimization-problem-solves-you/" rel="noreferrer">In Soviet Union, Optimization Problem Solves You</a>&quot;. In particular, if LP is too difficult to solve to have a centralized economy (i.e. optimizing in <span class="math-container">$\mathsf{P}$</span> is asking too much), then any decentralized system must be doing some sort of parallel processing faster than poly-time (for me: <span class="math-container">$\mathsf{NC}$</span>).</p>

CC BY-SA 3.0
2017-12-20T19:48:59.717Z
Because NC is a hierarchy, you are unlikely to find a "hardest" problem in NC (more precisely: NC does not have complete problems unless the NC hierarchy collapses). Similarly, there is probably not a "universal" *minimal* set of restrictions on LP to put it into NC, although this seems harder to rule out, even conditioned on natural assumptions. (This is not to detract from the question - I like the question, and it obviously produced some interesting answers - just a remark.)
Joshua Grochow
<cc.complexity-theory><optimization><linear-programming>
Hardest optimization problems in NC
Artem Kaznatcheev
# Hardest optimization problems in NC

(Asked by: username_0 on 2012-06-02)

When learning optimization problems, we usually consider linear programming (or more generally: convex optimization) as the simplest example. It is solvable in polynomial time, and has relatively easy to understand algorithms. However, the decision version of LP is $\mathsf{P}$-complete. This suggests that it is one of the hardest problems we can solve in polynomial time.

Under the assumption that $\mathsf{NC} \neq \mathsf{P}$. **What is the 'hardest' natural kind of optimization problems with decision problems in $\mathsf{NC}$?**

If this is too vague, then we can restrict to restrictions. **What is the minimal set of restrictions we need to place on linear programs (or more generally: convex programs) to allow the decision problem associated with the restricted programs to be solvable in $\mathsf{NC}$?**

---

### Motivation

To a large extent, this is idle curiosity. However, it was brought about by Cosma Shalizi's "[In Soviet Union, Optimization Problem Solves You](http://crookedtimber.org/2012/05/30/in-soviet-union-optimization-problem-solves-you/)". In particular, if LP is too difficult to solve to have a centralized economy (i.e. optimizing in $\mathsf{P}$ is asking too much), then any decentralized system must be doing some sort of parallel processing faster than poly-time (for me: $\mathsf{NC}$).

**Tags:** cc.complexity-theory, optimization, linear-programming
> **Comments:**
> **username_1**: Because NC is a hierarchy, you are unlikely to find a "hardest" problem in NC (more precisely: NC does not have complete problems unless the NC hierarchy collapses). Similarly, there is probably not a "universal" *minimal* set of restrictions on LP to put it into NC, although this seems harder to rule out, even conditioned on natural assumptions. (This is not to detract from the question - I like the question, and it obviously produced some interesting answers - just a remark.)  

---

## 2 answers

### Answer by username_3 on 2012-06-03. Score: 10 | Accepted answer

Are you aware of the work on positive LPs/SDPs? There are a bunch of results in the area, mostly along the lines of "if the constraints of the LP/SDP are positive, then the problem can be solved in NC."

Some important references in this line of work are [Luby-Nisan 93](http://dl.acm.org/citation.cfm?id=167211) and [Jain-Yao 11](http://arxiv.org/abs/1104.2502). Another excellent resource is [this slide of Rahul Jain's talk](http://www.youtube.com/watch?v=_Mf-KQmUJwA&t=7m0s) at the "Recent Progress in Quantum Algorithms" conference at IQC. The entire talk is available on youtube.

> **Comments:**
> **username_4**: More precisely, Positive Linear Programming and Positive Semidefinite Programming are optimization problems that are not only exactly solvable in polynomial time (that is, they are in $\mathsf{PO}$), but also admit $\mathsf{NC}$ approximation schemes. They are not solvable exactly in $\mathsf{NC}$ (that is, in $\mathsf{NCO}$) unless $\mathsf{P} = \mathsf{NC}$.  
> **username_5**: @argentpepper where is reference that positive SDP and LP is $P$-complete?  

---

### Answer by username_2 on 2012-06-03. Score: 2

I am not sure, but you may be interested - if not, I beg your pardon - to the following [paper](http://onlinelibrary.wiley.com/doi/10.1002/net.10027/abstract), which is not related to a natural kind of optimization problem, but deals with a problem which can be reduced to a particular optimization problem, whose solution is in NC.

Igor Averbakh, Oded Berman, "Parallel NC-algorithms for multifacility location problems with mutual communication and their applications", Networks, Volume 40, Issue 1, pages 1–12, August 2002, Wiley

DOI: 10.1002/net.10027

Abstract

The generic problem studied is to locate p distinguishable facilities on a tree to satisfy upper-bound constraints on distances between pairs of facilities, given that each facility must be located within its own feasible region, which is defined as a subtree of the tree. We present a parallel location scheme (PLS) for solving the problem that can be implemented as an NC-algorithm. We also introduce parallel NC-algorithms based on the PLS for the minimax versions of the problem, including the distance-constrained p-center problem with mutual communication. Combining the PLS and the improved Megiddo's parametric technique, we develop strongly polynomial serial algorithms for the minimax problems; the algorithms have the best complexities currently available in the literature. Efficient parallel algorithms are given for obtaining optimal regions of the facilities.


---

