Computer science Randomized, circuit, counting and interactive complexity Concept
Kolmogorov complexity
Summary
The Kolmogorov complexity of a finite string is the length of a shortest program that prints the string. It measures how much information the string contains, or how far it can be compressed. By the invariance theorem the choice of programming language changes the complexity only by a bounded amount. It is the basis of algorithmic information theory and of algorithmic randomness.
Where this leads
1 page builds on this one.
Further reading
About this page
| Tag | 8PY3K6NCKF |
|---|---|
| URI | m2://8PY3K6NCKF |
| Kind | concept |
| Writing | W0 stub |
| MSC | 68Q30, 03D32 |
| Same as | |
| Changed | 2 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.