Oracle machine

Black box systems
Concepts
Black box · Oracle machine
Methods and techniques

Black-box testing · Blackboxing


Related techniques
Feed forward · Obfuscation
Pattern recognition · White box
Fundamentals
Control systems · Open systems
Operations research
Thermodynamic systems
For computing machines sold by Oracle, see Oracle_Corporation#Hardware.

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.

Oracles

An oracle machine can be conceived as a Turing machine connected to an oracle. The oracle, in this context, is an entity capable of solving some problem, which for example may be a decision problem or a function problem. The problem does not have to be computable; the oracle is not assumed to be a Turing machine or computer program. The oracle is simply a "black box" that is able to produce a solution for any instance of a given computational problem:

An oracle machine can perform all of the usual operations of a Turing machine, and can also query the oracle to obtain a solution to any instance of the computational problem for that oracle. For example, if the problem is a decision problem for a set A of natural numbers, the oracle machine supplies the oracle with a natural number, and the oracle responds with "yes" or "no" stating whether that number is an element of A.

Definitions

There are many equivalent definitions of oracle Turing machines, as discussed below. The one presented here is from van Melkebeek (2000:43).

An oracle machine, like a Turing machine, includes:

In addition to these components, an oracle machine also includes:

From time to time, the oracle machine may enter the ASK state. When this happens, the following actions are performed in a single computational step:

The effect of changing to the ASK state is thus to receive, in a single step, a solution to the problem instance that is written on the oracle tape.

Alternative definitions

There are many alternative definitions to the one presented above. Many of these are specialized for the case where the oracle solves a decision problem. In this case:

These definitions are equivalent from the point of view of Turing computability: a function is oracle-computable from a given oracle under all of these definitions if it is oracle-computable under any of them. The definitions are not equivalent, however, from the point of view of computational complexity. A definition such as the one by van Melkebeek, using an oracle tape which may have its own alphabet, is required in general.

Complexity classes of oracle machines

The complexity class of decision problems solvable by an algorithm in class A with an oracle for a language L is called AL. For example, PSAT is the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for the Boolean satisfiability problem. The notation AB can be extended to a set of languages B (or a complexity class B), by using the following definition:

A^B = \bigcup_{L \in B} A^L

When a language L is complete for some class B, then AL=AB provided that machines in A can execute reductions used in the completeness definition of class B. In particular, since SAT is NP-complete with respect to polynomial time reductions, PSAT=PNP. However, if A = DLOGTIME, then ASAT may not equal ANP.

It is obvious that NP PNP, but the question of whether NPNP, PNP, NP, and P are equal remains tentative at best. It is believed they are different, and this leads to the definition of the polynomial hierarchy.

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

It is interesting to consider the case where an oracle is chosen randomly from among all possible oracles (an infinite set). It has been shown in this case, that with probability 1, PANPA (Bennett and Gill 1981). When a question is true for almost all oracles, it is said to be true for a random oracle. This choice of terminology is justified by the fact random oracles support a statement with probability 0 or 1 only. (This follows from Kolmogorov's zero one law.) This is taken as evidence PNP. A statement may be true for a random oracle and false for ordinary Turing machines at the same time; for example, for a random oracle A, IPAPSPACEA, but without an oracle, IP = PSPACE (Chang et al., 1994).

Oracles and halting problems

A machine with an oracle for the halting problem can determine whether particular Turing machines will halt on particular inputs, but they cannot determine, in general, if machines equivalent to themselves will halt. This creates a hierarchy of machines, each with a more powerful halting oracle and an even harder halting problem. This hierarchy of machines can be used to define the arithmetical hierarchy (Börger 1989).

Applications to cryptography

Main article: Random oracle

In cryptography, oracles are used to make arguments for the security of cryptographic protocols where 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 answers each query randomly but consistently; the oracle is assumed to be available to all parties including the attacker, as the hash function is. Such a proof shows that unless the attacker solves 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 (i.e., as a random oracle).

See also

References

This article is issued from Wikipedia - version of the Monday, December 14, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.