Let $A,B,C$ be a complexity classes, are $A \subseteq B \Longrightarrow A^C \subseteq B^C$?

35 Views Asked by At

Let $A,B,C$ be a compleixty classes is $A \subseteq B \Longrightarrow A^C \subseteq B^C$.

So $A \subseteq B$ given oracle access to some $L \in C$ complete, follow that $A^C \subseteq B^C$.

is that correct for any complexity classes?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes- containments relativize. If we can simulate $A$ machines using $B$ machines, then the same simulation goes through for $A^{C}$ machines using $B^{C}$ machines. The only difference is that the $A^{C}$ machines may make oracle queries; but those can be simulated by the $B^{C}$ machines.