Oracle machine

In complexity theory and computability theory, an oracle machine is an abstract machine that can query a black box called an oracle, which is able to give an answer to any instance of a certain problem ⁠${\displaystyle R}$⁠ in a single operation. The problem ⁠${\displaystyle R}$⁠ can be of any complexity class, or it can even be an undecidable problem such as the halting problem. If another problem ⁠${\displaystyle R'}$⁠ is reducible to ⁠${\displaystyle R}$⁠ in polynomial time, then the oracle machine (with the ⁠${\displaystyle R}$⁠-oracle) can solve ⁠${\displaystyle R'}$⁠ in polynomial time; one can say that ⁠${\displaystyle R'}$⁠ is in the relativized complexity class ⁠${\displaystyle {\mathsf {P}}^{R}}$⁠. Other relativized complexity classes such as ⁠${\displaystyle {\mathsf {NP}}^{R}}$⁠ can be defined analogously.