patternMinor
Precise definition of oracle classes $A^B$
Viewed 0 times
definitionpreciseoracleclasses
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#71937, answer score: 3
Revisions (0)
No revisions yet.