<blockquote>
  <p><strong>Possible Duplicate:</strong><br>
  <a href="https://cstheory.stackexchange.com/questions/2017/limits-to-parallel-computing">Limits to Parallel Computing</a>  </p>
</blockquote>



<p>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.</p>

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

CC BY-SA 2.5
2011-03-24T09:16:13.837Z
@ripper234: While this is a nice question, it is possibly duplicated to [this question](http://cstheory.stackexchange.com/q/2017/1800). 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 張顯之
CC BY-SA 2.5
2011-03-24T09:22:21.273Z
@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
CC BY-SA 2.5
2011-03-24T09:26:45.313Z
@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 張顯之
CC BY-SA 2.5
2011-03-24T09:39:33.560Z
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
CC BY-SA 2.5
2011-03-24T10:01:27.197Z
As @Hsien commented, since this would imply NC != P is , then the answer right now is "it's not known".
ripper234
CC BY-SA 2.5
2011-03-24T12:42:12.487Z
I am not sure how obtaining $T(n)/k$ on $k$ cores relates to NC which seems to demand more.
Raphael
CC BY-SA 2.5
2011-03-24T15:57:50.830Z
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
<dc.parallel-comp>
Is there a problem which is provably not parallelizable?
ripper234
# Is there a problem which is provably not parallelizable?

(Asked by: username_0 on 2011-03-24)

> **Possible Duplicate:**  
> [Limits to Parallel Computing](https://cstheory.stackexchange.com/questions/2017/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"?

**Tags:** dc.parallel-comp
> **Comments:**
> **username_1**: @ripper234: While this is a nice question, it is possibly duplicated to [this question](http://cstheory.stackexchange.com/q/2017/1800). 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.  
> **username_0**: @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.  
> **username_1**: @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.  
> **username_0**: 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.  
> **username_0**: As @Hsien commented, since this would imply NC != P is , then the answer right now is "it's not known".  
> **username_2**: I am not sure how obtaining $T(n)/k$ on $k$ cores relates to NC which seems to demand more.  
> **username_3**: 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.  

---

## 0 answers

