There are successes with an increasing numbers of individual computational units in GPUs or as processor cores. Given someone made the effort to build a huge array of processors which - however - can only communicate locally with their neighbors (let's say on a hex grid in 2D - not arbitrary distance connections), how will time complexities of algorithms change and which algorithms will profit and which will never be fast enough?
Let's assume the number of processors is allowed to scale up as O(N). Probably many physics simulation can get a significant boost, however, some problems might require complex interaction between all parts of the data such that the time complexity cannot get below some limit. Are there results for this kind of problem?
PS: I have general math and computation knowledge, but I will try to understand technical details as much as possible :)