Existe-t-il une référence définitive pour les machines Turing avec plusieurs bandes oracle?

10

La plupart de la littérature semble s'intéresser aux machines à oracles simples pour des problèmes spécifiques, mais il semble y avoir quelques articles qui considèrent les machines à oracles multiples. Existe-t-il un bon article ou une thèse qui donne un aperçu de ce que l'on sait de ces machines? Je m'intéresse en particulier à P avec plusieurs oracles.

oracles turing-machines Joe Fitzsimons
la source
3
Si vous ne voulez qu'un nombre fini N d'oracles, vous pouvez définir un oracle composé N-en-1 en utilisant les premiers bits de log (N) de l'oracle composé pour indiquer le sous-oracle que vous souhaitez interroger. Suis-je en train de manquer quelque chose?
Niel de Beaudrap du
Oui, j'y avais pensé. Cependant, je m'intéresse à des ensembles spécifiques d'oracles, et il semble donc plus naturel de les considérer séparément que comme un objet composé. J'ai pensé qu'il y aurait peut-être de bons résultats dans cette direction.
Joe Fitzsimons
1
juste pour la curiosité, le fait d'avoir plusieurs oracles ajoute-t-il plus de puissance de calcul par rapport à une seule machine oracle? Il me semble que non, car vous prenez simplement l'oracle correspondant à la langue dans la classe de complexité la plus élevée. De plus, le fait d'avoir un nombre fixe d'oracles ralentira la machine d'une constante.
Marcos Villagra
1
Je suis avec le commentaire de Marcos sur l'oracle le plus fort subsumant les autres .. mais je suis intéressé par ce que vous aviez en tête maintenant!
Daniel Apon
1
Envisagez-vous d'autoriser une infinité d'oracles, où la MT est autorisée à choisir l'oracle à interroger? Avec une telle configuration, il pourrait y avoir une différence intéressante entre un ensemble d'oracles dans lequel chacun était strictement plus faible qu'un autre oracle Q, et Q lui-même.
András Salamon

Réponses:

5

Voici un article plus récent donnant une différence entre un seul et plusieurs oracles motivés par la cryptographie:

Donald Beaver et Joan Feigenbaum. Masquage des instances dans les requêtes multiracle . STACS 1990. Springer Lecture Notes in Computer Science, 1990, Volume 415/1990, 37-48, DOI: 10.1007 / 3-540-52282-4_30

Joshua Grochow
la source
juste une question, je suppose que le concept de multi-oracle n'a de sens que si les oracles ne peuvent pas s'effondrer les uns dans les autres pour des raisons de sécurité (perçues?)?
Ahmed Masud
3

Voici un article plus ancien que vous pourriez trouver utile: Logspace Machines with Multiple Oracle Tapes par Nancy Lynch au MIT ( PDF ). En particulier, le théorème 2.2, sur la page PDF 5, pourrait être le type de chose que vous recherchez. Il existe également une section sur les hiérarchies définies par différents nombres de bandes oracle par machine.

Avis de non-responsabilité après le fait: ressemble à une question similaire et (encore plus similaire) réponse a été donnée ici .

Daniel Apon
la source