A long-standing open problem dating back to the 1960s is whether there exists a search-to-decision reduction for the time-bounded Kolmogorov complexity problem - that is, the problem of determining whether the length of the shortest time-$t$ program generating a given string $x$ is at most $s$.

In this work, we consider the more ``robust" version of the time-bounded Kolmogorov complexity problem, referred to as the GapMINKT problem, where given a size bound $s$ and a running time bound $t$, the goal is to determine whether there exists a $poly(t,|x|)$-time program of length $s+\log |x|$ that generates $x$. We present the first non-trivial search-to-decision reduction $R$ for the GapMINKT problem; $R$ has a running-time bound of $2^{\epsilon n}$ for any $\epsilon > 0$ and additionally only queries its oracle on ``thresholds" $s$ of size $s+\log |x|$. As such, we get that any algorithm with running-time (resp. circuit size) $2^{\alpha s} poly(|x|,t,s)$ for solving GapMINKT (given an instance $(x,t,s)$, yields an algorithm for finding a witness with running-time (resp. circuit size) $2^{(\alpha+\epsilon) s} poly(|x|,t,s)$.

Our second results is a polynomial-time search-to-decision reduction for the time-bounded Kolmogorov complexity problem in the average-case regime. Such a reduction was recently shown by Liu and Pass (FOCS'20), heavily relying on cryptographic techniques. Our reduction is more direct and additionally has the advantage of being length-preserving, and as such also applies in the exponential time/size regime.

A central component in both of these results is the use of Kolmogorov and Levin's Symmetry of Information Theorem.

A long-standing open problem dating back to the 1960s is whether there exists a search-to-decision reduction for the time-bounded Kolmogorov complexity problem - that is, the problem of determining whether the length of the shortest time-$t$ program generating a given string $x$ is at most $s$.

In this work, we consider the more ``robust" version of the time-bounded Kolmogorov complexity problem, referred to as the GapMINKT problem, where given a size bound $s$ and a running time bound $t$, the goal is to determine whether there exists a $poly(t,|x|)$-time program of length $s+\log |x|$ that generates $x$. We present the first non-trivial search-to-decision reduction $R$ for the GapMINKT problem; $R$ has a running-time bound of $2^{\epsilon n}$ for any $\epsilon > 0$ and additionally only queries its oracle on ``thresholds" $s$ of size $s+\log |x|$. As such, we get that any algorithm with running-time (resp. circuit size) $2^{\alpha s} poly(|x|,t,s)$ for solving GapMINKT (given an instance $(x,t,s)$, yields an algorithm for finding a witness with running-time (resp. circuit size) $2^{(\alpha+\epsilon) s} poly(|x|,t,s)$.

Our second results is a polynomial-time search-to-decision reduction for the time-bounded Kolmogorov complexity problem in the average-case regime. Such a reduction was recently shown by Liu and Pass (FOCS'20), heavily relying on cryptographic techniques. Our reduction is more direct and additionally has the advantage of being length-preserving, and as such also applies in the exponential time/size regime.

A central component in both of these results is the use of Kolmogorov and Levin's Symmetry of Information Theorem.