Is there a containment between $\mathsf{ZPP}$ and $\mathsf{UP}$?

Question

Do we know if $\mathsf{ZPP}\subseteq\mathsf{UP}$ known or is there oracles against the hypothesis?

Answer 1

There is an oracle $\mathcal O$ such that $\textsf{ZPP}^{\mathcal O}\not\subseteq \textsf{UP}^{\mathcal O}$. The inclusion is not known, and it would therefore require non-relativizing techniques to resolve the question (and probably even non-algebrizing techniques). On the other hand, the inclusion $\textsf{ZPP}\subseteq \textsf{UP}$ is conjectured to be true, because the Derandomization Hypothesis implies $\textsf{P}=\textsf{ZPP}=\textsf{BPP}$, and since $\textsf{P}\subseteq \textsf{UP}$, we get $\textsf{ZPP}\subseteq \textsf{UP}$.

Oracle sketch. The oracle $\mathcal O$ is constructed in phases. For the $n$-th phase, we fix the strings in $\mathcal O\cap \{0,1\}^n$. For a yes-input, we take a random subset $S\subseteq \{0,1\}^{n-1}$, and set $\mathcal O\cap\{0,1\}^n:=0S$. For a no-input, we set $\mathcal O\cap\{0,1\}^n:=1S$.

The language $\mathcal L$ which now has $\mathcal L\in \textsf{ZPP}^{\mathcal O}\setminus \textsf{UP}^{\mathcal O}$ asks the question: on input $1^n$, is it true that (1) $|\mathcal L\cap 0\{0,1\}^{n-1}|>\frac{1}{4}2^{n}$, and (2) not $|\mathcal L\cap 1\{0,1\}^{n-1}|>\frac{1}{4}2^n$? Because of the way we constructed the oracle, for any $n$ we always have either both (1) and (2) are true, or neither (1) nor (2), so it suffices for an $\textsf{RP}$ algorithm to check whether (1) holds, and for a $\textsf{co-RP}$ algorithm to check whether (2) holds. Hence $\mathcal L\in \textsf{RP}^{\mathcal O}\cap \textsf{co-RP}^{\mathcal O}=\textsf{ZPP}^{\mathcal O}$.

The details of diagonalizing against all $\textsf{UP}$-Turing Machines are omitted, but are standard.