P / poly

12

P/poly=NP/poly impliqueNPP/poly , qui à son tour a des conséquences intéressantes comme l'effondrement de la hiérarchie polynomiale.

Y a-t-il des implications intéressantes pour P/polyNP/poly ?

Thomas Klimpel
la source
6
P/poly=NP/poly estéquivalentàNPP/poly .
Emil Jeřábek
1
5
@Kaveh: supprimer la motivation est-il vraiment le genre de chose que nous devrions faire? Cela m'a fait découvrir des choses que je n'avais jamais rencontrées auparavant, et ce n'est pas comme si elles n'étaient pas séparées. Ce n'est pas Twitter.
András Salamon
4
@ EmilJeřábek Je pense que je l'ai maintenant. NP P / poly implique P / poly = NP / poly, car l'algorithme déterministe peut obtenir à la fois sa propre chaîne de conseils pour devenir aussi puissant que NP, ainsi que la chaîne de conseils pour la langue de NP / poly, et c'est assez pour décider de cette langue.
Thomas Klimpel
2
@ThomasKlimpel: Oui, exactement.
Emil Jeřábek

Réponses:

10

Le commentaire d'Emil Jeřábek répond à la question:

P / poly NP / poly est équivalent à NP P / poly=

Notez le corollaire

P / poly NP / poly implique P NP.

Preuve de corollaire:

  1. P / poly NP / poly est équivalent à NP P / poly (commentaire d'Emil)= 
  2. NP P / poly implique P / poly NP / poly (sous-entendu par 1.)== 
  3. P / poly NP / poly implique NP P / poly (équivalent à 2.) 
  4. NP P / poly implique P NP (P P / poly) 
  5. P / poly NP / poly implique P NP (sous-entendu par 3. et 4.) 

Preuve du commentaire d'Emil: Il suffit de montrer que NP P / poly implique P / poly NP / poly.==

  1. Supposons donc NP P / poly.
  2. Parce que SAT NP, il existe et une séquence de chaînes de conseils avec , un algorithme déterministe qui peut décider des instances SAT de taille dans le temps , si elle a accès à . WLOG, cet algorithme peut également décider des instances SAT de taille , car nous pouvons définir une séquence modifiée avec , où toutes les chaînes de conseils précédentes sont incluses dans .p S A Tk S A T > 0 s n | s n | n k S A T n n p S A T s nn s n = s n - 1 spSATkSAT>0sn|sn|nkSATnnpSATsnn| s n | n k S A T + 1 s sn=sn1sn|sn|nkSAT+1sn
  3. Soit maintenant NP / poly un langage arbitraire, pour lequel nous devons montrer P / poly. Il existe et une séquence de chaînes de conseils avec et un algorithme non déterministe qui peut décider de instances de taille dans le temps , s'il a accès à .L p Lk L > 0 l n | lLLpLkL>0ln Ln n p L l n|ln|nkLLnnpLln
  4. Pour chaque avec , une instance SAT de taille peut être calculée (en temps ) qui est satisfaisable exactement si .| w |wc n p L O ( n p L ) w L|w|=ncnpLO(npL)wL
  5. Donc pour la séquence de chaînes de conseils avec , la combinaison des algorithmes déterministes de 2. et 4. donne un algorithme déterministe qui peut décider de instances de taille dans le temps , si elle a accès à . | t n | n k L + ( c n p L ) k S A T L n O ( ( c n p L ) p S A T ) t ntn=lnscnpL|tn|nkL+(cnpL)kSATLnO((cnpL)pSAT)tn
  6. Parce que NP / poly était un langage arbitraire, cela montre NP / poly P / poly, sous l'hypothèse que NP P / poly.L

Toutes les preuves ci-dessus se relativisent, car l'existence de problèmes NP-complets est également vraie dans les mondes relativisés. Cela suggère qu'il est vain de rechercher une preuve que P / poly NP / poly. Cependant résumons la section de motivation suppriméede la question comme "La chaîne de conseil pourrait être un système axiomatique formel (automatiquement garanti pour être cohérent, sourire maléfique) dont la force augmente rapidement avec la longueur d'entrée, et NP est extrêmement bon pour exploiter ce conseil." Si l'on ne fait pas très attention à ce que "l'existence d'une séquence de piqûres d'avis" n'ait qu'une signification "formelle" par rapport à un système formel fixe, cette configuration est susceptible de permettre la construction de paradoxes apparents. Mais la construction de tels paradoxes peut néanmoins être amusante, et peut-être même suggérer des moyens de construire des preuves d'indépendance (pour des systèmes formels suffisamment faibles).

Thomas Klimpel
la source