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:
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 PB≠NPB. 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, then with probability 1, PA≠NPA. 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 P≠NP. A statement may be true for a random oracle and false for ordinary Turing machines at the same time; for example for oracles A, IPA≠PSPACEA, while IP = PSPACE.
Read more about this topic: Oracle Machine
Famous quotes containing the words complexity, classes, oracle and/or machines:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)
“There are four classes of idols which beset men’s minds. To these for distinction’s sake I have assigned names—calling the first class Idols of the Tribe; the second, Idols of the Cave; the third, Idols of the Market-Place; the fourth, Idols of the Theatre.”
—Francis Bacon (1561–1626)
“Know thyself.”
—Inscription on the Oracle of Apollo at Delphi, Greece, 6th century B.C.....
“The machine has had a pernicious effect upon virtue, pity, and love, and young men used to machines which induce inertia, and fear, are near impotents.”
—Edward Dahlberg (1900–1977)