Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-084 | 2nd June 2022 22:08

Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity

RSS-Feed




TR22-084
Authors: Yanyi Liu, Rafael Pass
Publication: 3rd June 2022 09:33
Downloads: 239
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