Kolmogorov Complexity with games

Reading Suggestions - 15 August 2023

Many problems in complexity can be reduced to winning a game.

Here is a nice example by Bauwens in:

Complexity of complexity and maximal plain versus prefix-free Kolmogorov complexity

More examples are given in the end.


Articles on games and Kolmogorov complexity