patternMinor
Under what kind of oracles are $P$ and $NP$ equivalent?
Viewed 0 times
equivalentwhatarekindunderoraclesand
Problem
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.
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.
Solution
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!
-
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!
Context
StackExchange Computer Science Q#126163, answer score: 5
Revisions (0)
No revisions yet.