Oracle machine

Black box systems
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
	v ; t ; e ;

Last updated January 19, 2024

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 solve certain problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as 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:

A decision problem is represented as a set A of natural numbers (or strings). An instance of the problem is an arbitrary natural number (or string). The solution to the instance is "YES" if the number (string) is in the set, and "NO" otherwise.
A function problem is represented by a function f from natural numbers (or strings) to natural numbers (or strings). An instance of the problem is an input x for f. The solution is the value f(x).

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 (2003 , p. 43).

An oracle machine, like a Turing machine, includes:

a work tape: a sequence of cells without beginning or end, each of which may contain a B (for blank) or a symbol from the tape alphabet;
a read/write head, which rests on a single cell of the work tape and can read the data there, write new data, and increment or decrement its position along the tape;
a control mechanism, which can be in one of a finite number of states, and which will perform different actions (reading data, writing data, moving the control mechanism, and changing states) depending on the current state and the data being read.

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

an oracle tape, which is a semi-infinite tape separate from the work tape. The alphabet for the oracle tape may be different from the alphabet for the work tape.
an oracle head which, like the read/write head, can move left or right along the oracle tape reading and writing symbols;
two special states: the ASK state and the RESPONSE state.

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 contents of the oracle tape are viewed as an instance of the oracle's computational problem;
the oracle is consulted, and the contents of the oracle tape are replaced with the solution to that instance of the problem;
the oracle head is moved to the first square on the oracle tape;
the state of the oracle machine is changed to RESPONSE.

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:

Some definitions, instead of writing the answer to the oracle tape, have two special states YES and NO in addition to the ASK state. When the oracle is consulted, the next state is chosen to be YES if the contents of the oracle tape are in the oracle set, and chosen to the NO if the contents are not in the oracle set.^[1]
Some definitions eschew the separate oracle tape. When the oracle state is entered, a tape symbol is specified. The oracle is queried with the number of times that this tape symbol appears on the work tape. If that number is in the oracle set, the next state is the YES state; if it is not, the next state is the NO state.^[2]
Another alternative definition makes the oracle tape read-only, and eliminates the ASK and RESPONSE states entirely. Before the machine is started, the indicator function of the oracle set is written on the oracle tape using symbols 0 and 1. The machine is then able to query the oracle by scanning to the correct square on the oracle tape and reading the value located there.^[3]

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 A^L. 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. The notation A^B 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 A^L=A^B 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, P^SAT=P^NP. However, if A = DLOGTIME, then A^SAT may not equal A^NP. (The definition of $A^{B}$ given above is not completely standard. In some contexts, such as the proof of the time and space hierarchy theorems, it is more useful to assume that the abstract machine defining class $A$ only has access to a single oracle for one language. In this context, $A^{B}$ is not defined if the complexity class $B$ does not have any complete problems with respect to the reductions available to $A$ .)

It is understood that NP ⊆ P^NP, but the question of whether NP^NP, P^NP, 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 P^A and NP^A for an oracle A. In particular, it has been shown there exist languages A and B such that P^A=NP^A and P^B≠NP^B.^[4] 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.^[5] Most proof techniques relativize.^[6]

One may 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, P^A≠NP^A.^[7] 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 that random oracles support a statement with probability 0 or 1 only. (This follows from Kolmogorov's zero–one law.) This is only weak evidence that P≠NP, since a statement may be true for a random oracle but false for ordinary Turing machines;^{[ original research? ]} for example, IP^A≠PSPACE^A for a random oracle A but IP = PSPACE.^[8]

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 it cannot determine, in general, whether machines equivalent to itself 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 .^[9]^{[ page needed ]}

Applications to cryptography

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).

Related Research Articles

In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete.

<span class="mw-page-title-main">Theory of computation</span> Academic subfield of computer science

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree. The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2^p(n)) time, where p(n) is a polynomial function of n.

Hypercomputation or super-Turing computation is a set of models of computation that can provide outputs that are not Turing-computable. For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that can correctly evaluate every statement in Peano arithmetic.

In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem to another decision problem using an effective function. The reduced instance is in the language $if and only if the initial instance is in its language . Thus if we can decide whether instances are in the language, we can decide whether instances are in its language by applying the reduction and solving for . Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that reduces to if, in layman's terms is at least as hard to solve as . This means that any algorithm that solves can also be used as part of a program that solves .$

Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem.

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. This appears to have been first demonstrated in Gurevich, Stockmeyer & Vishkin (1984). The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.

In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A sufficiently efficient reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.

In computational complexity theory, L is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space. Formally, the Turing machine has two tapes, one of which encodes the input and can only be read, whereas the other tape has logarithmic size but can be read as well as written. Logarithmic space is sufficient to hold a constant number of pointers into the input and a logarithmic number of boolean flags, and many basic logspace algorithms use the memory in this way.

In computability theory, a Turing reduction from a decision problem $to a decision problem is an oracle machine which decides problem given an oracle for . It can be understood as an algorithm that could be used to solve if it had available to it a subroutine for solving . The concept can be analogously applied to function problems.$

In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. It can also be defined equivalently in terms of Turing machines with advice, extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, P/poly is the class of decision problems that can be solved by a polynomial-time Turing machine with advice strings of length polynomial in the input size. These two different definitions make P/poly central to circuit complexity and non-uniform complexity.

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs.

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.

Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs".

In structural complexity theory, the Berman–Hartmanis conjecture is an unsolved conjecture named after Leonard C. Berman and Juris Hartmanis that states that all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms.

References

Footnotes

↑ Adachi 1990, p. 111.
↑ Rogers 1967, p. 129.
↑ Soare 1987, p. 47; Rogers 1967, p. 130.
↑ Baker, Gill & Solovay 1975, p. 431.
↑ Trevisan 2014, p. 2.
↑ Trevisan 2014, p. 1.
↑ Bennett & Gill 1981, p. 96.
↑ Chang et al. 1994, p. 29.
↑ Börger 1989.

Sources

Adachi, Akeo (1990). Foundations of computation theory. Tokyo: Ohmsha. ISBN 978-4-274-02190-9.
Baker, Theodore; Gill, John; Solovay, Robert (December 1975). "Relativizations of the P=?NP Question" (PDF). SIAM Journal on Computing. 4 (4). doi:10.1137/0204037. ISSN 0097-5397. Archived (PDF) from the original on 19 March 2023. Retrieved 21 October 2023.
Bennett, Charles H.; Gill, John (February 1981). "Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1" (PDF). SIAM Journal on Computing. 10 (1). doi:10.1137/0210008. ISSN 0097-5397. Archived (PDF) from the original on 25 December 2022.
Börger, Egon (1989). Computability, complexity, logic. Studies in logic and the foundations of mathematics. Amsterdam: North-Holland. ISBN 978-0-444-87406-1.
Chang, Richard; Chor, Benny; Goldreich, Oded; Hartmanis, Juris; Håstad, Johan; Ranjan, Desh; Rohatgi, Pankaj (1 August 1994). "The random oracle hypothesis is false" (PDF). Journal of Computer and System Sciences. 49 (1): 24–39. doi: 10.1016/S0022-0000(05)80084-4 . ISSN 0022-0000.
Davis, Martin, ed. (1 April 1965). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions . Hewlett, New York: Raven Press. ISBN 978-0-911216-01-1 . Retrieved 21 October 2023.
Papadimitriou, Christos (30 November 1993). Computational complexity. Reading, Massachusetts: Addison-Wesley. ISBN 978-0-201-53082-7.
Rogers, Hartley (1 April 1967). Theory of recursive functions and effective computability . New York: McGraw-Hill. OCLC 559483934.
Sipser, Michael (1997). Introduction to the theory of computation. Boston: PWS Publishing. ISBN 978-0-534-94728-6. OCLC 300459879.
Soare, Robert I. (1987). Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic (1st ed.). Springer Berlin, Heidelberg. doi:10.1007/978-3-662-02460-7_3. ISSN 0172-6641.
Trevisan, Luca (16 January 2014). "Notes for Lecture 4" (PDF). CS254: Computational Complexity. Stanford University. Archived (PDF) from the original on 1 April 2014. Retrieved 22 October 2023.
Turing, Alan (1939). Systems of Logic Based on Ordinals (PhD thesis). Princeton University. doi:10.1112/plms/s2-45.1.161. hdl: 21.11116/0000-0001-91CE-3 . ProQuest 301792588. Archived from the original on 13 March 2020.
van Melkebeek, Dieter (29 June 2003). Randomness and Completeness in Computational Complexity . Lecture Notes in Computer Science. Vol. 1950. Springer Berlin Heidelberg. doi:10.1007/3-540-44545-5. ISBN 978-3-540-44545-6. ISSN 1611-3349. OCLC 48909425. S2CID 27442913.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[FOOTNOTEAdachi1990111-1] Adachi 1990, p. 111.

[FOOTNOTERogers1967129-2] Rogers 1967, p. 129.

[FOOTNOTESoare198747Rogers1967130-3] Soare 1987, p. 47; Rogers 1967, p. 130.

[FOOTNOTEBakerGillSolovay1975431-4] Baker, Gill & Solovay 1975, p. 431.

[FOOTNOTETrevisan20142-5] Trevisan 2014, p. 2.

[FOOTNOTETrevisan20141-6] Trevisan 2014, p. 1.

[FOOTNOTEBennettGill198196-7] Bennett & Gill 1981, p. 96.

[FOOTNOTEChangChorGoldreichHartmanis199429-8] Chang et al. 1994, p. 29.

[FOOTNOTEBörger1989-9] Börger 1989.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]