Worldlex Wiki - Un problème de décision est représenté par un ensemble A de nombres naturels (ou de chaînes de caractères ). Une instance de ce problème est un nombre naturel (ou une chaîne de caractères) quelconque. La solution à cette instance est « OUI » si le nombre (ou la chaîne) appartient à l’ensemble, et « NON » sinon.
- Un problème de fonction est représenté par une relation binaire R reliant des nombres naturels (ou des chaînes de caractères) à d' autres nombres naturels (ou chaînes de caractères). Une instance de ce problème est une entrée x de R. Une solution est une valeur associée à x par R.
Une machine oracle peut effectuer toutes les opérations habituelles d'une machine de Turing et peut également interroger l'oracle pour obtenir la solution de n'importe quelle instance du problème de calcul associé à cet oracle. Par exemple, si le problème consiste à déterminer si un ensemble A de nombres naturels est concerné, la machine oracle fournit à l'oracle un nombre naturel, et l'oracle répond par « oui » ou « non » , indiquant si ce nombre appartient à A.
Définitions
Il existe de nombreuses définitions équivalentes des machines de Turing oracles, comme nous le verrons plus loin. Celle présentée ici est tirée de fonction indicatrice de l'ensemble d'oracle est inscrite sur la bande d'oracle à l'aide des symboles 0 et 1. La machine peut alors interroger l'oracle en parcourant la bande jusqu'à la case correspondante et en lisant la valeur qui s'y trouve.
Ces définitions sont équivalentes du point de vue de la calculabilité par une machine de Turing : une fonction est calculable par un oracle donné selon toutes ces définitions si elle l'est selon au moins une d'entre elles. Elles ne sont cependant pas équivalentes du point de vue de la complexité algorithmique . Une définition telle que celle de van Melkebeek, utilisant un ruban d'oracle pouvant posséder son propre alphabet, est généralement nécessaire.
Classes de complexité des machines oracles
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 notée A<sub> L</sub> . Par exemple, P<sub> SAT</sub> 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 satisfaisabilité booléenne . La notation A<sub> B</sub> peut être étendue à un ensemble de langages B (ou à une classe de complexité B ), selon la définition suivante :
Lorsqu'un langage L est complet pour une certaine classe B , alors A <sub>L</sub> = A <sub> B </sub> si les machines de A peuvent 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<sub> SAT</sub> = P<sub> NP</sub> . Cependant, si A = DLOGTIME , alors A <sub>SAT</sub> peut différer de A <sub>NP</sub> . (La définition donnée ci-dessus n'est pas tout à fait standard. Dans certains contextes, comme la démonstration des théorèmes de hiérarchie temps - espace , il est plus utile de supposer que la machine abstraite définissant la classe n'a accès qu'à un seul oracle pour un seul langage. Dans ce contexte, la complétude n'est pas définie si la classe de complexité ne possède aucun problème complet par rapport aux réductions accessibles à A.)
Il est admis que NP ⊆ P NP , mais la question de savoir si NP NP , P NP , NP et P sont égaux reste au mieux hypothétique. On pense qu'ils sont différents, ce qui conduit à la définition de la hiérarchie polynomiale .
Les machines à oracles sont utiles pour étudier la relation entre les classes de complexité P et NP , en considérant la relation entre PA et NP pour un oracle A. En particulier, il a été démontré qu'il existe des langages A et B tels que PA = NP et PB ≠ NP B. [ Le fait que la question P = NP se relativise dans les deux sens est considéré comme une preuve de la difficulté à y répondre, car toute technique de démonstration qui relativise (c'est-à-dire qui n'est pas affectée par l'ajout d'un oracle) ne permettra pas de répondre à la question P = NP. La plupart des techniques de démonstration se relativisent.
On peut considérer le cas où un oracle est choisi aléatoirement parmi tous les oracles possibles (un ensemble infini ). Il a été démontré dans ce cas qu'avec une probabilité de 1, P<sub> A </sub> ≠ NP<sub> A</sub> . 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 se justifie par le fait que les oracles aléatoires ne soutiennent une proposition qu'avec une probabilité de 0 ou 1. (Ceci découle de la loi binaire de Kolmogorov .) Cela ne constitue qu'une preuve faible que P ≠ NP, puisqu'une proposition peut être vraie pour un oracle aléatoire mais fausse pour les machines de Turing ordinaires ; par exemple, IP<sub> A </sub> ≠ P<sub>SPACE</sub> A pour un oracle aléatoire A, mais IP = P<sub>SPACE</sub> .
Oracles et problèmes d'arrêt
Une machine dotée d'un oracle pour le problème de l'arrêt peut déterminer si certaines machines de Turing s'arrêteront pour des entrées particulières, mais elle ne peut pas déterminer, de manière générale, si les machines oracles comme elle (c'est-à-dire équipées d'un oracle pour le problème de l'arrêt) s'arrêteront. Ceci crée une hiérarchie de machines, chacune possédant un oracle d'arrêt plus puissant et un problème d'arrêt plus difficile. Cette hiérarchie de machines permet de définir la hiérarchie arithmétique .