Conference Papers Year : 2024

Kolmogorov complexity as a combinatorial tool

Alexander Shen

Abstract

Kolmogorov complexity is often used as a convenient language for counting and/or probabilistic existence proofs. However, there are some applications where Kolmogorov complexity is used in a more subtle way. We provide one (somehow) surprising example where an existence of a winning strategy in a natural combinatorial game is proven (and no direct proof is known).
Fichier principal
Vignette du fichier
2405.09304v1.pdf (126.58 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-04647436 , version 1 (14-07-2024)

Identifiers

Cite

Alexander Shen. Kolmogorov complexity as a combinatorial tool. CiE 2024 - 20th Conference on Computability in Europe, Computability in Europe association, Jul 2024, Amsterdam, Netherlands. pp.27-31, ⟨10.1007/978-3-031-64309-5_3⟩. ⟨lirmm-04647436⟩
25 View
13 Download

Altmetric

Share

More