22
$\begingroup$

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?

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
17
$\begingroup$

It is not even known whether 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? 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 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? 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 = 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – sclv
    Commented Mar 23, 2011 at 0:10
  • $\begingroup$ @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. $\endgroup$
    – András Salamon
    Commented Mar 23, 2011 at 11:06
  • 1
    $\begingroup$ What do you consider the input size here? Also, if you have an mno 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. $\endgroup$
    – sclv
    Commented Mar 23, 2011 at 11:37
10
$\begingroup$

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 (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 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).

The book 'Limits on Parallel Computation' has more on this.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – slimton
    Commented Oct 8, 2010 at 21:33
  • $\begingroup$ argh. you're right. I should have stuck to max flows. thanks for the correction. $\endgroup$
    – Suresh Venkat
    Commented Oct 8, 2010 at 21:53
0
$\begingroup$

I answered the similar question Are there any famous problems/algorithms in scientific computing that cannot be sped up by parallelisation on the Computational Science 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. 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.)

Improve this answer
$\endgroup$

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.