2

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

Community
  • 1
ripper234
  • 873
  • 10
  • 15
  • 2
    @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 09: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 09: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 09:26
  • So this is an excellent answer to this question (because I believe it's really more focused than the other one). I'll post it myself and accept it eventually, but if you post it as well I'd rather accept your answer. – ripper234 Mar 24 '11 at 09:39
  • 4
    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
  • 1
    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
  • As @Hsien commented, since this would imply NC != P is , then the answer right now is "it's not known". – ripper234 Mar 24 '11 at 10:01

0 Answers0