Machine Oracle

En théorie de la complexité et en théorie de la calculabilité , une machine oracle est une machine abstraite utilisée pour étudier les problèmes de décision . Elle peut être visualisée comme une machine de Turing avec une boîte noire , appelée oracle , qui est capable de résoudre certains problèmes en une seule opération. Le problème peut être de n'importe quelle classe de complexité . Même les problèmes indécidables , tels que le problème d'arrêt , peuvent être utilisés.

Une machine oracle peut être conçue comme une machine de Turing connectée à un oracle . L'oracle, dans ce contexte, est une entité capable de résoudre un problème, qui peut par exemple être un problème de décision ou un problème de fonction . Le problème n'a pas besoin d'être calculable ; l'oracle n'est pas supposé être une machine de Turing ou un programme informatique. L'oracle est simplement une « boîte noire » capable de produire une solution pour toute instance d'un problème de calcul donné :

• Un problème de décision est représenté par un ensemble A de nombres naturels (ou de chaînes). Une instance du problème est un nombre naturel arbitraire (ou une chaîne). La solution de l'instance est « OUI » si le nombre (la chaîne) est dans l'ensemble, et « NON » dans le cas contraire.
• Un problème de fonction est représenté par une fonction f de nombres naturels (ou de chaînes) vers des nombres naturels (ou des chaînes). Une instance du problème est une entrée x pour f . La solution est la valeur f ( x ).

Une machine oracle peut effectuer toutes les opérations habituelles d'une machine de Turing et peut également interroger l'oracle pour obtenir une solution à n'importe quelle instance du problème de calcul pour cet oracle. Par exemple, si le problème est un problème de décision pour un ensemble A de nombres naturels, la machine oracle fournit à l'oracle un nombre naturel et l'oracle répond par « oui » ou « non » en indiquant si ce nombre est un élément de A .

Il existe de nombreuses définitions équivalentes des machines de Turing oracle, comme indiqué ci-dessous. Celle présentée ici est tirée de van Melkebeek (2003, p. 43).

Une machine oracle, comme une machine de Turing, comprend :

• une bande de travail : une séquence de cellules sans début ni fin, chacune pouvant contenir un B (pour blanc) ou un symbole de l'alphabet de la bande ;
• une tête de lecture/écriture , qui repose sur une seule cellule de la bande de travail et peut y lire les données, écrire de nouvelles données et incrémenter ou décrémenter sa position le long de la bande ;
• un mécanisme de contrôle , qui peut se trouver dans un nombre fini d' états , et qui effectuera différentes actions (lecture de données, écriture de données, déplacement du mécanisme de contrôle et changement d'état) en fonction de l'état actuel et des données en cours de lecture.

En plus de ces composants, une machine oracle comprend également :

• une bande Oracle , qui est une bande semi-infinie séparée de la bande de travail. L'alphabet de la bande Oracle peut être différent de celui de la bande de travail.
• une tête oracle qui, comme la tête de lecture/écriture, peut se déplacer vers la gauche ou vers la droite le long de la bande oracle pour lire et écrire des symboles ;
• deux états spéciaux : l'état ASK et l'état RESPONSE.

De temps à autre, la machine Oracle peut entrer dans l'état ASK. Lorsque cela se produit, les actions suivantes sont effectuées en une seule étape de calcul :

• le contenu de la bande oracle est considéré comme une instance du problème de calcul de l'oracle ;
• l'oracle est consulté et le contenu de la bande oracle est remplacé par la solution à cette instance du problème ;
• la tête de l'oracle est déplacée vers la première case de la bande de l'oracle ;
• l'état de la machine oracle est changé en RÉPONSE.

L’effet du passage à l’état ASK est donc de recevoir, en une seule étape, une solution à l’instance du problème qui est écrite sur la bande oracle.

Il existe de nombreuses définitions alternatives à celle présentée ci-dessus. Beaucoup d'entre elles sont spécialisées dans le cas où l'oracle résout un problème de décision. Dans ce cas :

• Certaines définitions, au lieu d'écrire la réponse sur la bande oracle, ont deux états spéciaux OUI et NON en plus de l'état ASK. Lorsque l'oracle est consulté, l'état suivant est choisi comme OUI si le contenu de la bande oracle est dans l'ensemble oracle, et choisi comme NON si le contenu n'est pas dans l'ensemble oracle.
• Certaines définitions évitent la bande Oracle séparée. Lorsque l'état Oracle est saisi, un symbole de bande est spécifié. L'Oracle est interrogé avec le nombre de fois que ce symbole de bande apparaît sur la bande de travail. Si ce nombre est dans l'ensemble Oracle, l'état suivant est l'état OUI ; s'il ne l'est pas, l'état suivant est l'état NON.
• Une autre définition alternative rend la bande Oracle en lecture seule et élimine entièrement les états ASK et RESPONSE. Avant le démarrage de la machine, la fonction d'indicateur de l'ensemble Oracle est écrite sur la bande Oracle à l'aide des symboles 0 et 1. La machine est alors capable d'interroger l'Oracle en parcourant la case correcte de la bande Oracle et en lisant la valeur qui s'y trouve.

Ces définitions sont équivalentes du point de vue de la calculabilité de Turing : une fonction est calculable par oracle à partir d'un oracle donné sous toutes ces définitions si elle est calculable par oracle sous l'une d'entre elles. Les définitions ne sont cependant pas équivalentes du point de vue de la complexité computationnelle. Une définition telle que celle de van Melkebeek, utilisant une bande oracle qui peut avoir son propre alphabet, est en général nécessaire.

La classe de complexité des problèmes de décision résolubles par un algorithme de classe A avec un oracle pour un langage L est appelée A ^L . Par exemple, P ^SAT est la classe des problèmes résolubles en temps polynomial par une machine de Turing déterministe avec un oracle pour le problème de satisfiabilité booléenne . La notation A ^B peut être étendue à un ensemble de langages B (ou à une classe de complexité B), en utilisant la définition suivante :

Lorsqu'un langage L est complet pour une classe B, alors A ^L = A ^B à condition que les machines de A puissent exécuter les réductions utilisées dans la définition de complétude de la classe B. En particulier, puisque SAT est NP-complet par rapport aux réductions en temps polynomial, P ^SAT = P ^NP . Cependant, si A = DLOGTIME , alors A ^SAT peut ne pas être égal à A ^NP . (La définition de donnée ci-dessus n'est pas complètement standard. Dans certains contextes, comme la preuve des théorèmes de hiérarchie temporelle et spatiale , il est plus utile de supposer que la machine abstraite définissant la classe n'a accès qu'à un seul oracle pour un langage. Dans ce contexte, n'est pas définie si la classe de complexité n'a pas de problèmes complets par rapport aux réductions disponibles pour .)

Il est entendu que NP ⊆ P ^NP , mais la question de savoir si NP ^NP , P ^NP , NP et P sont égaux reste au mieux provisoire. On pense qu'ils sont différents, et cela conduit à la définition de la hiérarchie polynomiale .

Les machines Oracle sont utiles pour étudier la relation entre les classes de complexité P et NP , en considérant la relation entre P ^A et NP ^A pour un oracle A. En particulier, il a été démontré qu'il existe des langages A et B tels que P ^A = NP ^A et P ^B ≠ NP ^B. Le fait que la question P = NP relativise dans les deux sens est considéré comme une preuve que répondre à cette question est difficile, car une technique de preuve qui relativise ( c'est-à-dire non affectée par l'ajout d'un oracle) ne répondra pas à la question P = NP. La plupart des techniques de preuve relativisent.

On peut considérer le cas où un oracle est choisi au hasard parmi tous les oracles possibles (un ensemble infini). Il a été démontré dans ce cas qu'avec une probabilité de 1, P ^A ≠NP ^A . Lorsqu'une question est vraie pour presque tous les oracles, on dit qu'elle est vraie pour un oracle aléatoire . Ce choix de terminologie est justifié par le fait que les oracles aléatoires ne supportent une affirmation qu'avec une probabilité de 0 ou 1. (Cela découle de la loi zéro-un de Kolmogorov .) Ce n'est qu'une faible preuve que P≠NP, puisqu'une affirmation peut être vraie pour un oracle aléatoire mais fausse pour les machines de Turing ordinaires ; par exemple, IP ^A ≠PSPACE ^A pour un oracle aléatoire A mais IP = PSPACE .

Une machine dotée d'un oracle pour le problème d'arrêt peut déterminer si des machines de Turing particulières s'arrêteront sur des entrées particulières, mais elle ne peut pas déterminer, en général, si des machines équivalentes à elle-même s'arrêteront. Cela crée une hiérarchie de machines, chacune avec un oracle d'arrêt plus puissant et un problème d'arrêt encore plus difficile. Cette hiérarchie de machines peut être utilisée pour définir la hiérarchie arithmétique .

En cryptographie , les oracles sont utilisés pour argumenter la sécurité des protocoles cryptographiques où une fonction de hachage est utilisée. Une réduction de sécurité pour le protocole est donnée dans le cas où, au lieu d'une fonction de hachage, un oracle aléatoire répond à chaque requête de manière aléatoire mais cohérente ; l'oracle est supposé être disponible pour toutes les parties, y compris l'attaquant, comme l'est la fonction de hachage. Une telle preuve montre qu'à moins que l'attaquant ne résolve le problème difficile au cœur de la réduction de sécurité, il doit utiliser une propriété intéressante de la fonction de hachage pour casser le protocole ; il ne peut pas traiter la fonction de hachage comme une boîte noire (c'est-à-dire comme un oracle aléatoire).