Definition
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 in a single operation. The problem can be of any complexity class, or it can even be an undecidable problem such as the halting problem. If another problem is reducible to in polynomial time, then the oracle machine can solve in polynomial time; one can say that is in the relativized complexity class . Other relativized complexity classes such as can be defined analogously.
Related concepts
A priori informationAbstract machineAlan TuringArithmetical hierarchyBenny ChorBinary relationBlack-box testingBlack boxBlack box groupBlackboxingBoolean satisfiability problemCharles H. Bennett (physicist)Christos PapadimitriouComplete (complexity)Complexity classComputability theoryComputational complexityComputational complexity theoryComputational problemControl systemCryptographic hash functionCryptographic protocolCryptographyDLOGTIMEDecision problemDemand oracleDeterministic Turing machineEgon BörgerFeed forward (control)Function problemGray-box testingHalting problemHartley Rogers, Jr.IP (complexity)Indicator functionInfinite setInteractive proof systemJohan HåstadJournal of Computer and System SciencesJuris HartmanisKolmogorov's zero–one lawLuca TrevisanMartin Davis (mathematician)Matroid oracleMichael SipserNP-completeNatural numberObfuscationOded GoldreichOpen system (systems theory)Operations researchOracle CorporationPSPACEP = NP problemPadding oracle attackPattern recognitionPolynomial hierarchyPolynomial timeProQuestProvable securityRandom oracleReduction (complexity)Robert I. SoareRobert M. SolovaySIAM Journal on ComputingSpace hierarchy theoremString (computer science)System identificationThermodynamic systemTime hierarchy theoremTuring machineTuring reductionUndecidable problemWhite-box testingWhite box (software engineering)
11 concepts already in your glossary