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)
“By his very success in inventing labor-saving devices, modern man has manufactured an abyss of boredom that only the privileged classes in earlier civilizations have ever fathomed.”
—Lewis Mumford (1895–1990)
“Know thyself.”
—Inscription on the Oracle of Apollo at Delphi, Greece, 6th century B.C.....
“If men do not keep on speaking terms with children, they cease to be men, and become merely machines for eating and for earning money.”
—John Updike (b. 1932)