Editing Oracle machine (section)

==Complexity classes of oracle machines==
The [[complexity class]] of [[decision problem]]s solvable by an algorithm in class A with an oracle for a language L is called A<sup>L</sup>. For example, P<sup>SAT</sup> 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<sup>B</sup> can be extended to a set of languages B (or a complexity class B), by using the following definition:
:<math>A^B = \bigcup_{L \in B} A^L</math>

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

It is understood that NP &sube; P<sup>NP</sup>, but the question of whether NP<sup>NP</sup>, P<sup>NP</sup>, 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 [[P = NP problem|complexity classes P and NP]], by considering the relationship between P<sup>A</sup> and NP<sup>A</sup> for an oracle A. In particular, it has been shown there exist languages A and B such that P<sup>A</sup>=NP<sup>A</sup> and P<sup>B</sup>&ne;NP<sup>B</sup>.{{sfn|Baker|Gill|Solovay|1975|p=431}} 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.{{sfn|Trevisan|2014|p=2}} Most proof techniques relativize.{{sfn|Trevisan|2014|p=1}}

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<sup>A</sup>&ne;NP<sup>A</sup>.{{sfn|Bennett|Gill|1981|p=96}} 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&ne;NP, since a statement may be true for a random oracle but false for ordinary Turing machines;{{Original research inline|date=October 2023}} for example, IP<sup>A</sup>&ne;PSPACE<sup>A</sup> for a random oracle A but [[IP (complexity)|IP]] = [[PSPACE]].{{sfn|Chang|Chor|Goldreich|Hartmanis|1994|p=29}}