What does it mean when one complexity class has another complexity class superscript?For example, sometimes in papers I see $P^P$ or $P^{NP}$.
Superscript on complexity class?
complexity theory;np;oracle machines
It's a synthetic notation for complexity classes of oracle machines. Let $\mathcal{A}$ be a class and $L$ be a language. We define:$$\mathcal{A}^L$$to be the complexity class of the languages decidable by a machine in class $\mathcal{A}$ with access to an oracle for $L$.If $\mathcal{A}$ and $\mathcal{B}$ are classes, we define:$$\mathcal{A}^\mathcal{B} = \bigcup_{L \in \mathcal{B}} \mathcal{A}^L$$Therefore, $\mathcal{P}^\mathcal{P}$ is the class of languages decidable in polynomial time by a machine with an oracle for any language of $\mathcal{P}$, and $\mathcal{P}^\mathcal{NP}$ is the class of languages decidable in polynomial time by a machine with an oracle for any language of $\mathcal{NP}$.