# Complexity Theory - Why can't you use diagonalization to seperate classes A and B when an orcale O exists under which A=B?

In a recent lecture the professor stated that given two complexity classes A and B, and given the existance of an oracle O such that $$A^o=B^o$$ (As I understand, meaning that a problem in A with can be reduced to a problem in B with the oracle O), It can be shown that classes A and B can not be seperated using a diagonilization argument.

Unfortunately he did not explain much further... Can someone give the outline\thought process of the general proof (informally)? I think I understand why diagonalization fails in specific time hirearchy proof constructions (due to the existence of a cook reduction) but I can not see how to generlize this in a satisfactory way.

Thank you.

• I think we had this or something similar before. Does anyone remember?
– Raphael
Oct 3, 2016 at 15:18
• Closest i have found: cs.stackexchange.com/questions/1271/… Oct 3, 2016 at 15:41
– Evil
Oct 3, 2016 at 16:26
– Raphael
Oct 3, 2016 at 19:11

In this context, we mean a proof that only treats Turing machines as black boxes, i.e. only uses the fact that we can encode Turing machines as strings and treat them as inputs to other machines. This gives rise to the possibility of simulation, a machine $M$ can simulate some machine $M'$ without paying too much in space/time.
You can now observe that such proofs immediately generalize to the oracle model (encoding and simulation are possible), so if you could write such a proof for $A\neq B$, it would also work in the oracle model, showing $A^\mathcal{O}\neq B^{\mathcal{O}}$.