[nitfol]

In the real world, taking exponential space implies taking exponential time. The fastest you can transmit information is the speed of light, so it will take exponential time to communicate with the furthest pieces of your exponentially large system.

[suppressingfire]

Depends on the problem and how you distribute data.

e.g., each node can generate its own subset to check, so you only need to distribute the program and input. That can be done using a multicast tree of some kind which brings distribution costs back down by a log.

[dhume]

But if you only have a finite amount of hardware available (which is probably the case), each node's data set grows exponentially with input size.

If your node population increases exponentially with input size, you're still running into the speed-of-light delay problem mentioned above (cube root of exponential is still exponential). If your solution is polynomial time with polynomially many nodes, your space cost is also polynomial.

[someone_here]

This could be said about almost all "polynomial time" algorithms though. The bigger the loop, the larger the variables you'll need (in general), and the more time you'll need to communicate between the pieces.

[cynicalkane]

OK, but the amount of data you need to access will be bounded by a polynomial...