3
$\begingroup$

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

$\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$ Jan 23 at 14:38
  • 1
    $\begingroup$ This also sounds like a good resource: cstheory.stackexchange.com/a/12366 $\endgroup$ Jan 23 at 14:45
  • 2
    $\begingroup$ @EmilJeřábek write these comments as answers! $\endgroup$
    – cody
    Jan 23 at 18:02

1 Answer 1

3
$\begingroup$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.