Kolmogorov complexity
E183589
Kolmogorov complexity is a measure of the amount of information in an object, defined as the length of the shortest computer program that can produce it.
All labels observed (6)
| Label | Occurrences |
|---|---|
| Kolmogorov complexity canonical | 11 |
| Chaitin’s incompleteness theorem | 1 |
| algorithmic randomness | 1 |
| plain Kolmogorov complexity | 1 |
| prefix Kolmogorov complexity | 1 |
| prefix-free Kolmogorov complexity | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T1637527 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Kolmogorov complexity Context triple: [Occam's razor, relatedConcept, Kolmogorov complexity]
-
A.
Blum complexity measures
Blum complexity measures are a formal framework in computational complexity theory that rigorously define and compare the resource usage (such as time or space) of algorithms via axiomatic conditions.
-
B.
Computability Theory
Computability Theory is a branch of theoretical computer science and mathematical logic that studies which problems can be solved by algorithms and how efficiently they can be computed.
-
C.
Shannon entropy
Shannon entropy is a fundamental measure in information theory that quantifies the average uncertainty or information content in a random variable or message source.
-
D.
Complexity Theory
Complexity Theory is a branch of theoretical computer science that studies the resources, such as time and space, required to solve computational problems and classifies these problems based on their inherent difficulty.
-
E.
Shannon–Khinchin axioms
The Shannon–Khinchin axioms are a set of fundamental conditions that uniquely characterize Shannon entropy as the standard measure of information and uncertainty in probability theory and information theory.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Kolmogorov complexity Target entity description: Kolmogorov complexity is a measure of the amount of information in an object, defined as the length of the shortest computer program that can produce it.
-
A.
Blum complexity measures
Blum complexity measures are a formal framework in computational complexity theory that rigorously define and compare the resource usage (such as time or space) of algorithms via axiomatic conditions.
-
B.
Computability Theory
Computability Theory is a branch of theoretical computer science and mathematical logic that studies which problems can be solved by algorithms and how efficiently they can be computed.
-
C.
Shannon entropy
Shannon entropy is a fundamental measure in information theory that quantifies the average uncertainty or information content in a random variable or message source.
-
D.
Complexity Theory
Complexity Theory is a branch of theoretical computer science that studies the resources, such as time and space, required to solve computational problems and classifies these problems based on their inherent difficulty.
-
E.
Shannon–Khinchin axioms
The Shannon–Khinchin axioms are a set of fundamental conditions that uniquely characterize Shannon entropy as the standard measure of information and uncertainty in probability theory and information theory.
- F. None of above. chosen
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
complexity measure
ⓘ
computability-theoretic concept ⓘ information-theoretic measure ⓘ |
| alsoKnownAs |
algorithmic complexity
ⓘ
descriptive complexity ⓘ program-size complexity ⓘ |
| coreIdea | measures information content via shortest effective description ⓘ |
| definedOver |
finite binary strings
ⓘ
finite strings ⓘ |
| definition | length of the shortest program that outputs a given object and then halts ⓘ |
| dependsOn | choice of universal Turing machine ⓘ |
| field | algorithmic information theory ⓘ |
| hasVariant |
conditional Kolmogorov complexity
ⓘ
monotone Kolmogorov complexity ⓘ Kolmogorov complexity self-linksurface differs ⓘ
surface form:
plain Kolmogorov complexity
Kolmogorov complexity self-linksurface differs ⓘ
surface form:
prefix Kolmogorov complexity
Kolmogorov complexity self-linksurface differs ⓘ
surface form:
prefix-free Kolmogorov complexity
space-bounded Kolmogorov complexity ⓘ time-bounded Kolmogorov complexity ⓘ |
| implies | no algorithm can compute exact Kolmogorov complexity for all strings ⓘ |
| independentlyDevelopedBy |
Gregory Chaitin
ⓘ
Ray Solomonoff ⓘ |
| introducedBy |
Andrei Kolmogorov
ⓘ
surface form:
Andrey Kolmogorov
|
| invarianceProperty | different universal Turing machines change complexity by at most an additive constant ⓘ |
| keyResult |
incompressibility method in combinatorics and complexity theory
ⓘ
most strings of length n have Kolmogorov complexity close to n ⓘ only a small fraction of strings are highly compressible ⓘ |
| mathematicalDomain |
information theory
ⓘ
mathematical logic ⓘ theoretical computer science ⓘ |
| namedAfter |
Andrei Kolmogorov
ⓘ
surface form:
Andrey Kolmogorov
|
| property |
non-computable
ⓘ
not computable by any algorithm ⓘ |
| relatedTo |
Halting problem
ⓘ
surface form:
Chaitin's constant
Martin-Löf randomness ⓘ Shannon entropy ⓘ data compression ⓘ minimum description length principle ⓘ universal Turing machine ⓘ |
| semiComputableProperty | upper semicomputable ⓘ |
| symbol |
C(x)
ⓘ
K(x) ⓘ |
| timePeriodOfDevelopment | 1960s ⓘ |
| usedFor |
characterizing algorithmic randomness
ⓘ
formalizing Occam's razor ⓘ formalizing randomness of individual strings ⓘ foundations of inductive inference ⓘ foundations of machine learning theory ⓘ proving lower bounds in theoretical computer science ⓘ studying incompressibility ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Kolmogorov complexity Description of subject: Kolmogorov complexity is a measure of the amount of information in an object, defined as the length of the shortest computer program that can produce it.
Referenced by (16)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
algorithmic randomness
this entity surface form:
Chaitin’s incompleteness theorem
this entity surface form:
prefix Kolmogorov complexity
this entity surface form:
plain Kolmogorov complexity
this entity surface form:
prefix-free Kolmogorov complexity
Universal Intelligence: A Definition of Machine Intelligence
→
usesConcept
→
Kolmogorov complexity
ⓘ