Circuits avec oracles vs Machines de Turing avec oracles

En termes simples: quelle est la correspondance entre les machines de Turing avec oracles et les familles de circuits uniformes avec oracles? Comment ces derniers sont-ils définis afin d'obtenir le même modèle de calcul, pour une machine Oracle Turing donnée?

Cela peut être une question élémentaire, mais il n'est pas évident de savoir où chercher, et je suis le genre de personne qui aime s'assurer que mes fondations utilisent un mortier de bonne qualité. S'il existe une référence standard, veuillez me l'indiquer. (Le livre de Papadimitriou, par exemple, ne semble pas du tout décrire des circuits avec des oracles.)

Mon hypothèse de travail est la suivante: une famille de circuits uniformes avec accès à un oracle (par exemple pour résoudre un problème NP-complet) est définie comme suit:

On définit une famille infinie de "portes d'oracle" O _n , une pour chaque taille de circuit n, chacune calculant une fonction f _n : {0,1} ^cn → {0,1} pour une constante c.
Les fonctions f _n calculées par les portes oracles O _n doivent être "uniformes" dans le sens suivant: pour tout n <N et x ∈ {0,1} ⁿ , nous avons besoin de f _n ( x ) = f _N (0 ^{c ( N − n)} x ) --- c'est-à-dire que les portes oracle doivent utiliser un "encodage" cohérent et extensible de leurs entrées.
On définit alors une famille de circuits uniformes, où les portes oracles sont parmi les opérations autorisées au circuit, restreignant le circuit pour la taille d'entrée n pour utiliser la porte O _n .

J'imagine que certains des choix ci-dessus peuvent être arbitrairement fixés sans perdre aucune généralité. Ce qui m'intéresse, c'est une référence pour la correspondance, ou du moins une description de la façon de modifier la description ci-dessus pour obtenir celle standard.

cc.complexity-theory turing-machines oracles circuit-families Niel de Beaudrap
la source

Puisque je sais que vous travaillez dans l'information quantique, je recommanderais l'enquête de John Watrous sur la complexité de calcul quantique, où il parle également d'oracles dans les circuits quantiques et d'interroger l'oracle en superposition.

Robin Kothari

L'article de Watrous est également une bonne référence. Mais il s'est avéré que j'avais besoin dans ce cas d'être en quelque sorte désabusé de l'idée que n'importe qui voudrait définir une famille de circuits relativisés d'une manière qui ne correspondrait pas au simple test du même prédicat pour différentes longueurs de chaîne finies, en étant a rappelé que la sémantique d'un oracle est classiquement d'indiquer l'appartenance à un ensemble. Il s'est avéré que des dessins de portes de circuit avec les symboles "∈A?" sur eux était tout ce dont j'avais besoin.

Niel de Beaudrap

Réponses:

La meilleure référence pour les circuits relativisés est l'article de Chris Wilson "Relativized NC" http://www.springerlink.com/content/u727654246wu8662/

La deuxième condition que vous avez (fermeture vers le bas de O_n) n'est pas nécessaire pour obtenir l'équivalence, par exemple, entre P ^ O et les circuits de taille uniforme avec l'oracle O. De plus, votre troisième condition doit être jetée, la taille du circuit empêchera l'accès à O_m pour m plus grand que la taille du circuit.

Lance Fortnow
la source

Il n'y a aucun commentaire explicite dans l'article de Wilson sur les portes d'oracle elles-mêmes; mais rétrospectivement, si vous prenez l'oracle au sérieux comme représentant l'appartenance à un ensemble de chaînes booléennes comme avec les MT, alors ma deuxième condition est simplement un non-problème (c'est-à-dire qu'il va sans dire). Par votre observation du superflu de ma troisième condition, il suffit alors d'avoir une famille infinie de portes qui décident de l'appartenance à A pour toute taille de chaîne finie particulière. Ça marche pour moi; J'aurais aimé y avoir pensé plus tôt.

Niel de Beaudrap

Remarques à l'intention des spectateurs occasionnels --- L'article de Wilson définit la contribution en profondeur d'une porte oracle sur k bits à ceil (log k), en analogie apparente avec les travaux antérieurs de Cook ("Une taxonomie de problèmes avec des algorithmes parallèles rapides" , Inform. And Control, 64). Il y a un problème technique de savoir s'il faut autoriser les requêtes oracle dans le processus de construction des circuits eux-mêmes (dont chacun peut également utiliser des oracles): il fait remarquer que cela ne semble pas avoir d'importance. En fin de compte, cependant, il est insatisfait de l'existence de A pour lequel NC_1 ^ A n'est pas contenu dans NSPACE ^ A (O (n ^ k)), pour toute constante k.

Niel de Beaudrap