ECCC-Report TR22-084https://eccc.weizmann.ac.il/report/2022/084Comments and Revisions published for TR22-084en-usFri, 03 Jun 2022 09:33:00 +0300
Paper TR22-084
| Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity |
Yanyi Liu,
Rafael Pass
https://eccc.weizmann.ac.il/report/2022/084A 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.Fri, 03 Jun 2022 09:33:00 +0300https://eccc.weizmann.ac.il/report/2022/084