# Relativized Version of NP^A-complete

I was reading this post about whether Cook-Levin relativizes and at the bottom of the answer, they include a quote from Computational Complexity by C. Papadimitriou (this is a longer version of the quote than included in the aforementioned post):

But when we say "$$NP^A$$-complete," do we also allow the use of oracles in our reductions? With a little reflection we may decide that the right way to state the result is in terms of ordinary reductions (especially since there are difficulites associated with defining space-bounded oracle machines, see the references).

However, I do not see why one would not allow for the use of oracles in reductions when defining $$NP^A$$-complete. Even accounting for the difficulty of defining space-bounded oracle machines, one could simply use polynomial-time reductions with an oracle instead of logarithmic-space reductions. So what goes wrong when one defines $$NP^A$$-complete using polynomial-time reductions with the use of oracles?

• Well, one reason is that the whole point of using reductions is to compare the complexity of various languages, hence ideally, you want to use a single notion of reduction that applies to as many languages and classes as feasible. If you introduce relativized poly-time reductions to apply to languages in $\mathrm{NP}^A$, it does not make much sense to use it to compare their complexity with languages coming from elsewhere. Another thing is that there is nothing relativized about the languages per se: it is only meaningful to relativize machines. Given a language $L$, there is no way ... Apr 15, 2022 at 9:43
• ... to tell whether $L$ was computed without any oracle, with oracle $A$, or with another oracle $B$. Any language may be computed in many different ways using many different oracles. Apr 15, 2022 at 9:45