0
$\begingroup$

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}$?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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}$. $\endgroup$
    – rus9384
    Commented Nov 23, 2023 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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