Describing dataDescription length We introduce the notion of description length, which is the length of a program used to generate an object.
The easiest way of describing objects is to distinguish them within a set.
Description complexity of integers Integers can easily be distinguished by their rank in ℕ. But this method does not see why round numbers are simple.
Complexity and structure Can we determine the complexity of an object by its structure? We illustrate this possibility by considering passwords: a good password should be simple to remember and complex to guess.
Defining complexity We define Kolmogorov complexity, which is the core of this course. It corresponds to the minimal description length of an object. This quantity depends on a reference machine, but the "invariance theorem" makes it objective.
Conditional complexity Sometimes, having access to another object can be a good proxy to provide an efficient description. This idea is involved in the definition of conditional complexity. A link between non-conditional complexity and conditional complexity is given by the "chain rule", which plays a prominent role, especially in AI.