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?

  • $\begingroup$ 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 ... $\endgroup$ Apr 15, 2022 at 9:43
  • $\begingroup$ ... 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. $\endgroup$ Apr 15, 2022 at 9:45


Your Answer

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

Browse other questions tagged or ask your own question.