<p>I was reading <a href="https://cstheory.stackexchange.com/questions/27377/does-the-cook-levin-theorem-relativize">this post about whether Cook-Levin relativizes</a> 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):</p>
<blockquote>
<p>But when we say &quot;<span class="math-container">$NP^A$</span>-complete,&quot; 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).</p>
</blockquote>
<p>However, I do not see why one would not allow for the use of oracles in reductions when defining <span class="math-container">$NP^A$</span>-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 <span class="math-container">$NP^A$</span>-complete using polynomial-time reductions with the use of oracles?</p>

CC BY-SA 4.0
2022-04-15T09:43:38.850Z
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 ...
Emil Jeřábek
CC BY-SA 4.0
2022-04-15T09:45:33.690Z
... 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.
Emil Jeřábek
<np-complete><relativization>
Relativized Version of NP^A-complete
Noble Mushtak
# Relativized Version of NP^A-complete

(Asked by: username_0 on 2022-04-14)

I was reading [this post about whether Cook-Levin relativizes](https://cstheory.stackexchange.com/questions/27377/does-the-cook-levin-theorem-relativize) 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?

**Tags:** np-complete, relativization
> **Comments:**
> **username_1**: 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 ...  
> **username_1**: ... 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.  

---

## 0 answers

