5
$\begingroup$

Definition : Kolmogorov complexity is a static complexity measure that captures the difficulty of describing a string.

For example, the string consisting of three million zeroes can be described with fewer than three million symbols (as in this sentence)

From wikipedia

In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as descriptive complexity, Kolmogorov–Chaitin complexity, algorithmic entropy, or program-size complexity

I am not able to understand few things like " static complexity " and why we need it

Improve this question
$\endgroup$
1
  • $\begingroup$ You can find a formal definition on "Classical recursion theory" Chapter VII.1, in the context of recursion theory. $\endgroup$
    – user1868607
    Dec 7, 2020 at 21:40

1 Answer 1

Reset to default
4
$\begingroup$

Complexities in this context could be divided into dynamic and static:

  • Dynamic complexity is an attribute of the execution of a program with the string as an input. For example, the time or space complexity of a Turing machine to accept or reject a string.
  • Static complexity is an attribute of a program that receives the string as input but not its execution. As you stated, Kolmogorov complexity is a static complexity since it is the length of the shortest program that creates the given string, an attribute that implies nothing about the execution of the program.
Improve this answer
$\endgroup$
1
  • $\begingroup$ "Algorithms and Theory of Computation Handbook, Second Edition, Volume 1", chapter 24 page 21. IMHO it is not a formal definition since it is not stated explicitly anywhere on the internet, I understood it from the context of where the quote was taken from. $\endgroup$
    – David Taub
    Dec 28, 2017 at 16:24

Your Answer

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

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