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

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

• It is correct. We know that $CoRP \subset UP$ because unique-Sat is Conp-hard and we know the fact that RP is in NP so $ZPP = RP \cap coRP$ is in UP because it is closed under complement. Jan 27 at 10:09
• @MohsenGhorbani $\mathsf{ZPP}\subseteq\mathsf{coRP}\subseteq\mathsf{coNP}\subseteq\mathsf{US}$ but where does $\mathsf{UP}$ come in?
– Mr.
Jan 27 at 10:15
• I thought UP = US‌. Jan 27 at 10:19

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.

• @LieuweVinkhujzen Can you provide a reference for 'standard'?
– Mr.
Jan 31 at 11:04
• @1.. A good reference is Computational Complexity: A Modern Approach, Chapter 3, by Arora & Barak. Second, if you have the time, the discovery of NP-Intermediate problems by Richard Ladner is instructive: On the structure of polynomial-time reducibility. For a good modern background, you can read the first few pages of Algebrization: A new barrier in Complexity Theory by Scott Aaronson and Avi Widgerson. Jan 31 at 11:33
• I meant 'The details of diagonalizing against all'. What does it imply in the context in oracles?
– Mr.
Jan 31 at 12:10