World's most popular travel blog for travel bloggers.

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

, , No Comments
Problem Detail: 

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.

Asked By : AmirB

Answered By : Ariel

In order to explain this, you need to understand what is meant by "diagonalization argument".

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}}$.

For further reading you could go to "Computational Complexity: A Modern Approach", by Arora & Barak. They have a section on limits of diagonalization.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback