HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is static complexity?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
staticcomplexitywhat

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#85963, answer score: 4

Revisions (0)

No revisions yet.