Kolmogorov complexity as a combinatorial tool

Alexander Shen

doi:10.1007/978-3-031-64309-5_3

Retour

Kolmogorov complexity as a combinatorial tool

Acte de colloque

Open Access

Kolmogorov complexity as a combinatorial tool

Alexander Shen

Twenty Years of Theoretical and Practical Synergies, Vol.14773, pp.27-31

Lecture Notes in Computer Science

CiE 2024 - 20th Conference on Computability in Europe (Amsterdam, Netherlands, 08/07/2024–12/07/2024)

16/05/2024

DOI: https://doi.org/10.1007/978-3-031-64309-5_3

Résumé

Kolmorogov complexity

Combinatorial game

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).

Fichiers et liens (1)

url

Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Titre: Kolmogorov complexity as a combinatorial tool
Créateurs - sans rôle: Alexander Shen - Systèmes complexes, automates et pavages
Détails de publication: Twenty Years of Theoretical and Practical Synergies, Vol.14773, pp.27-31
Colloque: CiE 2024 - 20th Conference on Computability in Europe (Amsterdam, Netherlands, 08/07/2024–12/07/2024)
Publications en série: Lecture Notes in Computer Science
Identifiants: 9937967409311
Unité académique: Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - LIRMM
Langue: English
Type de ressource: Conference proceeding
Champs locaux: lirmm-04647436