# name
Search to Decision Procedures for Time Bounded Kolmogorov Complexity

# metadata.dc.description[].value
Treballs Finals del Màster de Lògica Pura i Aplicada, Facultat de Filosofia, Universitat de Barcelona. Curs: 2025-2026. Tutor: Atserias, Albert

# metadata.dc.description.abstract[].value
In the 2024 paper “Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity”, Hirahara, Kabanets, Lu, and Oliveira apply modern meta-complexity techniques—such as symmetry of information and computational depth—to solve a foundational open problem in time-bounded Kolmogorov complexity. This recent breakthrough provides exact search-to-decision reductions that can find exact minimal programs over any polynomial-time samplable distribution, whereas earlier works mainly focused on approximate reductions that output larger or slower programs. This master’s thesis unpacks their work, explaining in detail the underlying tools, technical mechanics, and proofs required to establish these results.

# metadata.dc.source[].value
Màster Oficial - Pure and Applied Logic / Lògica Pura i aplicada

# metadata.dc.subject.classification[].value
Kolmogorov, A. N. (Andrei Nikolaevich), 1903-1987

# metadata.dc.subject.other[].value
Kolmogorov, A. N. (Andrei Nikolaevich), 1903-1987

# metadata.dc.title[].value
Search to Decision Procedures for Time Bounded Kolmogorov Complexity