<p>There is an oracle <span class="math-container">$\mathcal O$</span> such that <span class="math-container">$\textsf{ZPP}^{\mathcal O}\not\subseteq \textsf{UP}^{\mathcal O}$</span>. 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 <span class="math-container">$\textsf{ZPP}\subseteq \textsf{UP}$</span> is <em>conjectured</em> to be true, because the Derandomization Hypothesis implies <span class="math-container">$\textsf{P}=\textsf{ZPP}=\textsf{BPP}$</span>, and since <span class="math-container">$\textsf{P}\subseteq \textsf{UP}$</span>, we get <span class="math-container">$\textsf{ZPP}\subseteq \textsf{UP}$</span>.</p>
<p><strong>Oracle sketch.</strong> The oracle <span class="math-container">$\mathcal O$</span> is constructed in phases. For the <span class="math-container">$n$</span>-th phase, we fix the strings in <span class="math-container">$\mathcal O\cap \{0,1\}^n$</span>. For a yes-input, we take a random subset <span class="math-container">$S\subseteq \{0,1\}^{n-1}$</span>, and set <span class="math-container">$\mathcal O\cap\{0,1\}^n:=0S$</span>. For a no-input, we set <span class="math-container">$\mathcal O\cap\{0,1\}^n:=1S$</span>.</p>
<p>The language <span class="math-container">$\mathcal L$</span> which now has <span class="math-container">$\mathcal L\in \textsf{ZPP}^{\mathcal O}\setminus \textsf{UP}^{\mathcal O}$</span> asks the question: on input <span class="math-container">$1^n$</span>, is it true that (1) <span class="math-container">$|\mathcal L\cap 0\{0,1\}^{n-1}|&gt;\frac{1}{4}2^{n}$</span>, and (2) not <span class="math-container">$|\mathcal L\cap 1\{0,1\}^{n-1}|&gt;\frac{1}{4}2^n$</span>? Because of the way we constructed the oracle, for any <span class="math-container">$n$</span> we always have either both (1) and (2) are true, or neither (1) nor (2), so it suffices for an <span class="math-container">$\textsf{RP}$</span> algorithm to check whether (1) holds, and for a <span class="math-container">$\textsf{co-RP}$</span> algorithm to check whether (2) holds. Hence <span class="math-container">$\mathcal L\in \textsf{RP}^{\mathcal O}\cap \textsf{co-RP}^{\mathcal O}=\textsf{ZPP}^{\mathcal O}$</span>.</p>
<p>The details of diagonalizing against all <span class="math-container">$\textsf{UP}$</span>-Turing Machines are omitted, but are standard.</p>

CC BY-SA 4.0
2021-01-31T11:04:18.990Z
@LieuweVinkhujzen Can you provide a reference for 'standard'?
Turbo
CC BY-SA 4.0
2021-01-31T11:33:47.440Z
@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.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2021-01-31T12:10:25.400Z
I meant 'The details of diagonalizing against all'. What does it imply in the context in oracles?
Turbo
CC BY-SA 4.0
2021-01-31T11:02:43.397Z
2021-01-31T11:02:43.397Z
Lieuwe Vinkhuijzen
<p>Do we know if <span class="math-container">$\mathsf{ZPP}\subseteq\mathsf{UP}$</span> known or is there oracles against the hypothesis?</p>

CC BY-SA 4.0
2021-01-27T10:09:18.503Z
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.
Mohsen Ghorbani
CC BY-SA 4.0
2021-01-27T10:15:59.747Z
@MohsenGhorbani $\mathsf{ZPP}\subseteq\mathsf{coRP}\subseteq\mathsf{coNP}\subseteq\mathsf{US}$ but where does $\mathsf{UP}$ come in?
Turbo
CC BY-SA 4.0
2021-01-27T10:19:58.333Z
I thought UP = US‌.
Mohsen Ghorbani
<cc.complexity-theory><complexity-classes>
Is there a containment between $\mathsf{ZPP}$ and $\mathsf{UP}$?
Turbo
# Is there a containment between $\mathsf{ZPP}$ and $\mathsf{UP}$?

(Asked by: username_0 on 2021-01-27)

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

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: 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.  
> **username_0**: @MohsenGhorbani $\mathsf{ZPP}\subseteq\mathsf{coRP}\subseteq\mathsf{coNP}\subseteq\mathsf{US}$ but where does $\mathsf{UP}$ come in?  
> **username_1**: I thought UP = US‌.  

---

## 1 answers

### Answer by username_2 on 2021-01-31. Score: 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.

> **Comments:**
> **username_0**: @LieuweVinkhujzen Can you provide a reference for 'standard'?  
> **username_2**: @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.  
> **username_0**: I meant 'The details of diagonalizing against all'. What does it imply in the context in oracles?  

---

