Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
    
Yes, it sounds reasonable. A chapter in the book Computational Complexity by Papadimitriou gives a good explanation to learn this subject. –  Tsuyoshi Ito Oct 8 '10 at 11:36

2 Answers 2

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.

share|improve this answer
    
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 Mar 23 '11 at 0:10
    
@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 Mar 23 '11 at 11:06
1  
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 Mar 23 '11 at 11:37

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.

share|improve this answer
2  
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 Oct 8 '10 at 21:33
    
argh. you're right. I should have stuck to max flows. thanks for the correction. –  Suresh Venkat Oct 8 '10 at 21:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.