Does $A^B = A^C$ imply $B = C$?

Question

I am familiar with the Baker, Solovay, Gill result of non-relativization of P vs NP problem. They showed that $\exists A \text{ s.t }P^A \neq NP^A$. But since we are referring to $P, NP$ as models of computation, this still does not concretely talk indicate $P \neq NP$. But what happens when we treat $P, NP$ as black-boxes themselves?

If I understand correctly, when using an oracle $B$ as $A^B$, $B$ is being used as a black-box that decides the language, there is no further information exploited about $B$ in the expression. If we are able to find $A$ such that $A^P \neq A^{NP}$, will that automatically solve P vs NP problem?

I feel that since $A^{NP}$ can access the oracle of $SAT$ it can by default decide any language decidable by $A^P$. In general where this is not the case, can we infer anything about $B \text{ vs } C$ from the result $A^B \neq A^C$?

Answer 1

Morally, yes, I agree. I believe what you write is correct and a reasonable way to think about things.

---

You can stop reading here, but if you want to read longer musings/ramblings, continue on:

Pedantically, it might depend on how exactly you formalize your question. Perhaps surprisingly, the notation $A^B$ is not entirely well-defined and is a bit of an abuse of notation. In most cases, it's not a big deal and we know how to read between the lines to understand what is meant, or there aren't any issues, but in some cases there can be issues. You might be tempted to think that $A^B$ should be well-defined whenever $A$ is any complexity class, but it's not; $A^B$ is only well-defined if $A$ is a class of Turing machines, so if you have a complexity class, you first need to identify a corresponding set of Turing machines. Often there is a clear correspondence between a complexity class and a class of Turing machines (e.g., $P$ corresponds to Turing machines that run in polynomial time), but occasionally it's not so clear. Normally this isn't much of an issue with many of the complexity classes we deal with in practice, but if you want to prove something for all $A$, this matters.

So to formalize your question, we need to define what we mean by $A^B$, and what we allow $A$ to be.

One reasonable definition of $A^B$ is

$$A^B = \bigcup_{L \in B} A^L,$$

i.e., take an infinite union over all languages $L$ in $B$. Under this definition, yes, if $A^P$ and $A^{NP}$ are well-defined, then $A^P \ne A^{NP}$ implies $P \ne NP$. In particular, if $P = NP$, then by plugging into the above definition, we see that $A^P = A^{NP}$; so the desired result follows by a contrapositive.

But this is not the only accepted definition. Another definition of $A^B$ is $A^L$ where $L$ is some language that is complete for $B$. Under this definition, it seems trickier. If I'm understanding correctly, it seems possible that we might have a class $A$ of Turing machines for which we could plausibly claim that $A^P \ne A^{NP}$, but we could still have $P \ne NP$. Suppose we took (say) maximum matching ($MAXMATCH$) as our problem complete for $P$, and 3SAT as our problem complete for $NP$. Suppose we took $A$ to be the class of Turing machines that use $O(1)$ space, which corresponds to the set of regular languages. Then $A^{3SAT}$ includes $3SAT$, since you can recognize $3SAT$ by simply copying the input over to the oracle, running the oracle, and returning whatever the oracle returns. But I expect that $A^{MAXMATCH}$ does not include $3SAT$ (not even if $P=NP$). So I expect we have $A^{MAXMATCH} \ne A^{3SAT}$, but I don't think this tells us anything about $P$ vs $NP$.

Arguably, the latter is a trivial case that should be ruled out by any reasonable choice of definitions. So perhaps it is not really an objection to your statement. Treat it more as a warning that we need to be cautious about how we formalize our intuitions, when we use notation like $A^B$ where $A$ and $B$ are complexity classes.

See also For complexity classes A and B, what does $A^B$ mean?, Superscript on complexity class? for basic definitions, the comments at https://cstheory.stackexchange.com/q/2490/5038, https://cstheory.stackexchange.com/q/2484/5038, https://cstheory.stackexchange.com/q/972/5038, https://cstheory.stackexchange.com/q/16268/5038 for cautionary notes, and also https://mathoverflow.net/q/35664/37212, https://cstheory.stackexchange.com/q/21590/5038 for elaboration on the points you already raised.