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

1 Answer 1

5
$\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 and acknowledge you have read our privacy policy.

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