So i'm defining the embarassingly parallel complexity class as the set of decision problems which can be solved in time $O(T(n))$ on a single computer and in time $O(T(n)/g(n))+O(\log(g(n))$ if you have access to $O(g(n))$ machines where $g(n)$ can be of a total size up to $T(n)$.

So these are the types of problems, which might be very expensive to solve (or simple), but you can compute them arbitrarily quickly using arbitrarily many processors (and basically unlimited space).

This is a considerably different class than $NC$ in that $NC$ is a subset of $P$ but the class "embarassingly parallel" is not obviously limited to any runtime (and might include extremely complex problems).

I am guessing this sort of class has been considered before. Does anyone know what the standard name of this complexity class/a related one is?


1 Answer 1


There is no complexity class for this, at least none of which I am aware of. Anyway, I would not define embarassingly parallel computations like this: basically, your second term $O(log(g(n))$ does not exist for embarassingly parallel computations. Indeed, by definition, if the computation is embarassingly parallel, then there is no communication overhead in the message-passing setting (or synchronization overhead in the shared-memory setting).

  • $\begingroup$ So the trouble with the decision problem framework is that the output is only T/F. So assuming each of the $g(n)$ processes produced a single bit of information each. To combine all these bits requires a circuit with some kind of depth dependent on $g(n)$ I thought just using a log for the “associative-tree” idea was a reasonable addition. You’re right, this is embarrassingly parallel in the normal sense of the word. $\endgroup$ Jan 9, 2023 at 3:30
  • $\begingroup$ If you need to aggregate in any way the outputs of the process (or threads), then this is not an embarassingly parallel computation. For embarassingly parallel computations, the output is simply the union of the outputs and no communication is required. $\endgroup$ Jan 9, 2023 at 8:33
  • $\begingroup$ My autocorrect removed the “not” in “this is NOT embarrassingly parallel in the normal sense of the word” sorry about that. $\endgroup$ Jan 9, 2023 at 14:42
  • $\begingroup$ Specialized parallel machines can do the aggregation in constant time, e.g. the CRCW PRAM can perform an AND in constant time. But this does not hold in general. Defining a complexity case for your special case is overkill. A class should contain natural and relevant problems capturing a genuine computation phenomenon, your case is too simple in my opinion. $\endgroup$ Jan 11, 2023 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.