# What does $A^B$ mean?

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.

• 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. – Ran G. Jun 6 '13 at 4:19

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.
• 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. – frafl Jun 6 '13 at 13:45