10

Most of the literature seems to be concerned with machines with single oracles for specific problems, however there appear to be a few papers that consider machines with multiple oracles. Is there a good paper or thesis which provides an overview of what is known about such machines? In particular I am interested in P with multiple oracles.

Marcos Villagra
  • 3,290
  • 27
  • 45
Joe Fitzsimons
  • 13,675
  • 47
  • 91
  • 3
    If you only want a finite number N of oracles, you could define an N-in-1 compound oracle by using the first log(N) bits of the compound oracle to indicate which suboracle you wish to query. Am I missing something? – Niel de Beaudrap Aug 18 '10 at 16:56
  • Yes, I had thought of that. However, I am interested in specific sets of oracles, and so it seems more natural to consider them separately than as a compound object. I thought perhaps there might be some nice results in this direction. – Joe Fitzsimons Aug 18 '10 at 17:14
  • 1
    just for curiosity, does having multiple oracles add more computational power with respect to a single oracle machine? It seems to me that no, because you just take the oracle corresponding to the language in the highest complexity class. Also, having a fixed number of oracles will slowdown the machine by a constant. – Marcos Villagra Aug 18 '10 at 23:37
  • 1
    I'm with Marcos's comment about the strongest oracle subsuming the others.. but I'm interested what you had in mind now! – Daniel Apon Aug 19 '10 at 04:22
  • 1
    Are you thinking of allowing infinitely many oracles, where the TM is allowed to choose which oracle to query? With such a setup there might be an interesting difference between a set of oracles in which each was strictly weaker than some other oracle Q, and Q itself. – András Salamon Aug 19 '10 at 13:08
  • Marcos and Daniel: You seem to be assuming that one oracle must contain the other. It is quite possible that they be chosen for two different problems such that neither one contains the other.

    András: I had been thinking only of finite sets initially, but infinite sets of oracles may also be interesting.

     – Joe Fitzsimons Aug 19 '10 at 15:18

2 Answers2

5

Here is a more recent paper giving a difference between single vs. multiple oracles motivated by cryptography:

Donald Beaver and Joan Feigenbaum. Hiding instances in multioracle queries. STACS 1990. Springer Lecture Notes in Computer Science, 1990, Volume 415/1990, 37-48, DOI: 10.1007/3-540-52282-4_30

Glorfindel
  • 359
  • 1
  • 4
  • 10
Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • just a question, i take it that the concept of multi-oracle only makes sense if the oracles cannot be collapsed into each other for some (perceived?) security reasons? – Ahmed Masud Dec 14 '11 at 09:37
3

Here is an older paper you might find helpful: Logspace Machines with Multiple Oracle Tapes by Nancy Lynch at MIT (PDF). In particular Theorem 2.2, on PDF-page 5, might be the type of thing you're looking for. There's also a section on hierarchies defined by different numbers of oracle tapes per machine.

Disclaimer after the fact: Looks like a similar question and (even more similar) answer were given here.

Community
  • 1
Daniel Apon
  • 6,001
  • 1
  • 37
  • 53