<p>Some oracles of this sort were given in other answers on this site:</p>
<ul>
<li><p><a href="https://cstheory.stackexchange.com/a/1545">https://cstheory.stackexchange.com/a/1545</a> gives references to an oracle <span class="math-container">$A$</span> such that <span class="math-container">$\mathrm{EXP}^A=\mathrm{NP}^A=\mathrm{ZPP}^A$</span>.</p>
</li>
<li><p><a href="https://cstheory.stackexchange.com/a/38765">https://cstheory.stackexchange.com/a/38765</a> gives a reference to an oracle <span class="math-container">$A$</span> such that <span class="math-container">$\mathrm{EXP}^A=\oplus\mathrm P^A=\mathrm{NP}^A=\mathrm{ZPP}^A$</span> and <span class="math-container">$\oplus_3\mathrm P^A=\mathrm P^A$</span>.</p>
</li>
</ul>
<p>Note that <span class="math-container">$\mathrm{EXP}^A=\mathrm{NP}^A$</span> implies <span class="math-container">$\mathrm{NP}^A=\mathrm{coNP}^A$</span> and <span class="math-container">$\mathrm P^A\ne\mathrm{NP}^A$</span> by the relativized time-hierarchy theorem.</p>
<p>Furthemore, <a href="https://cstheory.stackexchange.com/a/12366">https://cstheory.stackexchange.com/a/12366</a> gives a reference to a paper that lists many oracle separations between the most common classes.</p>

CC BY-SA 4.0
2023-01-24T12:09:04.957Z
2023-01-24T12:09:04.957Z
Emil Jeřábek
<p>Do we know of an oracle relative to which P ≠ NP but NP = coNP?</p>

CC BY-SA 4.0
2023-01-23T14:38:44.280Z
Sure. There are even oracles $A$ such that $\mathrm{EXP}^A=\mathrm{NP}^A$; this implies $\mathrm{NP}^A=\mathrm{coNP}^A$ as $\mathrm{EXP}^A$ is closed under complement, and $\mathrm P^A\ne\mathrm{NP}^A$ on pain of contradicting the relativized time-hierarchy theorem. One such oracle (further satisfying $\mathrm{EXP}^A=\mathrm{ZPP}^A$) is referenced in https://cstheory.stackexchange.com/a/1545; another (satisfying $\mathrm{EXP}^A=\mathrm{NP}^A=\oplus\mathrm P^A=\mathrm{ZPP}^A$ and $\mathrm{Mod_3P}^A=\mathrm P^A$) is referenced in https://cstheory.stackexchange.com/a/38765.
Emil Jeřábek
CC BY-SA 4.0
2023-01-23T14:45:55.803Z
This also sounds like a good resource: https://cstheory.stackexchange.com/a/12366
Emil Jeřábek
CC BY-SA 4.0
2023-01-23T18:02:23.730Z
@EmilJeřábek write these comments as answers!
cody
<complexity-classes><oracles><relativization>
Relativized world in which P ≠ NP = coNP
Noel Arteche
# Relativized world in which P ≠ NP = coNP

(Asked by: username_0 on 2023-01-23)

Do we know of an oracle relative to which P ≠ NP but NP = coNP?

**Tags:** complexity-classes, oracles, relativization
> **Comments:**
> **username_1**: Sure. There are even oracles $A$ such that $\mathrm{EXP}^A=\mathrm{NP}^A$; this implies $\mathrm{NP}^A=\mathrm{coNP}^A$ as $\mathrm{EXP}^A$ is closed under complement, and $\mathrm P^A\ne\mathrm{NP}^A$ on pain of contradicting the relativized time-hierarchy theorem. One such oracle (further satisfying $\mathrm{EXP}^A=\mathrm{ZPP}^A$) is referenced in https://cstheory.stackexchange.com/a/1545; another (satisfying $\mathrm{EXP}^A=\mathrm{NP}^A=\oplus\mathrm P^A=\mathrm{ZPP}^A$ and $\mathrm{Mod_3P}^A=\mathrm P^A$) is referenced in https://cstheory.stackexchange.com/a/38765.  
> **username_1**: This also sounds like a good resource: https://cstheory.stackexchange.com/a/12366  
> **username_2**: @EmilJeřábek write these comments as answers!  

---

## 1 answers

### Answer by username_1 on 2023-01-24. Score: 5 | Accepted answer

Some oracles of this sort were given in other answers on this site:

* <https://cstheory.stackexchange.com/a/1545> gives references to an oracle $A$ such that $\mathrm{EXP}^A=\mathrm{NP}^A=\mathrm{ZPP}^A$.
* <https://cstheory.stackexchange.com/a/38765> gives a reference to an oracle $A$ such that $\mathrm{EXP}^A=\oplus\mathrm P^A=\mathrm{NP}^A=\mathrm{ZPP}^A$ and $\oplus\_3\mathrm P^A=\mathrm P^A$.

Note that $\mathrm{EXP}^A=\mathrm{NP}^A$ implies $\mathrm{NP}^A=\mathrm{coNP}^A$ and $\mathrm P^A\ne\mathrm{NP}^A$ by the relativized time-hierarchy theorem.

Furthemore, <https://cstheory.stackexchange.com/a/12366> gives a reference to a paper that lists many oracle separations between the most common classes.


---

