Quelle est la simulation connue la plus rapide de BPP utilisant des algorithmes de Las Vegas?

$\mathsf{BPP}$ et $\mathsf{ZPP}$ sont deux des classes de complexité probabiliste de base.

$\mathsf{BPP}$ est la classe de langages décidée par les algorithmes de Turing à temps polynomial probabiliste où la probabilité que l'algorithme renvoie une réponse incorrecte est limitée, c'est-à-dire que la probabilité d'erreur est au plus $\frac{1}{3}$ (pour les instances OUI et NON).

D'un autre côté, les algorithmes $\mathsf{ZPP}$ peuvent être considérés comme ces algorithmes probabilistes qui ne renvoient jamais une réponse incorrecte, chaque fois qu'ils renvoient une réponse, elle est correcte. Cependant, leur durée de fonctionnement n'est pas limitée par un polynôme, ils s'exécutent dans le polynôme attendu.

Soit $\mathsf{ZPTime}(f)$ la classe de langage décidée par des algorithmes probabilistes avec une probabilité d'erreur nulle et un temps d'exécution attendu $f$ . Ils sont également appelés algorithmes de Las Vegas et $\mathsf{ZPP} = \mathsf{ZPTime}(n^{O(1)})$ .

Ma question est quelle est la meilleure simulation connue des algorithmes $\mathsf{BPP}$ utilisant les algorithmes de Las Vegas? Pouvons-nous les simuler en temps attendu sous-exponentiel? Y a-t-il une amélioration connue par rapport à la simulation de force brute triviale qui prend un temps exponentiel?

Plus formellement, savons-nous si ou $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{O(n^{\epsilon})})$ pour certains ? $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{n-n^{\epsilon}})$ $\epsilon>0$

cc.complexity-theory complexity-classes randomness randomized-algorithms echuly
la source

Quelle est n, la longueur de l'entrée? Pourquoi pouvons-nous accepter en

2^{n}

$2^n$

domotorp

est la même chose que

2^{p o l y (n) - n^{ϵ}}

$2^{\mathrm{poly}(n)-n^\epsilon}$

2^{p o l y (n)}

$2^{\mathrm{poly}(n)}$

Emil Jeřábek

Je trouve la question assez intéressante. J'ai édité la question pour la rendre plus lisible et précise. N'hésitez pas à modifier davantage. ps: Je suppose que vous vouliez probablement prendre en compte le nombre polynomial de bits aléatoires utilisés par l'algorithme BPP comme paramètre pour le temps de simulation, mais comme Emil le souligne, ce que vous avez écrit donne

. Si vous voulez que vous deviez remplacer BPP par une classe particulière d'algorithmes probabilistes d'erreur bornée qui ont un paramètre pour le nombre de bits aléatoires utilisés par l'algorithme.

2^{p o l y (n)}

$2^{poly(n)}$

Kaveh

Vous pouvez demander si nous pouvons simuler un algorithme BPP qui utilise

bits aléatoires dans

puisque la simulation par force brute s'exécute en

r (n)

$r(n)$

Z P T i m e (2^{r (n) - n^{ϵ}} n^{O (1)})

$\mathsf{ZPTime}(2^{r(n)-n^\epsilon}n^{O(1)})$

2^{r (n)} n^{O (1)}

$2^{r(n)}n^{O(1)}$ fois.

Kaveh

Réponses:

Tout d' abord, d' observer que , si pour une constante , alors . (Preuve par une hiérarchie temporelle non déterministe.) Il serait donc important de prouver une telle inclusion, non seulement parce qu'il s'agit d'une simulation améliorée, mais aussi de la première avancée sur des bornes inférieures temporelles randomisées depuis des décennies. $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ $c$ $\mathsf{BPP} \neq \mathsf{NEXP}$

Ensuite, considérons la classe $\mathsf{PromiseBPP}$ , pour laquelle le problème suivant est " -hard": $\mathsf{PromiseBPP}$

Problème de probabilité d'approximation de circuit (CAPP): Étant donné un circuit , émettez la probabilité d'acceptation de $C$ àintérieurune facteur additif. $C$ $1/6$

Les résultats d'Impagliazzo, Kabanets et Wigderson 2002 impliquent qu'un algorithme de temps zéro à pour CAPP (où est la taille de ) impliquerait . Dans STOC'10, j'ai étendu ceci pour montrer: en supposant que pour chaque avec bits d'entrée et taille, on peut calculer CAPP de manière non déterministe (donc, zéro erreur suffit) en $2^{n^{\varepsilon}}$ $n$ $C$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ $C$ $k$ $n$ temps, puis . C'est-à-dire qu'il y a certainement des problèmes calculables avec le caractère aléatoire à deux erreurs, pour lesquels des algorithmes à zéro erreur qui battent même légèrement la recherche exhaustive impliqueraient des limites inférieures de circuit. Je crois que cela devrait être interprété comme une méthode possible pour prouver les limites inférieures; Votre kilométrage peut varier. $2^{k-\omega(\log k)}\mathrm{poly}(n)$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$

Notez que même prouver est également ouvert, et prouver cela impliquerait également des limites inférieures: par Kabanets et Impagliazzo 2004, si le test d'identité polynomiale (un problème de ) est dans pour tous les . Récemment (à venir dans STOC'13), j'ai prouvé sans condition que soit $\mathsf{RP} \subseteq \mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\mathsf{coRP}$ $\mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ , alors nous avons des bornes inférieures pour le permanent ou $\varepsilon > 0$ $\mathsf{NEXP}$ ou $\mathsf{BPP} \subseteq \mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^{\varepsilon}$ a circuits de taille , s'appuyant sur la méthode du "témoin facile" des Kabanets. Cela implique deux choses: $\mathsf{RTIME}[2^n]$ $n^c$

Il y a un tel que pour tout , est inconditionnellement dans - il s'agit de la meilleure dérandomisation inconditionnelle de $c$ $\varepsilon > 0$ $\mathsf{RP}$ $\mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^c$ dans que nous connaissons jusqu'à présent. $\mathsf{RP/BPP}$ $\mathsf{ZPP}$
Pour commencer à obtenir des simulations sous-exponentielles intéressantes de , il suffit "de" supposer $\mathsf{BPP}$ n'a pas de circuits de taille polynomiale fixe. $\mathsf{RTIME}[2^n]$

Ryan Williams
la source

Merci à Niel d'avoir pris le temps de rendre ma réponse lisible :)

Ryan Williams

Ryan, je pense que je suis sur le point de poser une question très stupide, mais c'est parti: dans votre première phrase, pourquoi avez-vous besoin de "pour tous

"? Le sous-ensemble BPP de ZPTIME (2 ^ (n ^ c)) pour certains c fixes implique-t-il un sous-ensemble BPP de RTIME (2 ^ (n ^ c)) et donc NTIME (2 ^ (n ^ c)), donc BPP est différent de NEXP ou sinon NTIME (2 ^ (2n ^ c)) est un sous-ensemble de NTIME (2 ^ (n ^ c))?

ϵ

$\epsilon$

Sasho Nikolov

Pas du tout stupide - en effet,

pour certains

est suffisant pour

, merci de l'avoir signalé. Les algorithmes de temps sous-exponentiels sont cependant nécessaires pour les autres conséquences.

B P P \subseteq N T I M E (2^{n^{c}})

$BPP \subseteq NTIME(2^{n^c})$

c

$c$

B P P \neq N E X P

$BPP \neq NEXP$

Ryan Williams

Ryan: Si je voulais comprendre votre article, quel livre / articles sur la complexité des circuits recommandez-vous de connaître?

T ....

Salut Arul, heureusement, Bill Gasarch m'a posé cette question il y a quelque temps et a mis en place la page Web suivante de liens: cs.umd.edu/~gasarch/ryan/ryan.html

Ryan Williams

Cela dépend des hypothèses que vous êtes prêt à faire.

Dans certaines hypothèses de dureté, à savoir , on obtient que . Cela implique notamment que , et donc que chaque langue $E \not\subseteq SIZE(2^{\varepsilon n})$ $P = BPP$ $BPP = ZPP$ $L \in BPP$ est acceptée par une machine de Las Vegas (voir "P = BPP sauf si E a des circuits sous-exponentiels: dérandomisation du lemme XOR", par Impagliazzo et Wigderson).

Vous pouvez également faire une hypothèse de dureté plus douce, à savoir que , et obtenir que (voir le lemme 46 dans "A la recherche d'un témoin facile: Temps exponentiel vs temps polynomial probabiliste "par Impagliazzo, Kabanets et Wigderson). $ZPE \not\subseteq \rm{io-DTIME}(2^{\varepsilon n})$ $BPP = ZPP$

Ou Meir
la source

À moins de progrès dans la dérandomisation, il me semble que l'exigence selon laquelle la machine de Las Vegas ne fait aucune erreur est cruciale, de sorte qu'il y a peu ou pas d'avantages à avoir un caractère aléatoire dans ce cas.

Pour un langage BPP décidé par un algorithme approprié , qui agit sur les entrées et une chaîne aléatoire représentant ses choix aléatoires, le critère d'erreur nulle implique que la machine de Las Vegas doit déterminer avec certitude lequel des deux cas $L$ $A$ $x \in \{0,1\}^n$ $r \in \{0,1\}^{N(n)}$ prises. Si on ne nous donne pas plus d'informations sur, alors c'est essentiellement un problème de promesse d'oracle: étant donné un oraclecalculant, et étant donné la promesse quedonne une sortiepour au moins deux fois plus d'entrées que la sortie opposée, déterminez quelle sortie est la plus courante.

\underset{r}{Pr} (A accepts (x, r)) ⩾ \frac{2}{3} or \underset{r}{Pr} (A accepts (x, r)) ⩽ \frac{1}{3}

$\Pr_r(\text{$A$ accepts $(x,r)$}) \geqslant \tfrac{2}{3} \quad\text{or}\quad \Pr_r(\text{$A$ accepts $(x,r)$}) \leqslant \tfrac{1}{3}$

A

$A$

A^{'}

$A'$

A^{'} (r) = A (x, r)

$A'(r) = A(x,r)$

A^{'}

$A'$

a \in {0, 1}

$a \in \{0,1\}$

1 - a

$1-a$

Bien que la machine de Las Vegas puisse utiliser des techniques aléatoires, si nous sommes en effet obligés de traiter comme un oracle, nous pouvons voir que la seule stratégie disponible pour une machine de Las Vegas est de faire un examen relativement approfondi (mais non exhaustif) de la chaînes aléatoires , pour voir quelle réponse est donnée pour chacun. Il ne peut être sûr que s'il trouve plus de $A'$ $r$ chaînes distinctes qui donnent toutes la même sortie; sinon, avec une probabilité faible (mais non nulle!), il peut être malchanceux et obtenir un échantillon non représentatif des sorties possibles. Pour obtenir zéro erreur, il doit échantillonner au moins $2^{N(n)}\!/3$ $r$ entrées . $2^{N(n)}\!/3$ $r$

Parce que la machine de Las Vegas doit inspecter au moins une fraction constante de toutes les chaînes aléatoires possibles , asymptotiquement nous ne sommes pas mieux lotis que si nous testions de manière déterministe toutes les chaînes aléatoires possibles. Nous ne tirons aucun avantage asymptotique de la simulation aléatoire d'algorithmes BPP dans un paramètre sans erreur, au-delà de ce que nous pouvons faire de manière déterministe par force brute. $r$

Notez que ce même argument donne lieu à une séparation oracle entre BPP et ZPP , c'est -à- dire qu'il existe un oracle tel que car l' algorithme ZPP prend un temps exponentiel, tandis qu'un algorithme BPP peut résoudre la question de l'oracle en une seule requête et réussir avec une erreur bornée. Cependant, cela ne vous dit rien de plus que ce que vous soupçonniez déjà (que le surcoût de la simulation peut être pire que le polynôme) ni que les asymptotiques sont tout aussi mauvaises qu'une simulation déterministe naïve. $A$

{Z P P}^{A} ⫋ {B P P}^{A}

$\mathsf{ZPP}^A \subsetneqq \mathsf{BPP}^A$

Niel de Beaudrap
la source

corrigez-moi si je me trompe: vous donnez un raisonnement intuitif pourquoi la dérandomisation semble impossible, mais nous savons que, selon certaines hypothèses raisonnables, BPP, ZPP et P sont tous la même chose. pour que l'intuition ne soit pas nécessairement bonne

Sasho Nikolov

Pas du tout. La dérandomisation serait probablement un aperçu de la façon de simuler le BPP par P , n'est-ce pas? Je viens de décrire comment, s'il veut des résultats inconditionnels qui n'exploitent pas la structure de l'algorithme lui-même, il peut aussi bien effectuer une simulation déterministe qu'une simulation aléatoire à zéro erreur. Ou y a-t-il un problème avec cette explication?

Niel de Beaudrap

Je pense que tout ce que vous dites est que la simulation de force brute naïve de BPP par ZPP n'est pas beaucoup plus rapide que la simulation de force brute naïve de BPP par P. mais je ne vois pas ce que cela est censé montrer. pour moi, c'est comme si quelqu'un demandait «quel est l'algorithme le plus rapide pour trouver une correspondance maximale» et obtenait une réponse «eh bien, à défaut de comprendre la structure des correspondances, c'est le temps exponentiel». la question est de savoir s'il existe un aperçu connu de la structure du BPP qui rend possible une simulation ZPP efficace

Sasho Nikolov

@SashoNikolov: Ce n'était pas vraiment censé être un aperçu profond. D'après le libellé de la question, il m'a semblé être limite pour migrer vers CS.SE. J'ai décidé d'y répondre littéralement, à savoir: à notre connaissance , le temps d'exécution attendu le plus efficace de Las Vegas Machine qui accepte un langage L∈BPP n'est pas beaucoup mieux qu'une machine déterministe qui explore les possibilités de la force brute. Les réponses qui disent qu'il pourrait y avoir une limite supérieure polynomiale si certaines conditions sont excellentes et instructives, et je les vote pour cela; mais je réponds à la vraie question.

Niel de Beaudrap

Je pense que c'est une bonne réponse (également plus lisible maintenant après l'édition). Nous n'avons pas de résultat conditionnel comme "P = ZPP implique P = BPP" ou "ZPP = BPP implique P = BPP", il est donc toujours possible de simuler BPP par des algorithmes ZP plus rapidement qu'avec des algorithmes déterministes. Cependant, le résultat de la relativisation semble impliquer que cela ne peut se produire par aucune simulation de relativisation, est-ce que je comprends bien?

Kaveh