From Wikipedia, the free encyclopedia

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.

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 one for outputs.

The complexity class of decision problems solvable by an algorithm in class A with an oracle for a problem in class B is written A^B. For example, the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for a problem in NP is P^NP. (This is also the class of problems reducible by polynomial-time Turing reduction to a problem in NP.)

It is obvious that NP ⊆ P^NP, but the question of whether NP^NP, P^NP, NP, and P are equal remains open. See polynomial hierarchy for further extensions.

The notation A^B also means the class of problems solvable by an algorithm in class A with an oracle for the language B. For example, P^SAT is the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for the Boolean satisfiability problem. When language B is complete for some class C, then A^B=A^C. In particular, since SAT is NP-complete, P^SAT=P^NP. Note that this assumes that the machine used in the definition of the class A is powerful enough to execute the reductions used in the completeness definition of the class C; for example, if A = DSPACE(1), A^SAT does not necessarily equal A^NP.

Oracle machines are useful for investigating the relationship between complexity classes P and NP, by considering the relationship between P^A and NP^A for an oracle A. In particular, it has been shown that there exist languages A and B such that P^A=NP^A and P^B≠NP^B (Baker, Gill, Solovay, 1975). The fact that the P=NP question relativizes both ways is taken as evidence that answering this question will be difficult, because any proof technique that relativizes (i.e., is unaffected by the addition of an oracle) will not answer the P=NP question.

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, P^A≠NP^A (Bennett, Gill, 1981). 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 P≠NP. Unfortunately, a statement may be true for a random oracle and false for ordinary Turing machines at the same time; one notable example of this is the result that IP = PSPACE.^[1]

It is possible to posit the existence of an oracle which computes a non-computable function, such as the answer to the halting problem or some equivalent. A machine with an oracle of this sort is a hypercomputer.

Interestingly, the halting paradox still applies to such machines; that is, although they can determine whether particular Turing machines will halt on particular inputs, they cannot determine whether machines with equivalent halting oracles will themselves halt. This fact creates a hierarchy of machines, called the arithmetical hierarchy, each with a more powerful halting oracle and an even harder halting problem.

In cryptography, oracles are sometimes used to make arguments for the security of cryptographic protocols where (typically) a hash function is used. A security reduction for the protocol is given in the case where, instead of a hash function, a random oracle is used which answers each query randomly but consistently; the oracle is assumed to be available to all parties including the attacker, just as a hash function is. Such a proof shows that unless the attacker can solve the hard problem at the heart of the security reduction, they must make use of some interesting property of the hash function to break the protocol; they cannot treat the hash function as a black box (ie as a random oracle). This method has been very effective in giving good reductions for the security of efficient protocols, but its validity is sometimes challenged in the cryptographic community since computable functions are inherently very different from random oracles. See random oracle for more details.

1. Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
2. C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Section 14.3: Oracles, pp. 339 – 343.
3. T. P. Baker, J. Gill, R. Solovay. Relativizations of the P =? NP Question. SIAM Journal on Computing, 4(4): 431-442 (1975)
4. C. H. Bennett, J. Gill. Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1. SIAM Journal on Computing, 10(1): 96-113 (1981)
5. Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 9.2: Relativization, pp.318 – 321.
6. Martin Davis, editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. Turing's paper is in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.

1. ^ Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, Pankaj Rohatgi. The Random Oracle Hypothesis is False. Journal of Computer and System Sciences, volume 49, issue 1, pp.24–39. August 1994. ISSN 0022-0000. http://citeseer.ist.psu.edu/282397.html