<p>It is not even known whether <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:N#nc" rel="nofollow noreferrer">NC</a> = P, but P-complete problems seem to be inherently hard to parallelize.  These include Linear Programming and Horn-SAT.  (In contrast, problems in NC seem reasonably easy to parallelize.)</p>

<p>See question <a href="https://cstheory.stackexchange.com/questions/1317/problems-between-nc-and-p-how-many-have-been-resolved-from-this-list">Problems between NC and P: How many have been resolved from this list?</a> for reference material (including links to a classic textbook that is now available for free download), and further discussion about problems that are in P but not known to be parallelizable.</p>

<p>See question <a href="https://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem">Generalized Ladner&#39;s Theorem</a> for the structure of the complexity classes between NC and P.  Briefly, if they differ then there are infinitely many complexity classes strictly between NC and P.</p>

<p>See question <a href="https://cstheory.stackexchange.com/questions/1643/nc-p-consequences">NC = P consequences?</a> for a nice demonstration by Ryan Williams that it is possible to amplify collapses in the hierarchy of complexity classes within P into perhaps more unlikely collapses like <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:P#pspace" rel="nofollow noreferrer">PSPACE</a> = <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:E#exp" rel="nofollow noreferrer">EXP</a>.</p>

<p>It is worth pointing out that one consequence of Horn-SAT being P-complete, and the links above, is that it does not seem possible to parallelize general SQL queries in databases, unless we can also rewrite any large-scale computation to use only a reasonable amount of storage.  This is a puzzling discrepancy -- I think it is quite uncontroversial to state <em>there are limits on compression</em>, but I often see articles which seem built on the assumption that it is possible to parallelize <em>any</em> database query.</p>

CC BY-SA 2.5
2011-03-23T00:10:36.633Z
Certainly you may not be able to parallelize any given portion of a database query, or at least in any straightforward manner. However, a database query (excluding subqueries to keep things simple) can be reduced to a full table scan over some joined table, and that joined table itself can always be scanned in parallel. This is why, when you increase parallelism settings in Oracle, it is more inclined to use full table scans rather than indexes.
sclv
CC BY-SA 2.5
2011-03-23T11:06:16.920Z
@sclv: This is true, but in general the intermediate joins can be exponential in the input size?  So one can parallelize via joins, but at the cost of having to scan an exponential number of tuples.
András Salamon
CC BY-SA 2.5
2011-03-23T11:37:05.187Z
What do you consider the input size here? Also, if you have an m*n*o cross-join, there's always the possibility that you could return precisely that many tuples -- i.e. there's no possible better bound on the worst-case. And this is more practical than theoretical, but in general you're worried not about parallelizing performance of a predicate over a row anyway, but about IO throughput, since that's where the bound will tend to be.
sclv
CC BY-SA 2.5
2010-10-08T03:13:17.630Z
2011-03-21T18:15:06.600Z
2017-04-13T12:32:28.077Z
András Salamon
<p>Well, if there were known cases, then we'd be able to separate P and NC. But there are many problems known to be <a href="http://en.wikipedia.org/wiki/P-complete">P-complete</a> (i.e under logspace reductions), and they present the same kind of barriers to showing P = NC as NP-complete problems do for P = NP. Among them include linear programming and <strike>matching (and</strike> max flows in general). </p>

<p>Ketan Mulmuley <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.6538">proved a result</a> separating P and a weak form of NC (without bit operations) back in 1994. In a sense, his current program for P vs NP takes off from where that left off (<a href="http://www.math.princeton.edu/~balexeev/weak.pdf">in a very loose way</a>). </p>

<p>The book '<a href="http://www.cs.washington.edu/homes/ruzzo/papers/limits.pdf">Limits on Parallel Computation</a>' has more on this. </p>

CC BY-SA 2.5
2010-10-08T21:33:19.007Z
Beware. I don't think matching is P-complete. Matching is known to be in RNC by polynomial identity testing (test if the determinant of the Tutte matrix of the graph is identically zero). If it were P-complete, then the unlikely collapse P = RNC would follow.
slimton
CC BY-SA 2.5
2010-10-08T21:53:26.160Z
argh. you're right. I should have stuck to max flows. thanks for the correction.
Suresh Venkat
CC BY-SA 2.5
2010-10-08T02:43:36.993Z
2010-10-08T21:54:01.510Z
2010-10-08T21:54:01.510Z
Suresh Venkat
<p>I answered the similar question <em><a href="https://scicomp.stackexchange.com/questions/1391/are-there-any-famous-problems-algorithms-in-scientific-computing-that-cannot-be">Are there any famous problems/algorithms in scientific computing that cannot be sped up by parallelisation</a></em> on the <a href="http://scicomp.stackexchange.com">Computational Science</a> site. Let me quote it here, because it offers a practical perspective on a very concrete instance of such a problem:</p>
<blockquote>
<p>The (famous) fast marching method for solving the Eikonal equation cannot be sped up by parallelization. There are other methods (for example fast sweeping methods) for solving the Eikonal equation that are more amenable to parallelization, but even here the potential for (parallel) speedup is limited.</p>
<p>The problem with the Eikonal equation is that the flow of information depends on the solution itself. Loosely speaking, the information flows along the characteristics (i.e. light rays in optics), but the characteristics depend on the solution itself. And the flow of information for the discretized Eikonal equation is even worse, requiring additional approximations (like implicitly present in fast sweeping methods) if any parallel speedup is desired.</p>
<p>To see the difficulties for parallelization, imagine a nice labyrinth like in some of the examples on <a href="http://math.berkeley.edu/%7Esethian/" rel="nofollow noreferrer">Sethian's webpage</a>. The number of cells on the shortest path through the labyrinth (probably) is a lower bound for the minimal number of steps/iterations of any (parallel) algorithm solving the corresponding problem.</p>
<p>(I write &quot;(probably) is&quot;, because lower bounds are notoriously difficult to prove, and often require some reasonable assumptions on the operations used by an algorithm.)</p>
</blockquote>

CC BY-SA 3.0
2015-12-23T14:11:45.650Z
2015-12-23T14:11:45.650Z
2020-06-17T09:38:08.363Z
Thomas Klimpel
<p>I am curious in a broad sense about what is known about parallelizing algorithms in P. I found the following wikipedia article about the subject:</p>

<p><a href="http://en.wikipedia.org/wiki/NC_%28complexity%29">http://en.wikipedia.org/wiki/NC_%28complexity%29</a></p>

<p>The article contains the following sentence:</p>

<blockquote>
  <p>It is unknown whether NC = P, but most
  researchers suspect this to be false,
  meaning that there are probably some
  tractable problems which are
  "inherently sequential" and cannot
  significantly be sped up by using
  parallelism</p>
</blockquote>

<p>Does this sound reasonable? Are there known cases where a problem in P cannot be sped up using parallelism?</p>

CC BY-SA 2.5
2010-10-08T02:39:13.043Z
See also similar questions http://cstheory.stackexchange.com/questions/1643/nc-p-consequences and http://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem
András Salamon
CC BY-SA 2.5
2010-10-08T11:36:53.710Z
Yes, it sounds reasonable.  A chapter in the book _Computational Complexity_ by Papadimitriou gives a good explanation to learn this subject.
Tsuyoshi Ito
<cc.complexity-theory><complexity-classes><big-picture>
Limits to Parallel Computing
Vladimir Levin
# Limits to Parallel Computing

(Asked by: username_0 on 2010-10-08)

I am curious in a broad sense about what is known about parallelizing algorithms in P. I found the following wikipedia article about the subject:

<http://en.wikipedia.org/wiki/NC_%28complexity%29>

The article contains the following sentence:

> It is unknown whether NC = P, but most
> researchers suspect this to be false,
> meaning that there are probably some
> tractable problems which are
> "inherently sequential" and cannot
> significantly be sped up by using
> parallelism

Does this sound reasonable? Are there known cases where a problem in P cannot be sped up using parallelism?

**Tags:** cc.complexity-theory, complexity-classes, big-picture
> **Comments:**
> **username_1**: See also similar questions http://cstheory.stackexchange.com/questions/1643/nc-p-consequences and http://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem  
> **username_2**: Yes, it sounds reasonable.  A chapter in the book _Computational Complexity_ by Papadimitriou gives a good explanation to learn this subject.  

---

## 3 answers

### Answer by username_1 on 2010-10-08. Score: 17

It is not even known whether [NC](http://qwiki.stanford.edu/index.php/Complexity_Zoo:N#nc) = P, but P-complete problems seem to be inherently hard to parallelize. These include Linear Programming and Horn-SAT. (In contrast, problems in NC seem reasonably easy to parallelize.)

See question [Problems between NC and P: How many have been resolved from this list?](https://cstheory.stackexchange.com/questions/1317/problems-between-nc-and-p-how-many-have-been-resolved-from-this-list) for reference material (including links to a classic textbook that is now available for free download), and further discussion about problems that are in P but not known to be parallelizable.

See question [Generalized Ladner's Theorem](https://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem) for the structure of the complexity classes between NC and P. Briefly, if they differ then there are infinitely many complexity classes strictly between NC and P.

See question [NC = P consequences?](https://cstheory.stackexchange.com/questions/1643/nc-p-consequences) for a nice demonstration by Ryan Williams that it is possible to amplify collapses in the hierarchy of complexity classes within P into perhaps more unlikely collapses like [PSPACE](http://qwiki.stanford.edu/index.php/Complexity_Zoo:P#pspace) = [EXP](http://qwiki.stanford.edu/index.php/Complexity_Zoo:E#exp).

It is worth pointing out that one consequence of Horn-SAT being P-complete, and the links above, is that it does not seem possible to parallelize general SQL queries in databases, unless we can also rewrite any large-scale computation to use only a reasonable amount of storage. This is a puzzling discrepancy -- I think it is quite uncontroversial to state *there are limits on compression*, but I often see articles which seem built on the assumption that it is possible to parallelize *any* database query.

> **Comments:**
> **username_3**: Certainly you may not be able to parallelize any given portion of a database query, or at least in any straightforward manner. However, a database query (excluding subqueries to keep things simple) can be reduced to a full table scan over some joined table, and that joined table itself can always be scanned in parallel. This is why, when you increase parallelism settings in Oracle, it is more inclined to use full table scans rather than indexes.  
> **username_1**: @sclv: This is true, but in general the intermediate joins can be exponential in the input size?  So one can parallelize via joins, but at the cost of having to scan an exponential number of tuples.  
> **username_3**: What do you consider the input size here? Also, if you have an m*n*o cross-join, there's always the possibility that you could return precisely that many tuples -- i.e. there's no possible better bound on the worst-case. And this is more practical than theoretical, but in general you're worried not about parallelizing performance of a predicate over a row anyway, but about IO throughput, since that's where the bound will tend to be.  

---

### Answer by username_4 on 2010-10-08. Score: 10

Well, if there were known cases, then we'd be able to separate P and NC. But there are many problems known to be [P-complete](http://en.wikipedia.org/wiki/P-complete) (i.e under logspace reductions), and they present the same kind of barriers to showing P = NC as NP-complete problems do for P = NP. Among them include linear programming and matching (and max flows in general).

Ketan Mulmuley [proved a result](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.6538) separating P and a weak form of NC (without bit operations) back in 1994. In a sense, his current program for P vs NP takes off from where that left off ([in a very loose way](http://www.math.princeton.edu/~balexeev/weak.pdf)).

The book '[Limits on Parallel Computation](http://www.cs.washington.edu/homes/ruzzo/papers/limits.pdf)' has more on this.

> **Comments:**
> **username_5**: Beware. I don't think matching is P-complete. Matching is known to be in RNC by polynomial identity testing (test if the determinant of the Tutte matrix of the graph is identically zero). If it were P-complete, then the unlikely collapse P = RNC would follow.  
> **username_4**: argh. you're right. I should have stuck to max flows. thanks for the correction.  

---

### Answer by username_6 on 2015-12-23. Score: 0

I answered the similar question *[Are there any famous problems/algorithms in scientific computing that cannot be sped up by parallelisation](https://scicomp.stackexchange.com/questions/1391/are-there-any-famous-problems-algorithms-in-scientific-computing-that-cannot-be)* on the [Computational Science](http://scicomp.stackexchange.com) site. Let me quote it here, because it offers a practical perspective on a very concrete instance of such a problem:

> The (famous) fast marching method for solving the Eikonal equation cannot be sped up by parallelization. There are other methods (for example fast sweeping methods) for solving the Eikonal equation that are more amenable to parallelization, but even here the potential for (parallel) speedup is limited.
>
> The problem with the Eikonal equation is that the flow of information depends on the solution itself. Loosely speaking, the information flows along the characteristics (i.e. light rays in optics), but the characteristics depend on the solution itself. And the flow of information for the discretized Eikonal equation is even worse, requiring additional approximations (like implicitly present in fast sweeping methods) if any parallel speedup is desired.
>
> To see the difficulties for parallelization, imagine a nice labyrinth like in some of the examples on [Sethian's webpage](http://math.berkeley.edu/%7Esethian/). The number of cells on the shortest path through the labyrinth (probably) is a lower bound for the minimal number of steps/iterations of any (parallel) algorithm solving the corresponding problem.
>
> (I write "(probably) is", because lower bounds are notoriously difficult to prove, and often require some reasonable assumptions on the operations used by an algorithm.)


---

