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}$.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ cs.stackexchange.com/q/12480/755 $\endgroup$– D.W. ♦Commented Oct 28 at 18:21
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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}$.
$\begingroup$
$\endgroup$
That's referring to a complexity class defined in terms of oracle machines. See the Wikipedia article on that topic for more.
For example, $P^L$ means the class of all problems that can be solved in polynomial time using a machine that has an oracle for $L$ (essentially, a subroutine you can invoke that magically tells you in $O(1)$ time whether $x \in L$ for any $x$ of your choice). Also, $P^P$ means the union of $P^L$ over all $L \in P$, i.e., all problems that can be solved in polynomial time using a machine that has an oracle for any language in $P$ of your choice.