2024/05/15 by Alexander Shen, Shen, Alexander
Computer Science · #68Q87 #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #F.1.2 #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2405.09304
openalex publication_date 2024/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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).