<p>Yes. Beigel CCC '89 showed $\mathsf{P} \neq \mathsf{UP} \neq \mathsf{NP}$ with probability 1. Combined with Rossman-Servedio-Tan, this gives the result you want. You should always try the <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#up" rel="noreferrer">Complexity Zoo</a> for questions like this...</p>

CC BY-SA 3.0
2018-01-03T03:35:25.867Z
2018-01-03T03:35:25.867Z
Joshua Grochow
<p>It is shown in <a href="https://arxiv.org/abs/1504.03398" rel="noreferrer">An average-case depth hierarchy theorem for Boolean circuits</a> a random oracle makes $PH$ infinite.</p>

<blockquote>
  <p>Is it possible to also show $UP\not=NP\not=\Sigma_2^P\not=\Sigma_3^P\not=\Sigma_4^P\not=\dots\not=PH\not=PSPACE$ with respect to a random oracle or does a random oracle give $UP=NP$?</p>
</blockquote>

<cc.complexity-theory><reference-request><oracles><polynomial-hierarchy><random-oracles>
Is $UP\not=NP$ with respect to random oracle?
Turbo
# Is $UP\not=NP$ with respect to random oracle?

(Asked by: username_0 on 2017-12-23)

It is shown in [An average-case depth hierarchy theorem for Boolean circuits](https://arxiv.org/abs/1504.03398) a random oracle makes $PH$ infinite.

> Is it possible to also show $UP\not=NP\not=\Sigma\_2^P\not=\Sigma\_3^P\not=\Sigma\_4^P\not=\dots\not=PH\not=PSPACE$ with respect to a random oracle or does a random oracle give $UP=NP$?

**Tags:** cc.complexity-theory, reference-request, oracles, polynomial-hierarchy, random-oracles

---

## 1 answers

### Answer by username_1 on 2018-01-03. Score: 8 | Accepted answer

Yes. Beigel CCC '89 showed $\mathsf{P} \neq \mathsf{UP} \neq \mathsf{NP}$ with probability 1. Combined with Rossman-Servedio-Tan, this gives the result you want. You should always try the [Complexity Zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#up) for questions like this...


---

