3
$\begingroup$

I was reading in Papadimitriou's "Computational Complexity" book Chapter 14, about Oracle Machines. Papadimitriou defines, in definition 14.3, page 339-340, Oracle Turing Machines with oracle a language $A \subseteq \Sigma^*$:

The computation of $M^{?}$ with oracle access $A$ in input $x$ is denoted $M^A(x)$.

So far so good.

In the next paragraph, he writes:

If $\mathcal{C}$ is any deterministic or non-deterministic complexity class, we can define $\mathcal{C}^A$ to be the class of all languages decided by machines of the same sort and time bound as $\mathcal{C}$, that have oracle access to $A$.

My question is:

Given any complexity class $B$ and $C$, can we always define $B^C$?

This is motivated by a question I posted (and deleted) at TCS.stackexchange where , using Papadimitriou's notation, I defined $B^C$ for a complexity class $B$ and $C$ but I received criticism (besides the context of the question) that I am not allowed to do that because oracle is not an operation defined on languages and hence complexity classes. Does this contradict the extract from Papadimitriou's book (where he explicitly defines $B^C$ for a _complexity class $B$)?

My understanding is that

We can define $B^C$ for a complexity class (i.e., a set of languages) $B$ if $B$ can be defined by a Turing Machine model.

If yes, why it is not explicit in Papadimitriou's book?

$\endgroup$
  • $\begingroup$ It's not so simple. There are many fine points involved. $\endgroup$ – Yuval Filmus Mar 23 '17 at 12:44
  • $\begingroup$ @YuvalFilmus I know. Thus the question. $\endgroup$ – PsySp Mar 23 '17 at 12:45
3
$\begingroup$

The simplest case is when $C$ has complete problems with respect to $\mathsf{F}B$ reductions (the function class corresponding to $B$). In that case, you can define $B^C$ as $B^L$ for some $C$-complete problem $L$, and everybody will be (mostly) happy, at least if $B$ is not a very weak class. This allows us to define $\mathsf{P}^{\mathsf{NP}}$, for example.

When $C$ doesn't have complete problems, sometimes the following definition is used: $B^C = \bigcup_{L \in C} B^L$, or perhaps $B^C = \bigcup_m \bigcup_{L_1,\ldots,L_m \in C} B^{L_1,\ldots,L_m}$. However, this definition doesn't necessarily have the right properties.

Another option is if you can enumerate all languages in $C$ (for example, $\mathsf{BPP}$ can be enumerated using probabilistic Turing machines with an explicit time bound), say they are $(L_n)_{n \in \mathbb{N}}$. In that case you can define $B^C = B^{L_1,L_2,\ldots}$, where the oracle for $L_1,L_2,\ldots$ accepts an index $i$ and a word $x$, and outputs whether $x \in L_i$. One drawback is that this definition depends on the enumeration; it's best to use a "natural" enumeration. Otherwise, you can "cheat" by putting information into the enumeration. A way out it to define $B^C$ as the intersection of $B^{L_1,L_2,\ldots}$ for all possible enumerations.

Things become even more complicated when $B$ is weak. For some of the issues involved, see Aehlig, Cook, and Nguyen, Relativizing Small Complexity Classes and their Theories. These issues are orthogonal to what we have described above: they cause problems even when trying to define $B^L$ for a language $L$.

$\endgroup$
  • $\begingroup$ Awesome answer. But does it directly answer what properties $B$ should have in order to define $B^C$? (Assuming $C$ as above) can we define $B^C$ for any complexity class $B$? $\endgroup$ – PsySp Mar 23 '17 at 12:57
  • $\begingroup$ There is no uniform definition for $B^C$ in general. $\endgroup$ – Yuval Filmus Mar 23 '17 at 13:01

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.