Do we know of an oracle relative to which P ≠ NP but NP = coNP?
$\begingroup$
$\endgroup$
3
-
4$\begingroup$ 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. $\endgroup$– Emil JeřábekJan 23 at 14:38
-
1$\begingroup$ This also sounds like a good resource: cstheory.stackexchange.com/a/12366 $\endgroup$– Emil JeřábekJan 23 at 14:45
-
2$\begingroup$ @EmilJeřábek write these comments as answers! $\endgroup$– codyJan 23 at 18:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
