$NP^{PP} vs. PP^{NP}$, which one subsumes the other?

219 Views Asked by At

I understand why P with an NP oracle ($P^{NP}$) subsumes $NP$: because it contains co-NP. But how about NP with a P oracle? Can it be any different from NP? (I'm guessing they are the same otherwise $NP^P$ would've appeared in the polynomial hierarchy)

Going further, How does it all stand with class PP (probabilistic polynomial time) assuming the polynomial hierarchy does not collapse?

  • $PP^{NP} = PP$?
  • $P^{PP} = PP$?
  • $NP^{PP} vs. PP^{NP}$, which one subsumes the other?

Any reasoning (intuition) as to why this does (not) hold?

1

There are 1 best solutions below

2
On

Since $P \subseteq NP$, $NP^P = NP$.

Nondeterministic programs are an extension of deterministic programs. They are just programs with a jump-and-branch command added. So every deterministic program is also a nondeterminnistic program that doesn't use jump-and-branch, so adding the oracle gives no additional computability.