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?

  • 1
    $\begingroup$ Regarding "program length", you might be interested to read about non-uniform complexity classes (e.g., circuit complexity). $\endgroup$
    – D.W.
    Mar 8, 2017 at 4:37
  • $\begingroup$ See especially the "NC vs. P" problem. $\endgroup$ Mar 8, 2017 at 11:09

1 Answer 1


Two well-known books in this research area are:

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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.