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 R in a single operation. The problem R can be of any complexity class, or it can even be an undecidable problem such as the halting problem. If another problem R′ is reducible to R in polynomial time, then the oracle machine (with the R-oracle) can solve R′ in polynomial time; one can say that R′ is in the relativized complexity class 𝖯R. Other relativized complexity classes such as 𝖭𝖯R can be defined analogously.
Wikipedia contributors, "Oracle machine", Wikipedia, revision 1367962950, retrieved 20 November 2026, source, CC BY-SA 4.0.