# Relativized world in which P ≠ NP = coNP

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

• 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 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 cstheory.stackexchange.com/a/38765. Commented Jan 23, 2023 at 14:38
• This also sounds like a good resource: cstheory.stackexchange.com/a/12366 Commented Jan 23, 2023 at 14:45
– cody
Commented Jan 23, 2023 at 18:02

• 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.