Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR22-084 | 2nd June 2022 22:08

#### Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity

TR22-084
Authors: Yanyi Liu, Rafael Pass
Publication: 3rd June 2022 09:33
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint