Gate/transistor number and program length measures of computational complexity?

Question

Are there scaling concepts regarding the number of components needed and minimum program length needed to solve a problem of some complexity?

For example, problems are characterized by O(.) measures of time and space complexity. Space complexity tells me the amount of memory needed but not the number of computational components needed. We assume a Turing machine and count the number of steps performed. But in practice, the number of instructions available, and the level of parallelism have some non-linear relationship with the amount of time needed to solve a problem. Amdahl's law deals with speeding up one part of the problem. On a more general level, there could be at least an empirical or conjectural observation of how physical hardware like NAND gates or transistors scale with problem size or speed.

Thinking in terms of program size, there is Kolmogorov complexity defined as the shortest program that will generate a sequence or other data object. But what about the min. program that will solve a problem? Has anyone defined or used Kolmogorov-like complexity to characterize a problem rather than information content?

Answer 1

Two well-known books in this research area are:

Jeffrey D. Ullman, Computational Aspects of VLSI, Computer Science Press, 1984

and

F. Tom Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, 1991.

The connection between space and time complexity is due to the finite speed of communicating across distance. Thus, a lot of the interesting results are about how various communication networks can (or cannot) be embedded in 3-dimensional space.