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)
“The most powerful lessons about ethics and morality do not come from school discussions or classes in character building. They come from family life where people treat one another with respect, consideration, and love.”
—Neil Kurshan (20th century)
“There be three things which are too wonderful for me, yea, four which I know not: the way of an eagle in the air; the way of a serpent upon a rock; the way of a ship in the midst of the sea; and the way of a man with a maid.”
—Bible: Hebrew Proverbs, 30:18-19.
From the oracle of Agur, son of Jakeh.
“There are bills to be paid, machines to keep in repair,
Irregular verbs to learn, the Time Being to redeem
From insignificance.”
—W.H. (Wystan Hugh)