Skip to main content
Added links on UP-generic oracles
Source Link
Joshua Grochow
  • 38.5k
  • 4
  • 134
  • 233

$\mathsf{UP} \neq \mathsf{EXP}$ is open. A UP-generic oracleoracle* 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)

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

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

added 23 characters in body
Source Link
Joshua Grochow
  • 38.5k
  • 4
  • 134
  • 233

$\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}$$\mathsf{UP} \subseteq \mathsf{\oplus P} \subseteq \mathsf{EXP}$ relative to any oracle, this should resolve 1.

$\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}$ relative to any oracle, this should resolve 1.

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

Source Link
Joshua Grochow
  • 38.5k
  • 4
  • 134
  • 233

$\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}$ relative to any oracle, this should resolve 1.