In section 2 of chapter 4 of Kumar the idea of scaling down is discussed. It is mentioned that the naive method (emulating by assignment) can scale the complexity of the problem more then just "shifting" it from the number of processors to time.
Two things are on my mind with respect to this question.
I'm sure it is interesting to come up with efficient schemes for such conversion for dedicated hardware solutions (say , given the architecture of CUDA , one can implement efficient algorithms based on the size of the different cache levels etc.) Is it interesting from the theory point of view? Can I say something about it without relating to a particular hardware solution? (Say , general schemes for work efficient preserving conversions)
I'm starting to see some possible connections to parameterized complexity. Is there any known work on the area? So far , Iv'e seen two popular papers and that