How strong have the oracles needed to be for these two classes to be proven equivalent with respect to them?

For instance: is $P^H$ = $NP^H$ (ie. is $P$ equipped with an oracle to solve the halting problem equivalent to $NP$ equipped with an oracle to solve the halting problem)?

From Theodore Baker, John Gill, and Robert Solovay. Relativization of the P=?NP problem. Siam Journal of Computing, 4:432-442, 1975 [219] we know $NP^A =P^A$ for their oracle A (which is a decision algorithm for a PSPACE complete problem).

If the oracle can perform an infinite amount of computation and return back the result in one step are these classes equal with respect to an oracle of this type? How about weaker ones? What is the weakest oracle we know of where $P$ and $NP$ are equal with respect to it?

An answer I'm looking for is something like: $P^O$=$NP^O$ with respect to an oracle O and any oracle more powerful than it.


1 Answer 1


It's not about strength: the Baker-Gill-Solovay nonrelativization result relativizes (hehehe), in the sense that

  • for every $A$ there is a $B\ge_p A$ such that $\mathsf{P}^B\not=\mathsf{NP}^B$, and

  • for every $A$ there is a $B\ge_p A$ such that $\mathsf{P}^B=\mathsf{NP}^B$.

What matters more - or at least, what matters more in a way we can understand - is the genericity/randomness properties of the oracle. Specifically, the set of oracles with respect to which $\mathsf{P}\not=\mathsf{NP}$ has full measure, which is to say that $\mathsf{P}^A\not=\mathsf{NP}^A$ whenever $A$ is "sufficiently random." If I recall correctly, the same is true for genericity: the set of oracles with respect to which $\mathsf{P}\not=\mathsf{NP}$ is comeager, which is to say that $\mathsf{P}^A\not=\mathsf{NP}^A$ whenever $A$ is "sufficiently generic." Both of these notions can be made precise. For a concrete example, Chaitin's constant and its relativizations are sufficiently random to separate $\mathsf{P}$ and $\mathsf{NP}$.

So what about the halting problem specifically? Well, the exact structure of the halting problem is rather dependent on the way we choose to enumerate Turing machines, and we can in fact whip up an "appropriate" enumeration whose associated halting problem goes whichever way we desire. So I suspect that it's hard to say anything here.

This leaves open the question of how weak we can make an oracle with respect to which we have $\mathsf{P}=\mathsf{NP}$ (or $\mathsf{P}\not=\mathsf{NP}$ for that matter). The Baker-Gill-Solovay argument gives us the non-highness result that for any non-polytime-computable $A$ we can find $B,C$ to which $A$ is not polytime-reduciblesuch that $\mathsf{P}^B=\mathsf{NP}^B$ and $\mathsf{P}^C\not=\mathsf{NP}^C$. (Incidentally, note that "high" and "low" are technical terms which I'm misusing here. I'm rude like that.)

Now the above isn't as satisfying as one might hope since the $\le_p$-degrees are rather "spread out." We might hope for some results "closer to home." For example, in an earlier edit I suggested examining the behavior of minimal degrees with respect to polynomial-time $m$-reducibility, where "minimal" means "nonzero but not strictly above any nonzero degree" (while this clashes with the standard order-theoretic meaning, it is standard in computability theory). I just realized that this is vacuous: there are no minimal polynomial-time degrees, with respect to either $m$- or $T$-reductions, at all! This was proved by Homer, following a result of Ladner.

Just to wrap up this coda, Homer subsequently observed (and this was followed up by Ambos-Spies) that things are less trivial with respect to so-called honest reductions; honesty is a bit technical, but the basic idea is to rule out situations where disproportionately much of the information about a set is concentrated in a small region of the oracle computing it. It turns out that there is a tentative connection between minimal degrees with respect to honest polynomial reductions and the $\mathsf{P=NP}$-problem. To my understanding this turned out to be a red herring, but it's still very neat!

  • $\begingroup$ Thank you! do you have any references for reading about genericity/randomness of oracles in relation to P and NP? $\endgroup$
    – DeeDee
    May 23, 2020 at 18:28
  • $\begingroup$ Not really, sadly, I picked this stuff up in classes. Maybe Arora/Barak says something about it? $\endgroup$ May 23, 2020 at 18:59
  • $\begingroup$ The minimal polytime degree is zero for one of P=NP and P≠NP... $\endgroup$ May 24, 2020 at 12:03
  • $\begingroup$ @YuvalFilmus I'm using the phrase "minimal degree" in the sense of computability theory (the following sentence is "Recall that a degree is minimal if it is nonzero but does not lie above any other nonzero degree"). This is really annoying usage, but it is standard there. $\endgroup$ May 24, 2020 at 13:52
  • 2
    $\begingroup$ @YuvalFilmus Coming back to this much later, it turns out that there are no minimal degrees with respect to polynomial time reductions, either $m$- or $T$-flavored, at all! Things get more complicated when we modify the notion of reducibility. $\endgroup$ Feb 15, 2021 at 1:41

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.