# A machine with multiple oracles

Suppose a machine $$T$$, and oracles $$A$$ and $$B$$ solve all problems in the complexity classes $$\mathcal C_T$$, $$\mathcal C_A$$ and $$\mathcal C_B$$ respectively.

Let $$T^{\{A,B\}}$$ denote a machine that is equivalent to a machine $$T$$ that has access to oracles $$A$$ and $$B$$. What would be the complexity class of all problems solvable by such a machine? Is it $$\mathcal C_T^{\mathcal C_A\cup\mathcal C_B}$$, $$\mathcal C_T^{\mathcal C_A}\cup\mathcal C_T^{\mathcal C_B}$$ or something else entirely? E.g. could it be that $$\mathsf{P^{\{NP, coNP\}}=PSPACE}$$?

The definition of an oracular complexity class is key to answering this question, it is often defined as: $$\mathsf{C^{A}=\bigcup_{L_A\in A}C^{L_A}}$$

But how do we define two oracles? Well the union definition ($$\mathsf{C^{A,B}}=\mathsf{C^{A\cup B}}$$) would imply that a Turing machine has access to only one language from either $$\mathsf{A}$$ or $$\mathsf{B}$$, which is not quite what we want. We would like that it has a language from both:

$$\mathsf{A^{B,C} = \bigcup_{L_B\in B,\hspace{0.05cm}L_C\in C} A^{L_B, L_C}}.$$

Choosing this definition would imply that $$\mathsf{A^{B,C}\not = \mathsf{C^A \cup C^B}}$$ either. For counter-example assume there exists some $$\mathsf{L_A\in C^A\setminus C^B}$$ and some $$\mathsf{L_B\in C^B\setminus C^A}$$. Deciding the language: $$\mathsf{L}=\{x\#y: x\in L_A, y\in L_B \}$$ is in $$\mathsf{C^{A,B}}$$ under our definition (assuming C is capable of Turing reductions), but it is in neither $$\mathsf{C^A}$$ or $$\mathsf{C^B}$$, so it can not be in $$\mathsf{C^A \cup C^B}$$.

So what is $$\mathsf{C^{A,B}}$$? Well, it seems to be it is its own object, without a simple equality to some other understood concept. Although, it often can be simplified when $$\mathsf{A}$$, $$\mathsf{B}$$ or $$\mathsf{C}$$ are known. For example, in the case you state there is a simple reduction.

$$\mathsf{P^{NP,CoNP}=P^{NP} }.$$

This is because $$\mathsf{P^{NP}=P^{CoNP}}$$ and polynomial time TMs can simulate other polynomial time TMs.

• So, it's not possible to simulate alternations with having an access to both $\mathsf{NP}$ and $\mathsf{coNP}$ oracles. And I suppose that would hold even if you replace oracles with their functional counterparts - $\mathsf{FNP}$ and $\mathsf{coFNP}$. Nov 23, 2023 at 11:03