Un oracle est-il jamais utile si vous ne pouvez pas contrôler les instances d'entrée?

Disons $F$ est un oracle pour un problème $\mathbb{NP}$, mais je ne peux pas appeler cet oracle avec une instance d'entrée. Au lieu de cela, chaque fois que j'appelle$F$Je reçois retourné une instance aléatoire et une solution. Ainsi, je sais que$F$ est en fait capable de résoudre arbitrairement $\mathbb{NP}$-des problèmes difficiles, je ne peux pas spécifier celui que je veux résoudre.

Est-il possible d’utiliser un tel oracle pour résoudre un $\mathbb{NP}$-problème plus rapide? Mon instinct dit non parce que l'utilisation naïve de l'oracle nécessite toujours$O(2^n)$temps en appelant l'oracle suffisamment pour vérifier chaque solution. Je ne peux tout simplement pas penser à un moyen de le prouver.

Comme l'a souligné Xodarap, si vous avez besoin que votre algorithme avec «l'oracle aléatoire» produise toujours la bonne réponse, alors l'oracle aléatoire est inutile. Le problème devient plus intéressant si nous permettons une faible probabilité d'erreur (où la probabilité est par rapport à l'instance aléatoire choisie par l'oracle).

De plus, comme l'a souligné Vor dans ses commentaires sur la question, il est inutile de dire «instance aléatoire» sans spécifier de distribution de probabilité. L'une des hypothèses raisonnables à faire ici est que cette instance aléatoire est choisie uniformément au hasard dans l'ensemble de toutes les chaînes de longueur p ( n ), où n est la longueur d'entrée et p est un polynôme fixe. Nous pourrions faire d'autres hypothèses, plus faibles, sur la distribution de probabilité.

Ici, nous ferons l'hypothèse assez générale et montrerons que l'existence d'un algorithme à temps polynomial randomisé avec un «oracle aléatoire» pour les problèmes NP-complets a une conséquence surprenante même sous cette faible hypothèse.

Supprimons l'exigence selon laquelle «l'oracle aléatoire» résoudra un problème dans NP (sur une instance choisie au hasard). Maintenant, «l'oracle aléatoire» peut être n'importe quelle distribution de probabilité prédéterminée sur des chaînes de longueur polynomiale, et chaque fois qu'il est demandé, il émet une chaîne selon cette distribution de probabilité. La seule exigence est que cette distribution de probabilité ne dépend que de la longueur d'entrée. Notez que votre modèle est en effet un cas particulier de ce modèle. Dans votre modèle, la distribution de probabilité doit avoir la forme suivante: elle choisit d'abord une instance uniformément aléatoire y dans un ensemble en fonction de la longueur d'entrée, puis renvoie une paire ( y , g ( y )), où g: {0, 1} * → {0, 1} est la fonction caractéristique d'un problème de décision dans NP. Maintenant, nous autorisons toute distribution de probabilité, tant que la distribution est déterminée par la seule longueur d'entrée.

Un «oracle» de cette forme générale est appelé un conseil randomisé . La classe des problèmes de décision qui peuvent être résolus par un algorithme de temps polynomial randomisé avec un conseil randomisé (avec erreur bilatérale bornée) est appelée BPP / rpoly, et il est connu que cette classe est égale à P / poly . (L'inclusion BPP / rpoly⊆P / poly peut être prouvée de la même manière qu'une inclusion BPP⊆P / poly bien connue. Pour une preuve de ce dernier, voir par exemple le théorème 6.3 de Goldreich [Gol08].)

Cela signifie que si un problème NP-complet peut être résolu dans votre modèle, alors NP⊆P / poly. Cependant, il est connu que NP⊆P / poly implique que la hiérarchie polynomiale s'effondre au deuxième niveau [KW98, Cai07]. La plupart des théoriciens de la complexité considèrent l'effondrement de la hiérarchie polynomiale comme une grande surprise. Si nous pensons que la hiérarchie polynomiale ne s'effondre pas, alors les problèmes NP-complets ne peuvent pas être résolus efficacement avec «l'oracle aléatoire» dans votre sens.

Références

[Cai07] Jin-Yi Cai. S ₂ ^p ⊆ ZPP ^NP . Journal of Computer and System Sciences , 73 (1): 25–35, février 2007. DOI: 10.1016 / j.jcss.2003.07.015 .

[Gol08] Odre Goldreich. Complexité informatique: une perspective conceptuelle . Cambridge University Press, 2008.

[KW98] Johannes Köbler et Osamu Watanabe. Nouvelles conséquences de l'effondrement du NP ayant de petits circuits. SIAM Journal on Computing , 28 (1): 311–324, 1998. DOI: 10.1137 / S0097539795296206 .

Pensons spécifiquement au problème NP-complet préféré de tout le monde: 3SAT.

Il est possible (bien que peu probable) que chaque fois que vous appelez votre oracle, il vous donne une affectation pour la même instance. Plus précisément, chaque fois que cela pourrait vous donner une affectation pour la phrase triviale:

Mais vous connaissez déjà la mission pour cela. Votre Oracle ne peut donc pas être utile.

Plus formellement, si nous appelons votre oracle $A$, puis $P^A\not=NP$ (en supposant $P\not=NP$...)