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"?

  • 2
    $\begingroup$ @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. $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 24 '11 at 9:16
  • $\begingroup$ @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. $\endgroup$ – ripper234 Mar 24 '11 at 9:22
  • $\begingroup$ @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. $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 24 '11 at 9:26
  • 4
    $\begingroup$ I am not sure how obtaining $T(n)/k$ on $k$ cores relates to NC which seems to demand more. $\endgroup$ – Raphael Mar 24 '11 at 12:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Marc Hamann Mar 24 '11 at 15:57

Browse other questions tagged or ask your own question.