1
$\begingroup$

$C_1 \subseteq C_2$ implies $C_1^A\subseteq C_2^A$?

I've given a caveat that one shouldn't make this implication blindly and it shall be justified.

I can think of examples such that $C_1^A \subsetneq C_2^A$ and examples such that $C_1^A = C_2^A$.

but could it be that $C_2^A \subset C_1^A$? I can't see how.

So what's the point of this caveat?

$\endgroup$
  • $\begingroup$ The main point is that $C_2^A$ is not a strict subset of $C_1^A$ for any oracle. But it still can be a subset (equal). $\endgroup$ – rus9384 Sep 18 '17 at 13:38
  • $\begingroup$ A proof of $C_1 \subseteq C_2$ relativizes if $C_1^A \subseteq C_2^A$ using essentially the same argument. Some proof techniques are non-relativizing. $\endgroup$ – Yuval Filmus Sep 18 '17 at 13:47
3
$\begingroup$

A proof technique is (informally) relativizing if the results it generates also hold relative to an oracle. Not all proof techniques are relativizing. Perhaps the best known example is $\mathsf{IP}=\mathsf{PSPACE}$, which uses the technique of algebraization. Although $\mathsf{PSPACE} \subseteq \mathsf{IP}$, there is an oracle $O$ such that $\mathsf{PSPACE}^O \not\subseteq \mathsf{IP}^O$ (see this question on cstheory).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.