Oracle machine

Abstract machine used to study decision problems

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 ⁠ R {\displaystyle R} ⁠ in a single operation. The problem ⁠ R {\displaystyle R} ⁠ can be of any complexity class, or it can even be an undecidable problem such as the halting problem. If another problem ⁠ R ′ {\displaystyle R'} ⁠ is reducible to ⁠ R {\displaystyle R} ⁠ in polynomial time, then the oracle machine (with the ⁠ R {\displaystyle R} ⁠-oracle) can solve ⁠ R ′ {\displaystyle R'} ⁠ in polynomial time; one can say that ⁠ R ′ {\displaystyle R'} ⁠ is in the relativized complexity class ⁠ P R {\displaystyle {\mathsf {P}}^{R}} ⁠.

From Wikipedia, under CC BY-SA. More on occurri.