For complexity classes A and B, what does $A^B$ mean?

Question

What does $A^B$ mean where A and B are complexity classes?

The "Polynomial Hierarchy" page says:

$A^B$ is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some complete problem in class B

In that case what is a Turing machine in class A?

(besides just a machine of some sort that can solve problems in A, because that doesn't give any insight as to what it means to augment such a machine with an oracle)

The motivation for this question was: What is a Turing Machine in class coNP.

• Ran G.: Yes, it's the augmentation of having oracle acess to some language in $B$. The TM is defined by $A$ (e.g, if $A=P$ the TM is deterministic, polynomially bounded; if $A=NP,ドル it is nondeterministic, polynomial). See the link to Wikipedia.
• D.W.: cs.stackexchange.com/q/69037/755, cs.stackexchange.com/questions/170174/…, cstheory.stackexchange.com/questions/2490/…, mathoverflow.net/a/35666/37212, cstheory.stackexchange.com/q/21590/5038

Answer 1

An oracle is a way for a Turing Machine to ask a question and get it answered immediately, "magically". The way we usually model it is that the Turing Machine can write down the question on a special, extra tape, and then (say) the tape is erased and the answer immediately written on it.

More specifically, we usually suppose that the oracle is for a particular language, so we write a string on the tape, followed by some special "end-of-string" symbol; then, the formula disappears and is replaced by either "YES" or "NO".

For a concrete example, suppose our Turing Machine has an oracle for SAT. Then it can write a formula on the string and immediately find out if it's satisfiable or not.

Notice that, since SAT is NP-Complete, a TM with a SAT oracle can decide any language in NP in polynomial time: Just reduce the input to a SAT formula, and then ask the oracle about this SAT formula.

So we might write $P^{NP}$ for the set of languages that can be decided in polynomial time by a TM with an oracle for SAT.

• frafl: The OP has more problems understanding the base class $\mathcal A$ than the concept of oracles, especially if it's not easy to figure out what a corresponding TM is. So probably some examples like $AC^{NP}$ or $(NP\cap co$-$NP)^{\mathcal C}$ would be nice.