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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Since your asnwer was earlier I will accept your answer. $\endgroup$
    – Turbo
    Commented Aug 8, 2017 at 2:51
  • 1
    $\begingroup$ But what is an UP generic oracle? $\endgroup$
    – Turbo
    Commented Aug 8, 2017 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}$).

Improve this answer
$\endgroup$
1
  • $\begingroup$ In this case can it also hold $P\neq P^{UP}=NP$? $\endgroup$
    – Turbo
    Commented Dec 5, 2020 at 18:44

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.