HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Do we know if there is an oracle $B$ so that $P^B \neq NP^B$ but $coNP^B=NP^B$?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
conpknowneqbutthatoraclethere

Problem

We know there is $B$ with $P^B \neq NP^B$, and we know there is $C$ with $coNP^C=NP^C$, what happens if we want to mix?

Solution

Any oracle relative to which $\mathsf{NP=EXP}$ would do the trick. You can find a construction of such an oracle in Heller's paper. Clearly if $\mathsf{NP=EXP}$ then $\mathsf{NP=coNP=EXP}$ but $\mathsf{P\neq NP}$ by the time hierarchy theorem.

I don't know whether there are known oracle constructions who collapse the hierarchy to $\Sigma_i$ and not to $\Sigma_{i-1}$, but it's an interesting question (I would guess the answer is in the affirmative).

Context

StackExchange Computer Science Q#85160, answer score: 2

Revisions (0)

No revisions yet.