[Solved]: How to scale down parallel complexity results to constantly many cores?

ignougroup
Problem Detail: I have had problems accepting the complexity theoretic view of “efficiently solved by parallel algorithm” which is given by the class NC:

NC is the class of problems that can be solved by a parallel algorithm in time $O(log^cn)$ on $p(n) in O(n^k)$ processors with $c,k in mathbb{N}$.

We can assume a PRAM. My problem is that this does not seem to say much about “real” machines, that is machines with a finite amount of processors. Now I am told that “it is known” that we can “efficiently” simulate a $O(n^k)$ processor algorithm on $p in mathbb{N}$ processors. What does “efficiently” mean here? Is this folklore or is there a rigorous theorem which quantifies the overhead caused by simulation? What I am afraid that happens is that I have a problem which has a sequential $O(n^k)$ algorithm and also an “efficient” parallel algorithm which, when simulated on $p$ processors, also takes $O(n^k)$ time (which is all that can be expected on this granularity level of analysis if the sequential algorithm is asymptotically optimal). In this case, there is no speedup whatsover as far as we can see; in fact, the simulated parallel algorithm may be slower than the sequential algorithm. That is I am really looking for statements more precise than $O$-bounds (or a declaration of absence of such results).

Asked By : Raphael

Answered By : Tsuyoshi Ito

If you assume that the number of processors is bounded by a constant, then you are right that a problem being in NC does not mean much in practice. Since any algorithm on a PRAM with k processors and t parallel time can be simulated with a single-processor RAM in O(kt) time, the parallel time and the sequential time can differ only by a constant factor if k is a constant. However, if you assume that you can prepare a computer with more processors as the input size grows, then a problem being in NC means that as long as you can prepare more processors, running time will be “very short” or, more precisely, polylogarithmic in the input size. If you think that this assumption is unrealistic, compare it to the assumption of unbounded memory: actual computers have only finite amount of space, but in the study of algorithms and complexity, we almost always assume that a computational device does not have a constant upper bound on space. In practice, this means that we can prepare a computer with more memory as the input size grows, which is how we usually use computers in the real world. NC models an analogous situation in parallel computation.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1647