Fitxers

TFM_Ünal_Aydos.pdf (611.2 KB)

Tipus de document

Treball de fi de màster

Data de publicació

2026-06-19

Llicència de publicació

cc by-nc-nd (c) Ünal, Aydos, 2026
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/230871

Search to Decision Procedures for Time Bounded Kolmogorov Complexity

Títol de la revista

Autors

Director/Tutor

ISSN de la revista

Títol del volum

Recurs relacionat

Resum

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.

Descripció

Treballs Finals del Màster de Lògica Pura i Aplicada, Facultat de Filosofia, Universitat de Barcelona. Curs: 2025-2026. Tutor: Atserias, Albert

Matèries

Lògica, Complexitat computacional, Kolmogorov, A. N. (Andrei Nikolaevich), 1903-1987, Treballs de fi de màster

Matèries (anglès)

Logic, Computational complexity, Kolmogorov, A. N. (Andrei Nikolaevich), 1903-1987, Master's thesis

Citació

Col·leccions

Màster Oficial - Pure and Applied Logic / Lògica Pura i aplicada

Citació

ÜNAL, Aydos. Search to Decision Procedures for Time Bounded Kolmogorov Complexity. [consulted: 23 of July of 2026]. Available at: https://hdl.handle.net/2445/230871

Exportar metadades

JSON - METS

Compartir registre