# Best problems that are prone to parallelization?

What are some problems that are prone to parallelization? When I think about this, the first thing that comes to my mind is matrix multiplication, which yields to faster calculations, meaning you can get speed ups easily. Any other examples like this?

• Dynamic programming, depending on the structure of the DP table. – Rasto S. Apr 20 '13 at 10:54
• This question is ill-posed. Almost any problem can be solved in parallel very well: just execute the brute-force search in parallel. So what are you really asking? – Raphael Apr 26 '13 at 9:50
• that is true esp for "embarrassingly parallel" and some other "natural" problems, but not true in general. some problems do not seem to break down under "divide and conquer", possibly inherently so. the question turns out to be very similar to (open?) complexity class separations. its an active area of research. – vzn Apr 26 '13 at 15:24
• @vzn Can you give an example for a problem that can not be solved by parallel brute-force search? – Raphael Apr 29 '13 at 10:33
• "example problem that can not be solved by parallel brute-force search?" my understanding, amdahls law seems to show that such problems exist but proving they exist formally is probably as hard as open/difficult complexity class separations – vzn Apr 29 '13 at 15:53

this is actually a somewhat subtle/open question to prove that some particular problems are efficiently or not efficiently parallelizable. see also NC class. The class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. also NC$\stackrel{?}{=}$P is open. wikipedia states:
• @vzn: unfortunately, by definition NC also includes lots of problems which are not efficiently parallelizable. The most infamous example is parallel binary search. The trouble is that this problem has polylogarithmic time complexity even for $p$ = 1. Any sequential algorithm requiring at most logarithmic time in the worst case is in NC regardless of its parallel feasibility! – Massimo Cafaro Apr 26 '13 at 15:51