3
$\begingroup$

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$...

$\endgroup$
  • $\begingroup$ Could you clarify what the problem is? $P^P$ is the set of decidable languages. $\endgroup$ – Patrick Jun 2 '14 at 14:37
  • $\begingroup$ @Patrick $\mathrm{P^P=P}$. $\endgroup$ – David Richerby Jun 2 '14 at 16:27
  • $\begingroup$ "class $P^P$, we have an oracle to it. We can now" $\: \mapsto \:$ "class $P$, so we can" $\;\;\;\;$ $\endgroup$ – user12859 Jun 2 '14 at 17:33
  • $\begingroup$ @DavidRicherby Right, thanks. Assumed "polynomial hierarchy", which clearly wasn't the scope of the question (at least it is clear now). $\endgroup$ – Patrick Jun 4 '14 at 14:38
  • 1
    $\begingroup$ @GMB : $\:$ Furthermore, your machines $M\hspace{.02 in}'$ run in $O(1)$ time. $\;\;\;\;$ $\endgroup$ – user12859 Jun 4 '14 at 22:25
4
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ Alright, I think I see what's going on here. By defining $P^P = \cup_{L \in P} P^L$, we are saying that a problem in $P^P$ needs an oracle TM that only ever gets to call one single $P$ oracle across all its input lengths. This gets around my objection, because it disallows querying a new machine for every input. Is that accurate? $\endgroup$ – GMB Jun 4 '14 at 22:09
  • $\begingroup$ Yes. ${}{}{}\;$ $\endgroup$ – user12859 Jun 4 '14 at 22:21
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Having an oracle for a single C-complete problem is equivalent to allowing oracles for all problems in C." -- I don't see that this is true; maybe I explained myself poorly in the OP. For example, it should be possible to "hide" an exponentially increasing amount of work in the oracle call, while still only ever calling machines that run in polynomial time. $\endgroup$ – GMB Jun 2 '14 at 19:54
  • $\begingroup$ Perhaps membership in $P^C$ means there is an algorithm that only ever calls an oracle to a single problem in $C$ (as opposed to calling a different oracle for different inputs)? $\endgroup$ – GMB Jun 2 '14 at 20:00
  • $\begingroup$ @GMB Let's be a little more concrete and say that $\mathcal{C}$ is EXPTIME and that you have an oracle for every problem in EXPTIME. The oracles allow you to solve any EXPTIME decision problem in a single time step. But, given that saving, your whole computation has to be in polytime. So, in particular, you can't use exponential time to decide which oracle to use. Or, in the model where you have a single EXPTIME-complete oracle, you can't use exponential time to set up its input. $\endgroup$ – David Richerby Jun 2 '14 at 20:59
  • $\begingroup$ GMB doesn't "use exponential time to decide which oracle to use." $\hspace{2.25 in}$ See the "Let $M$ ..." paragraph in the OP. $\:$ $\endgroup$ – user12859 Jun 3 '14 at 2:41
  • $\begingroup$ @RickyDemer The claim in the following paragraph is that $M'$ runs in linear time. There are two possibilities for $M'$: either it rejects everything (call that $M_r$), or it accepts only $x$ (call that one $M_{a,x}$). To simulate $M$ for all inputs, the machine calling the oracle must be able to decide, for all $x$, whether to call the oracle for $M_{a,x}(x)$ or the one for $M_r(x)$. If $M$ decides an EXPTIME-hard problem, you need exponential time to decide which of those two oracles to call. That can't be done by a polynomial time machine. $\endgroup$ – David Richerby Jun 3 '14 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.