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?
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.