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

  • $\begingroup$ 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. $\endgroup$ – Mohsen Ghorbani Jan 27 at 10:09
  • 4
    $\begingroup$ @MohsenGhorbani $\mathsf{ZPP}\subseteq\mathsf{coRP}\subseteq\mathsf{coNP}\subseteq\mathsf{US}$ but where does $\mathsf{UP}$ come in? $\endgroup$ – 1.. Jan 27 at 10:15
  • 1
    $\begingroup$ I thought UP = US‌. $\endgroup$ – Mohsen Ghorbani 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.

  • $\begingroup$ @LieuweVinkhujzen Can you provide a reference for 'standard'? $\endgroup$ – 1.. Jan 31 at 11:04
  • $\begingroup$ @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. $\endgroup$ – Lieuwe Vinkhuijzen Jan 31 at 11:33
  • $\begingroup$ I meant 'The details of diagonalizing against all'. What does it imply in the context in oracles? $\endgroup$ – 1.. Jan 31 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.