# Is there a problem which is provably not parallelizable? [duplicate]

Possible Duplicate:
Limits to Parallel Computing

A friend just asked me, if for every problem that takes time t on one processor, solving it on two processors will take t/2. Obviously, this is not known in the general case.

Is there a counter examples to this? Meaning, is there a problem that is provably "hard to parallel"?

• @ripper234: While this is a nice question, it is possibly duplicated to this question. Some of the links within are also nice. People works in algorithms may think that the max-flow problem is hard to parallel. Hope this help! Vote to close as duplicate. – Hsien-Chih Chang 張顯之 Mar 24 '11 at 9:16
• @Hsien - I think the answer is simply "we don't know of any concrete example today". This answer is much simpler than the discussion at the answer you linked to. I suggest to keep this open, and if you think that this is indeed the answer, post it and I'll accept it. – ripper234 Mar 24 '11 at 9:22
• @ripple234: Yes, since a concrete example will imply strong consequences in complexity theory (that is, $\mathsf{NC} \neq \mathsf{P}$.) Also, we need 5 votes to close a question, so let the community decides. Personally I would like to see more people share their insights, but rather in one discussion thread than two threads, which benefits the future users. – Hsien-Chih Chang 張顯之 Mar 24 '11 at 9:26
• I am not sure how obtaining $T(n)/k$ on $k$ cores relates to NC which seems to demand more. – Raphael Mar 24 '11 at 12:42
• I'd recommend changing the title to use the word "parallelizable", which is more standard and is more likely to be found by a search. – Marc Hamann Mar 24 '11 at 15:57