A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. We consider this problem in the context of promise problems (i.e,. the $\prBPP$ v.s. $\prP$ problem) and show that for all sufficiently large constants $c$, the following are \emph{equivalent}:
\BI
\item $\prBPP=\prP$.
\item For every $\BPTIME(n^c)$ algorithm $M$, and every sufficiently large $z \in \{0,1\}^n$, there exists some $x \in \{0,1\}^n$ such that $M$ fails to decide whether $Kt(x \mid z)$ is ``very large'' ($\geq n-1$) or ``very small'' ($\leq O(\log
n)$).
\EI
where $Kt(x \mid z$) denotes the Levin-Kolmogorov complexity of $x$ conditioned on $z$.

As far as we are aware, this yields the first full \emph{characterization} of when $\prBPP = \prP$ through the hardness of some class of problems. Previous hardness assumptions used for derandomization only provide a one-sided implication.