Search to Decision Procedures for Time Bounded Kolmogorov Complexity

Abstract

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.