Question about the definition of complexity class oracles

Question

If $B$ is a complexity class, then the class $P^B$ (for example) is defined as the set of problems that can be run in polynomial time, given an oracle to every problem in $B$. That's what they told me in my Theory of Computation class, anyways.

Per this definition, it seems to me that $P^P$ captures every decidable language. Here's why I think that:

Let $M$ be a TM that always halts. On input $x$, construct a new machine $M'$ that: (1) checks to see if the input is equal to $x$, (2) if its input is $x$ then it simulates $M$ on $x$, (3) if its input is not $x$ then it instantly rejects.

This new machine $M'$ runs in $O(n)$ time, so in the class $P^P$, we have an oracle to it. We can now consult this oracle to find out if $M'$ accepts $x$, and we learn in only $O(n)$ time whether or not $M$ accepts $x$. So we have an algorithm that decides $M$ and runs in $TIME(O(n))$, given an oracle to some countable set of problems in $TIME(O(n))$ (e.g. every $M'$, constructed with respect to every possible finite bitstring $x$).

What am I misunderstanding?

---

Here is an attempt to clarify my confusion.

This is the model that I think we are using:

There are three tapes usable by the Oracle Turing Machine: a standard worktape, an "oracle input tape," and an "oracle machine tape." The OTM can enter a special state where it takes the machine description written on the oracle machine tape, performs a magical 1-step simulation of that machine on input equal to the contents of the oracle input tape, and then writes down a $1$ or a $0$ on the worktape according to the results of the simulation.

Define: A language $L$ is in $P^P$ if there is an OTM that decides L and always halts in $p(n)$ steps on length $n$ input (for some polynomial $p$), and also for every Turing machine description $M$ used by the OTM, there exists a polynomial $q$ such that $M$ halts in $q(n)$ steps on input $M$.

Then my argument is valid, I think: every machine that we write down runs in linear time overall (even though the constant associated with that machine will grow very quickly for increasingly-long inputs).

This wouldn't be a problem if we flipped the quantifiers (i.e. "there exists a polynomial $q(n)$ such that every machine description $M$ used by the OTM halts in $q(n)$ steps). But I'm not sure that still describes $P^P$...

Answer 1

Either you're misunderstanding what they said, or you're not misunderstanding anything.

If $B$ is a complexity class, then the class $P^B$ is defined as $\bigcup_{L \in B} P^{L}$. (That applies even when $B$ does not have a complete problem.)

If $B$ is a complexity class and $K$ is complete for $B$ under polynomial-time Turing reductions, then $P^B = P^K$.

Proof: If those hypotheses hold then for all languages $L$ in $B$, by using the reduction to simulate oracle queries to $L$, one has $P^L \subseteq P^K$.

Thus, if those hypotheses hold then $P^K \subseteq \bigcup_{L \in B} P^{L} = P^B = \bigcup_{L \in B} P^{L} \subseteq \bigcup_{L \in B} P^{K} = P^K$.

Therefore, if those hypotheses hold then $P^B = P^K$.

Answer 2

Let $\mathcal{C}$ be a complexity class. $\mathrm{P}^{\mathcal{C}}$ is usually defined to be the class of problems decidable in polynomial time by a deterministic machine that has an oracle for some $\mathcal{C}$-complete problem $X$. Thus, in particular, $\mathrm{P}^{\mathrm{P}} = \mathrm{P}$: you can only make polynomially many oracle calls and each one of those can be simulated in a polynomial number of steps.

Having an oracle for a single $\mathcal{C}$-complete problem is equivalent to allowing oracles for all problems in $\mathcal{C}$. By definition of completeness, any problem in $\mathcal{C}$ can be reduced in polynomial time to $X$. So, instead of calling the oracle for some problem $Y$, you perform the reduction from $Y$ to $X$ and use the oracle for that.

The reason you seem to have obtained something more powerful is that you've hidden a lot of complexity in your oracle calls. Suppose, for example, that $M$ decides an $\mathrm{EXPTIME}$-complete problem. By the time hierarchy theorem, there is no polynomial-time algorithm that, given $M$ and an input $x$, determines whether $M$ accepts $x$. This means that, when you want to call your oracle for $M(x)$, you don't know whether to call the one that accepts $x$ or the one that rejects it.

If you think in terms of having an oracle for a single complete problem, it's maybe easier to see. You now need to do the reduction yourself: that is, you need to reduce the problem defined by $M$ to your $\mathrm{P}$-complete problem $X$. But this cannot be done by the time hierarchy theorem.