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?