A search-to-decision reduction is a procedure that allows one to find a solution to a problem from the mere ability to decide when a solution exists. The existence of a search-to-decision reduction for time-bounded Kolmogorov complexity, i.e., the problem of checking if a string $x$ can be generated by a $t$-time bounded program of description length $s$, is a long-standing open problem that dates back to the 1960s.

In this work, we obtain new average-case and worst-case search-to-decision reductions for the complexity measure $K^t$ and its randomized analogue $rK^t$:

(Conditional Errorless and Error-Prone Reductions for $K^t$) Under the assumption that $E$ requires exponential size circuits, we design polynomial-time average-case search-to-decision reductions for $K^t$ in both errorless and error-prone settings.

In fact, under the easiness of deciding $K^t$ under the uniform distribution, we obtain a search algorithm for any given polynomial-time samplable distribution. In the error-prone reduction, the search algorithm works in the more general setting of conditional $K^t$ complexity, i.e., it finds a minimum length $t$-time bound program for generating $x$ given a string $y$.

(Unconditional Errorless Reduction for $rK^t$) We obtain an unconditional polynomial-time average-case search-to-decision reduction for $rK^t$ in the errorless setting. Similarly to the results described above, we obtain a search algorithm for each polynomial-time samplable distribution, assuming the existence of a decision algorithm under the uniform distribution.

To our knowledge, this is the first unconditional sub-exponential time search-to-decision reduction among the measures $K^t$ and $rK^t$ that works with respect to any given polynomial-time samplable distribution.

(Worst-Case to Average-Case Reductions) Under the errorless average-case easiness of deciding $rK^t$, we design a worst-case search algorithm running in time $2^{O(n/\log n)}$ that produces a minimum length randomized $t$-time program for every input string $x \in \{0,1\}^n$, with the caveat that it only succeeds on some explicitly computed sub-exponential time bound $t \leq 2^{n^{\varepsilon}}$ that depends on $x$. A similar result holds for $K^t$, under the assumption that $E$ requires exponential size circuits.

In these results, the corresponding search problem is solved \emph{exactly}, i.e., a successful run of the search algorithm outputs a $t$-time bounded program for $x$ of minimum length, as opposed to an approximately optimal program of slightly larger description length or running time.