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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.