Limits to Parallel Computing 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?
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&#39;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.