Oracle machine

From Wikipedia

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

In complexity theory, an oracle is a black box that computes a function in a single step. This could be a complicated function like subset sum. It could even be an uncomputable function like the halting problem.

An oracle machine is a Turing machine connected to an oracle. The Turing machine can write on its own tape an input for the oracle, then tell the oracle to execute. In a single step, the oracle computes its function, erases its input, and writes its output to the tape. Sometimes the Turing machine is described as having two tapes, one of which is reserved for oracle inputs and outputs.

Clearly, for some oracles, the oracle machine will be more powerful than a simple Turing machine. It is possible to define complexity classes analagous to P and NP for this machine. This can be useful for investigating the relationship between P and NP.

For an oracle A, the corresponding classes are called PA and NPA. It has been shown that there exist oracles A and B such that PA=NPA and PBNPB. When a question such as this has different answers for different oracles, it is said to "relativize both ways". The fact that the P=NP question relativizes both ways is taken as evidence that answering this question will be difficult.

It is interesting to consider the case where an oracle is chosen randomly from among all possible oracles. It has been shown that if oracle A is chosen randomly, then with probability 1, PANPA. When a question is true for almost all oracles, it is said to be true "for a random oracle". This is sometimes taken as evidence that PNP. Unfortunately, it is possible for some statement to be true for a random oracle, but not be true for ordinary Turing machines.