<p>The word you are missing to bind the two terms is "concurrency".</p>

<p>My favorite phrasing [1] is the following:</p>

<blockquote>
  <ul>
  <li><p>Concurrency is non-determinism with regards to the order in which events <em>may</em> occur.</p></li>
  <li><p>Parallelism is the degree to which events occur simultaneously.</p></li>
  </ul>
</blockquote>

<p>Another way to look at it is that descriptions of computations that allow non-determinism in the scheduling of operations are suitable for parallel execution (and the corresponding expected performance improvements).</p>

<p>[1] from PKF Holzenspies. On run-time exploitation of concurrency. PhD thesis, University of Twente, Enschede, the Netherlands, April 2010. URL <a href="http://doc.utwente.nl/70959/" rel="nofollow">http://doc.utwente.nl/70959/</a>. page 3.</p>

CC BY-SA 3.0
2012-07-15T00:22:59.943Z
2012-07-15T00:22:59.943Z
kena
<p>pondering another Q/A &amp; the responses on here[1] leads to this question:</p>

<blockquote>
  <p>whats the difference between nondeterminism and parallelism?</p>
</blockquote>

<p>am aware of basic answers. have some of my own ideas on this &amp; have researched some of the basics but think it can be seen as a nontrivial, subtle, or even deep question that can be answered multiple valid ways &amp; relates to open areas of research.</p>

<p>am also interested in accounts that attempt to explain one in terms of the other or contrast the two or relate the two in a theoretical way.</p>

<p>[1] <a href="https://cstheory.stackexchange.com/a/12009/7884">media "fails" in describing/summarizing TCS</a></p>

CC BY-SA 3.0
2012-07-14T18:04:25.013Z
I think it would help if you could elaborate on what you think basic answers are and what you think is nontrivial, subtle, etc.
Vijay D
CC BY-SA 3.0
2012-07-14T19:52:42.953Z
fair enough. there are textbook definitions of nondeterminism & parallelism neither of which reference the other and which are basic. nontrivial answers would tie in how they are similar or can be defined in terms of each other or refer to complexity classes etc. also the distinction of NP vs coNP seems crucial... etc
vzn
CC BY-SA 3.0
2012-07-14T20:15:32.067Z
The two notions are completely different, and this is why usually the definition of one does not refer to the other.  I understand that there is a possibility that a student who has just learned the two notions may incorrectly think that they may be related, but asking for an explanation of the difference between them is hardly a research-level question.  Please remember that you are asking your questions on a website dedicated to research-level questions.
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-14T22:51:48.640Z
This question doesn't make sense as is. What makes you think they're related? What's the difference between a fish and a bicycle?
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2012-07-15T02:33:19.910Z
sigh I guess I have to spell it out as usual. nondeterminism seems very similar to what are called "embarrassingly parallel" problems in which instances of the problem can be computed separately with no intercommunication between processes. an old example is computing pixels of the mandelbrot set. am sure there are many more analogies & connections but I guess the field is waiting for an einstein-level intellect to map out the terra incognita for the unwashed masses, wink. (in the meantime you can all gang up on me and downvote my incoherent questions, wink.)
vzn
CC BY-SA 3.0
2012-07-15T04:28:19.840Z
calling something embarrassingly parallel when an exponential number of processors would need to do polynomial work each seems improper and misleading usage of the term. is sorting embarrassingly parallel because one can check the $n!$ permutations in parallel?
Sasho Nikolov
CC BY-SA 3.0
2012-07-15T09:30:06.513Z
There is nothing to sigh about having to spell things out. The terms 'nondeterminism' and 'parallelism' mean different things in different contexts. I could interpret them in the process algebra, programming language, or the automata theory sense. Each is different.
Vijay D
CC BY-SA 3.0
2012-07-15T09:33:02.143Z
Just a suggestion: if you could make your question much more precise, it would help. Please add to the question (formal or informal) definitions of nondeterminism, parallelism, what you think is a basic answer and what an example of a non-trivial answer is. Maybe what a trivial answer is, and why would also help.
Vijay D
CC BY-SA 3.0
2012-07-15T11:18:39.983Z
Although a student or someone unfamiliar with complexity theory might confuse these two, the difference is quite clear. Therefore this post doesn't look like a research-level question. I would suggest posting a question on [cs.se] if you don't know the difference or if the difference is not clear for you. If you know the difference then please include it in the question and be more specific about what you want to know. In its current form the question looks like "can someone explain apples in terms of oranges".
Kaveh
<cc.complexity-theory><reference-request>
whats the difference between nondeterminism and parallelism?
vzn
# whats the difference between nondeterminism and parallelism?

(Asked by: username_0 on 2012-07-14)

pondering another Q/A & the responses on here[1] leads to this question:

> whats the difference between nondeterminism and parallelism?

am aware of basic answers. have some of my own ideas on this & have researched some of the basics but think it can be seen as a nontrivial, subtle, or even deep question that can be answered multiple valid ways & relates to open areas of research.

am also interested in accounts that attempt to explain one in terms of the other or contrast the two or relate the two in a theoretical way.

[1] [media "fails" in describing/summarizing TCS](https://cstheory.stackexchange.com/a/12009/7884)

**Tags:** cc.complexity-theory, reference-request

> **Comments:**
> **username_1**: I think it would help if you could elaborate on what you think basic answers are and what you think is nontrivial, subtle, etc.  
> **username_0**: fair enough. there are textbook definitions of nondeterminism & parallelism neither of which reference the other and which are basic. nontrivial answers would tie in how they are similar or can be defined in terms of each other or refer to complexity classes etc. also the distinction of NP vs coNP seems crucial... etc  
> **username_2**: The two notions are completely different, and this is why usually the definition of one does not refer to the other.  I understand that there is a possibility that a student who has just learned the two notions may incorrectly think that they may be related, but asking for an explanation of the difference between them is hardly a research-level question.  Please remember that you are asking your questions on a website dedicated to research-level questions.  
> **username_3**: This question doesn't make sense as is. What makes you think they're related? What's the difference between a fish and a bicycle?  
> **username_0**: sigh I guess I have to spell it out as usual. nondeterminism seems very similar to what are called "embarrassingly parallel" problems in which instances of the problem can be computed separately with no intercommunication between processes. an old example is computing pixels of the mandelbrot set. am sure there are many more analogies & connections but I guess the field is waiting for an einstein-level intellect to map out the terra incognita for the unwashed masses, wink. (in the meantime you can all gang up on me and downvote my incoherent questions, wink.)  
> **username_4**: calling something embarrassingly parallel when an exponential number of processors would need to do polynomial work each seems improper and misleading usage of the term. is sorting embarrassingly parallel because one can check the $n!$ permutations in parallel?  
> **username_1**: There is nothing to sigh about having to spell things out. The terms 'nondeterminism' and 'parallelism' mean different things in different contexts. I could interpret them in the process algebra, programming language, or the automata theory sense. Each is different.  
> **username_1**: Just a suggestion: if you could make your question much more precise, it would help. Please add to the question (formal or informal) definitions of nondeterminism, parallelism, what you think is a basic answer and what an example of a non-trivial answer is. Maybe what a trivial answer is, and why would also help.  
> **username_5**: Although a student or someone unfamiliar with complexity theory might confuse these two, the difference is quite clear. Therefore this post doesn't look like a research-level question. I would suggest posting a question on [cs.se] if you don't know the difference or if the difference is not clear for you. If you know the difference then please include it in the question and be more specific about what you want to know. In its current form the question looks like "can someone explain apples in terms of oranges".  

---

## 1 answers

### Answer by username_6 on 2012-07-15. Score: 3 | Accepted answer

The word you are missing to bind the two terms is "concurrency".

My favorite phrasing [1] is the following:

> * Concurrency is non-determinism with regards to the order in which events *may* occur.
> * Parallelism is the degree to which events occur simultaneously.

Another way to look at it is that descriptions of computations that allow non-determinism in the scheduling of operations are suitable for parallel execution (and the corresponding expected performance improvements).

[1] from PKF Holzenspies. On run-time exploitation of concurrency. PhD thesis, University of Twente, Enschede, the Netherlands, April 2010. URL <http://doc.utwente.nl/70959/>. page 3.


---

