Oracle machine
| Black box systems | |
|---|---|
 | |
| System | |
| Black box, Oracle machine | |
| Methods and techniques | |
| Black-box testing, Blackboxing | |
| Related techniques | |
| Feed forward, Obfuscation, Pattern recognition, White box, White-box testing, Gray-box testing, System identification | |
| Fundamentals | |
| A priori information, Control systems, Open systems, Operations research, Thermodynamic systems | |
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 (with the -oracle) 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.
