Suppose I have an oracle X. Then let Y be an oracle which will answer any computable question about X. In other words, Y takes as input a Turing program which can in turn make calls to X. Y then returns the output of that program (assuming the output is one bit, otherwise, or if the program doesn't halt, then the definition is open to interpretation).

Has this concept been studied? Is there a name for such oracles?

This relates to communication complexity. In that case X would be Alice's input, X' would be Bob's input, and Y and Y' would be sufficient to efficiently compute their strategies. The Y and Y' oracles are a way to express the fact that in communication complexity one usually doesn't care how much time the parties spend on computation.

  • $\begingroup$ I think we can easily simulate algorithms in this oracle setting within the usual oracle setting, can't we? $\endgroup$ – Kaveh Jul 2 '12 at 18:47
  • 3
    $\begingroup$ can't we think of Y(X) as a single oracle? $\endgroup$ – Kaveh Jul 3 '12 at 2:54
  • 1
    $\begingroup$ btw, I am not sure I understand the question correctly. In computational problems we typically have inputs and want to compute the value of a fixed function on those inputs. $\endgroup$ – Kaveh Jul 3 '12 at 2:54
  • 1
    $\begingroup$ If I understand correctly, here is the setting: we have two inputs X and X' and we want to compute a function on them. The machine is given access to two fixed oracles which answer questions about X and X'. Btw, you still cannot ask any question about X and X' since the machine has to be able to write the question (i.e. the code of the TM) and that will take time. (Also what can be done will depend on the particular encoding of the TMs used by Y and Y'.) $\endgroup$ – Kaveh Jul 4 '12 at 1:27
  • 3
    $\begingroup$ Type-2 complexity theory? $\endgroup$ – Tsuyoshi Ito Jul 4 '12 at 13:34

Your Answer

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

Browse other questions tagged or ask your own question.