<p>That is, suppose <span class="math-container">$A\subseteq B$</span> for two complexity classes <span class="math-container">$A$</span> and <span class="math-container">$B$</span>. Is it the case that for <em>any</em> oracle <span class="math-container">$C$</span>, and any definitions <span class="math-container">$A^*$</span> and <span class="math-container">$B^*$</span> of <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, we have <span class="math-container">${A^*}^C\subseteq {B^*}^C$</span>? (The particular definitions used may affect the relativization.)</p>
<p>I have spent quite a while searching for an answer to this, in addition to trying to prove it myself either way. I have yet to find any counter example (that is, some classes <span class="math-container">$A\subseteq B$</span> where <span class="math-container">$A^C\not\subseteq B^C$</span> for some oracle <span class="math-container">$C$</span>).</p>

CC BY-SA 4.0
2022-12-21T00:27:34.627Z
No. See, among others, https://cs.stackexchange.com/a/111956/6431
Clement C.
CC BY-SA 4.0
2022-12-21T07:16:04.010Z
The question is ill-posed, as relativization by an oracle is not an operation on complexity classes in the first place. Relativization involves picking an underlying machine model for the class, and modifying it in some machine-specific way to allow for oracles. It is possible to relativize one class in two different ways.
Emil Jeřábek
<cc.complexity-theory><oracles><relativization><structural-complexity>
Is complexity class containment preserved relative to any oracle?
abelard-to-girard
# Is complexity class containment preserved relative to any oracle?

(Asked by: username_0 on 2022-12-20)

That is, suppose $A\subseteq B$ for two complexity classes $A$ and $B$. Is it the case that for *any* oracle $C$, and any definitions $A^\*$ and $B^\*$ of $A$ and $B$, we have ${A^\*}^C\subseteq {B^\*}^C$? (The particular definitions used may affect the relativization.)

I have spent quite a while searching for an answer to this, in addition to trying to prove it myself either way. I have yet to find any counter example (that is, some classes $A\subseteq B$ where $A^C\not\subseteq B^C$ for some oracle $C$).

**Tags:** cc.complexity-theory, oracles, relativization, structural-complexity
> **Comments:**
> **username_1**: No. See, among others, https://cs.stackexchange.com/a/111956/6431  
> **username_2**: The question is ill-posed, as relativization by an oracle is not an operation on complexity classes in the first place. Relativization involves picking an underlying machine model for the class, and modifying it in some machine-specific way to allow for oracles. It is possible to relativize one class in two different ways.  

---

## 0 answers

