<p>$\mathsf{UP} \neq \mathsf{EXP}$ is open. A UP-generic oracle* should make $\mathsf{P} \neq \mathsf{UP} = \mathsf{EXP}$, and since $\mathsf{UP} \subseteq \mathsf{\oplus P} \subseteq \mathsf{EXP}$ relative to any oracle, this should resolve 1. (I say "should" because I haven't checked all the details...)</p>

<p>*UP-generic oracles are discussed, for example, by <a href="https://doi.org/10.1016/S0890-5401(03)00018-X" rel="nofollow noreferrer">Fenner-Fortnow-Kurtz-Li</a> (<a href="http://papers.fortnow.com/files/obt.pdf" rel="nofollow noreferrer">author's freely available version</a>) and also (shameless self plug) a quick tutorial in Section 5.1 <a href="http://doi.org/10.1016/j.ic.2011.01.006" rel="nofollow noreferrer">here</a> (<a href="http://lance.fortnow.com/papers/files/equiv.pdf" rel="nofollow noreferrer">author's free version</a>)</p>

CC BY-SA 3.0
2017-08-08T02:51:30.030Z
Since your asnwer was earlier I will accept your answer.
Turbo
CC BY-SA 3.0
2017-08-08T07:35:27.510Z
But what is an UP generic oracle?
Turbo
CC BY-SA 3.0
2017-08-07T16:41:11.783Z
2017-08-08T17:56:23.683Z
2017-08-08T17:56:23.683Z
Joshua Grochow
<p>The quoted Beigel, Buhrman, and Fortnow paper gives a solution to 2 in Theorem 1.8: there is an oracle relative to which $\mathrm{P=Mod_3P}$ (which implies $\mathrm{P=UP}$), and $\mathrm{\oplus P=NP=EXP}$ (which, together with the first equality, actually implies $\mathrm{EXP=ZPP}$).</p>

CC BY-SA 4.0
2020-12-05T18:44:30.587Z
In this case can it also hold $P\neq P^{UP}=NP$?
Turbo
CC BY-SA 3.0
2017-08-07T17:12:23.170Z
2017-08-07T17:12:23.170Z
Emil Jeřábek
<p><a href="http://dx.doi.org/10.1137/0213045" rel="noreferrer">Heller</a> (Theorem 6) gave an oracle relative to which <span class="math-container">$NP=EXP$</span>, and <a href="https://doi.org/10.1016/0022-0000(92)90023-C" rel="noreferrer">Homer &amp; Selman</a> gave an oracle relative to which <span class="math-container">$P=UP$</span> and <span class="math-container">$\Sigma_2^P=EXP$</span>.</p>
<p><a href="http://doi.org/10.1145/276698.276737" rel="noreferrer">Beigel, Buhrman, Fortnow</a> (<a href="http://papers.fortnow.com/files/newiso.pdf" rel="noreferrer">freely available author's version</a>) gave an oracle in which <span class="math-container">$P=\oplus P$</span> and <span class="math-container">$NP=EXP$</span> holds.</p>
<blockquote>
<ol>
<li><p>Is there an oracle that gives <span class="math-container">$P\neq UP=coUP=NP=coNP=\oplus P=EXP$</span>?</p>
</li>
<li><p>Is there an oracle that gives <span class="math-container">$P=UP=coUP\neq NP=coNP=\oplus P=EXP$</span>?</p>
</li>
</ol>
</blockquote>
<p>Or is it known <span class="math-container">$UP\neq EXP$</span> unconditionally?</p>

<cc.complexity-theory><complexity-classes><oracles><exp-time-algorithms><relativization>
Oracle comparing $EXP$ with $UP$
Turbo
# Oracle comparing $EXP$ with $UP$

(Asked by: username_0 on 2017-08-07)

[Heller](http://dx.doi.org/10.1137/0213045) (Theorem 6) gave an oracle relative to which $NP=EXP$, and [Homer & Selman](https://doi.org/10.1016/0022-0000(92)90023-C) gave an oracle relative to which $P=UP$ and $\Sigma\_2^P=EXP$.

[Beigel, Buhrman, Fortnow](http://doi.org/10.1145/276698.276737) ([freely available author's version](http://papers.fortnow.com/files/newiso.pdf)) gave an oracle in which $P=\oplus P$ and $NP=EXP$ holds.

> 1. Is there an oracle that gives $P\neq UP=coUP=NP=coNP=\oplus P=EXP$?
> 2. Is there an oracle that gives $P=UP=coUP\neq NP=coNP=\oplus P=EXP$?

Or is it known $UP\neq EXP$ unconditionally?

**Tags:** cc.complexity-theory, complexity-classes, oracles, exp-time-algorithms, relativization

---

## 2 answers

### Answer by username_1 on 2017-08-07. Score: 7 | Accepted answer

$\mathsf{UP} \neq \mathsf{EXP}$ is open. A UP-generic oracle\* should make $\mathsf{P} \neq \mathsf{UP} = \mathsf{EXP}$, and since $\mathsf{UP} \subseteq \mathsf{\oplus P} \subseteq \mathsf{EXP}$ relative to any oracle, this should resolve 1. (I say "should" because I haven't checked all the details...)

\*UP-generic oracles are discussed, for example, by [Fenner-Fortnow-Kurtz-Li](https://doi.org/10.1016/S0890-5401(03)00018-X) ([author's freely available version](http://papers.fortnow.com/files/obt.pdf)) and also (shameless self plug) a quick tutorial in Section 5.1 [here](http://doi.org/10.1016/j.ic.2011.01.006) ([author's free version](http://lance.fortnow.com/papers/files/equiv.pdf))

> **Comments:**
> **username_0**: Since your asnwer was earlier I will accept your answer.  
> **username_0**: But what is an UP generic oracle?  

---

### Answer by username_2 on 2017-08-07. Score: 7

The quoted Beigel, Buhrman, and Fortnow paper gives a solution to 2 in Theorem 1.8: there is an oracle relative to which $\mathrm{P=Mod\_3P}$ (which implies $\mathrm{P=UP}$), and $\mathrm{\oplus P=NP=EXP}$ (which, together with the first equality, actually implies $\mathrm{EXP=ZPP}$).

> **Comments:**
> **username_0**: In this case can it also hold $P\neq P^{UP}=NP$?  

---

