2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ I think we had this or something similar before. Does anyone remember? $\endgroup$ – Raphael♦ Oct 3 '16 at 15:18
  • 1
    $\begingroup$ Closest i have found: cs.stackexchange.com/questions/1271/… $\endgroup$ – Ariel Oct 3 '16 at 15:41
  • $\begingroup$ @Raphael by answer similar $\endgroup$ – Evil Oct 3 '16 at 16:26
  • $\begingroup$ Thanks Ariel, Evil! Community votes, please: duplicate? $\endgroup$ – Raphael♦ Oct 3 '16 at 19:11
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ My current understanding of a diagonolization argument to seperate two classes A and B is an argument in which one constructs a turing machine in class B, and assumes an equivalant machine in class A. one than shows that the machine in A is nonsensical (rejects if accepts and accepts if rejects) and therfore can not exist. Is this what is meant? $\endgroup$ – AmirB Oct 3 '16 at 16:01
  • 1
    $\begingroup$ All you described here is the general concept of proof by contradiction. Nothing is said about the specific nature of the proof. Notice that simulation/self reference are key features in known "diagonalization proofs" (e.g. time hierarchy/undecidability of halting). $\endgroup$ – Ariel Oct 3 '16 at 16:17

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.