10
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ 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? $\endgroup$
    – Niel de Beaudrap
    Commented Aug 18, 2010 at 16:56
  • $\begingroup$ 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. $\endgroup$
    – Joe Fitzsimons
    Commented Aug 18, 2010 at 17:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Marcos Villagra
    Commented Aug 18, 2010 at 23:37
  • 1
    $\begingroup$ I'm with Marcos's comment about the strongest oracle subsuming the others.. but I'm interested what you had in mind now! $\endgroup$
    – Daniel Apon
    Commented Aug 19, 2010 at 4:22
  • 1
    $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Aug 19, 2010 at 13:08

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Ahmed Masud
    Commented Dec 14, 2011 at 9:37
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.