0

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.

Dan Stahlke
  • 493
  • 2
  • 8
  • I think we can easily simulate algorithms in this oracle setting within the usual oracle setting, can't we? – Kaveh Jul 02 '12 at 18:47
  • @Kaveh, could you explain your comment? Having the oracle Y is more powerful than X, and in fact allows answering any question about X in one step. However, having oracles Y and Y', derived from X and X', does not answer all questions about the pair (X, X') in a small number of calls to Y and Y'. So I think the concept is nontrivial. Actually it more or less is very similar to communication complexity, but by defining the oracles Y and Y', I hope to study computation without reference to communication. – Dan Stahlke Jul 02 '12 at 18:59
  • 3
    can't we think of Y(X) as a single oracle? – Kaveh Jul 03 '12 at 02:54
  • 1
    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. – Kaveh Jul 03 '12 at 02:54
  • @Kaveh, yeah, so I was thinking of X and X' as being the inputs. So the inputs, which are typically exponentially large, are given in the form of oracles (like in Grover's algorithm). Then I want the oracles Y and Y' to easily answer any question that involves only one of the inputs X and X'. It is very likely that I didn't describe it well or used the wrong language since I am just getting started in CS theory. – Dan Stahlke Jul 03 '12 at 12:07
  • 1
    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'.) – Kaveh Jul 04 '12 at 01:27
  • 3
    Type-2 complexity theory? – Tsuyoshi Ito Jul 04 '12 at 13:34
  • @Kaveh: yes, that is exactly how I am thinking of it. The specifics depend on how everything is defined, but I would be happy to see references to anything of this general character. – Dan Stahlke Jul 04 '12 at 17:08
  • @TsuyoshiIto: what you link to describes how I am thinking of oracle X. But is there name for the oracle Y(X)? – Dan Stahlke Jul 04 '12 at 17:08
  • No, “type-2 complexity theory” is not a name for an oracle. – Tsuyoshi Ito Jul 04 '12 at 18:29

0 Answers0