Theory and applications of probabilistic Kolmogorov complexity

Diverse applications of Kolmogorov complexity to learning [CIKK16], circuit complexity [OPS19], cryptography [LP20], average-case complexity [Hir21], and proof search [Kra22] have been discovered in recent years. Since the running time of algorithms is a key resource in these fields, it is crucial in the corresponding arguments to consider time-bounded variants of Kolmogorov complexity. While fruitful interactions between time-bounded Kolmogorov com- plexity and different areas of theoretical computer science have been known for quite a while (e.g., [Sip83, Ko91, ABK+ 06, AF09], to name a few), the aforementioned results have led to a renewed interest in this topic. The theory of Kolmogorov complexity is well understood, but many useful results and proper- ties of Kolmogorov complexity are not known to hold in time-bounded settings. Unfortunately, this creates technical diffculties or leads to conditional results when applying methods from time-bounded Kolmogorov complexity to algorithms and complexity theory. Perhaps even more importantly, in many cases it is desirable or even necessary to consider randomised algorithms. Since random strings have high complexity, the classical theory of time-bounded Kolmogorov complexity might be inappropriate or simply cannot be applied in such contexts. To mitigate these issues and develop a more robust theory of time-bounded Kolmogorov complexity that survives in the important setting of randomised computations, some recent papers [Oli19, LO21, LOS21, GKLO22, LOZ22] have explored probabilistic notions of time- bounded Kolmogorov complexity, such as rKt complexity [Oli19], rKt complexity [LOS21], and pKt complexity [GKLO22]. These measures consider different ways of encoding an object via a probabilistic representation. In this survey, we provide an introduction to probabilistic time- bounded Kolmogorov complexity and its applications, highlighting many open problems and research directions