5
$\begingroup$

Heller (Theorem 6) gave an oracle relative to which $NP=EXP$, and Homer & Selman gave an oracle relative to which $P=UP$ and $\Sigma_2^P=EXP$.

Beigel, Buhrman, Fortnow (freely available author's version) gave an oracle in which $P=\oplus P$ and $NP=EXP$ holds.

  1. Is there an oracle that gives $P\neq UP=coUP=NP=coNP=\oplus P=EXP$?

  2. Is there an oracle that gives $P=UP=coUP\neq NP=coNP=\oplus P=EXP$?

Or is it known $UP\neq EXP$ unconditionally?

$\endgroup$
7
$\begingroup$

$\mathsf{UP} \neq \mathsf{EXP}$ is open. A UP-generic oracle* should make $\mathsf{P} \neq \mathsf{UP} = \mathsf{EXP}$, and since $\mathsf{UP} \subseteq \mathsf{\oplus P} \subseteq \mathsf{EXP}$ relative to any oracle, this should resolve 1. (I say "should" because I haven't checked all the details...)

*UP-generic oracles are discussed, for example, by Fenner-Fortnow-Kurtz-Li (author's freely available version) and also (shameless self plug) a quick tutorial in Section 5.1 here (author's free version)

$\endgroup$
  • $\begingroup$ Since your asnwer was earlier I will accept your answer. $\endgroup$ – Turbo Aug 8 '17 at 2:51
  • 1
    $\begingroup$ But what is an UP generic oracle? $\endgroup$ – Turbo Aug 8 '17 at 7:35
7
$\begingroup$

The quoted Beigel, Buhrman, and Fortnow paper gives a solution to 2 in Theorem 1.8: there is an oracle relative to which $\mathrm{P=Mod_3P}$ (which implies $\mathrm{P=UP}$), and $\mathrm{\oplus P=NP=EXP}$ (which, together with the first equality, actually implies $\mathrm{EXP=ZPP}$).

$\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.