Compréhension concrète de la différence entre les définitions PP et BPP

9

Je suis confus quant à la façon dont PP et BPP sont définis. Supposons χ est la fonction caractéristique d'un langage L . M être la machine de Turing probabiliste. Les définitions suivantes sont-elles correctes:
P P = { L : P r [ χ ( x ) M ( x ) ] > 1BPP={L:Pr[χ(x)M(X)]12+ϵXL, ϵ>0}
PP={L:Pr[χ(X)M(X)]>12}

Si la définition est incorrecte, veuillez essayer de faire des changements minimes pour les corriger (c.-à-d. Ne pas donner une autre définition équivalente qui utilise une machine de comptage ou un modèle modifié). Je ne peux pas distinguer correctement les conditions de probabilité sur les deux définitions.

Quelques exemples concrets avec un aperçu clair des points subtils seraient très utiles.

DurgaDatta
la source

Réponses:

10

Cela me semble correct. La différence entre BPP et PP est que , pour BPP la probabilité doit être supérieure à 1/2 par une constante , alors que pour PP , il pourrait être 1/2+1/2n . Donc, pour les problèmes BPP, vous pouvez faire une amplification de probabilité avec un petit nombre de répétitions, alors que pour les problèmes PP généraux, vous ne pouvez pas.

adrianN
la source
12

La réponse de Vor donne la définition standard. Permettez-moi d'essayer d'expliquer la différence un peu plus intuitivement.

Soit M un algorithme à temps polynomial probabiliste d'erreur bornée pour un langage L qui répond correctement avec une probabilité d'au moins p12+δ. SoitXl'entrée etnla taille de l'entrée.

Ce qui distingue un arbitraire algorithme à partir d' un B P P algorithme est l' écart positif entre la probabilité d'accepter x L et la probabilité d'acceptation x L . PPBPPXLXLL'essentiel de est que l'écart est au moins n - O ( 1 ) . Je vais essayer d'expliquer pourquoi cette distinction est significative et permet de considérer B P P comme des algorithmes efficaces (même conjecturés pour être égaux à PBPPnO(1)BPPP) alors que est considéré comme inefficace (en fait P P contient N P ). Tout cela vient de cet écart.PPPPNP

Commençons par regarder plus attentivement.PP

Notez que si un algorithme utilise au plus bits aléatoires pendant son exécution et que la probabilité d'erreur est inférieure à 2 - r ( n ) alors la probabilité d'erreur est en fait de 0 , il ne peut y avoir de choix de bits aléatoires qui rendront l'algorithme répondre incorrectement.r(n)2r(n)0

De plus, un algorithme avec un temps d'exécution ne peut pas utiliser plus de t ( n ) bits aléatoires, donc si l'erreur d'un algorithme probabiliste avec le pire temps d'exécution t ( n ) est meilleure quet(n)t(n)t(n)

Avec un argument similaire, nous pouvons montrer que le cas où la différence entre la probabilité d'accepter un et la probabilité d'accepter un x L est trop petite est similaire au cas où nous n'avons presque pas de différence comme dans P P cas.xLxLPP

Allons maintenant en voie .BPP

Dans les algorithmes probabilistes, nous pouvons augmenter la probabilité de répondre correctement. Disons que nous voulons augmenter la probabilité de correction à pour une probabilité d'erreur ϵ = 2 - n (erreur exponentiellement petite).1ϵϵ=2n

L'idée est simple: lancez plusieurs fois et prenez la réponse de la majorité.M

Combien de fois faut-il exécuter pour que la probabilité d'erreur soit au plus ϵ ? Θ ( δ - 1 lg ϵ ) fois. La preuve est donnée au bas de cette réponse.MϵΘ(δ1lgϵ)

Prenons maintenant en considération que les algorithmes dont nous discutons doivent être polynomiaux. Cela signifie que nous ne pouvons pas exécuter plus de plusieurs fois de façon polynomiale. En d'autres termes, Θ ( δ - 1 ln ϵ ) = n O ( 1 ) , ou plus simplementMΘ(δ1lnϵ)=nO(1)

δ1lgϵ=nO(1)

Cette relation classe les algorithmes probabilistes d'erreur bornée en classes en fonction de leur probabilité d'erreur. Il n'y a pas de différence entre la probabilité d'erreur étant 2 - n ou une constante positive (c'est-à-dire ne change pas avec n ) ou 1ϵ2nn. On peut passer de l'un à l'autre tout en restant dans le temps polynomial.12nO(1)

Toutefois , si est trop petit, disons 0 , 2 - n , ou même n - ω ( 1 ) nous n'avons pas une façon de renforcer la probabilité exactitude et de réduire la probabilité d'erreur suffisamment pour entrer dans B P P .δ02nnω(1)BPP

Le point principal ici est que dans nous pouvons réduire efficacement la probabilité d'erreur de façon exponentielle, nous sommes donc presque certains des réponses et c'est ce qui nous fait considérer cette classe d'algorithmes comme des algorithmes efficaces. La probabilité d'erreur peut être réduite à tel point qu'une défaillance matérielle est plus probable ou même qu'un météore tombant sur l'ordinateur est plus probable que de commettre une erreur par l'algorithme probabiliste.BPP

Ce n'est pas vrai pour , nous ne savons pas comment réduire la probabilité d'erreur et nous nous retrouvons presque comme si nous répondions en lançant une pièce pour obtenir la réponse (nous ne sommes pas complètement, les probabilités ne sont pas à moitié et moitié, mais il est très proche de cette situation).PP


Cette section donne la preuve que pour obtenir la probabilité d'erreur lorsque l'on part d'un algorithme avec gap ( 1ϵnous devrions exécuterMΘ(δ-1lgϵ)fois.(12δ,12+δ)M Θ(δ1lgϵ)

Soit l'algorithme qui exécute M pendant k fois, puis répond selon la réponse de la majorité. Pour simplifier, supposons que k est impair, donc nous n'avons pas de liens.NkMkk

Prenons le cas que . Le cas x L est similaire. Alors P r { M ( x )  accepte } = p 1xLxL Pour analyser la probabilité d'exactitude deNk,nous devons estimer la probabilité que la majorité deskexécutions acceptent.

Pr{M(x) accepts}=p12+δ
Nkk

Soit Xje 1 si le ème passage accepte et 0 s'il le rejette. Notez que chaque exécution est indépendante des autres car elles utilisent des bits aléatoires indépendants. Ainsi, X i s sont des variables aléatoires booléennes indépendantes où E [ X i ] = P r { X i = 1 } = P r { M ( x )  accepte } = p 1je0Xje

E[Xje]=Pr{Xje=1}=Pr{M(X) accepte}=p12+δ

Soit . Nous devons estimer la probabilité que la majorité accepte, c'est-à-dire la probabilité que Y kOui=Σje=1kXje .Ouik2

Pr{Nk(X) accepte}=Pr{Ouik2}

Comment faire? Nous pouvons utiliser la borne de Chernoff qui nous indique la concentration de probabilité proche de la valeur attendue. Pour toute variable aléatoire de valeur attendue μ , nous avonsZμ

Pr{|Z-μ|>αμ}<eα24μ

ZαμμαY<k2

E[Y]=E[Σi=1kXi]=Σi=1kE[Xi]=kpk2+kδ

Y<k2|Y(k2+kδ)|>kδ

Pr{|Ykp|>αkp}<eα24kp

ααkp=kδα=δp2δ2δ+1

Nous avons donc

Pr{Y<k2}Pr{|Y(k2+kδ)|>kδ}Pr{|Ykp|>αkp}<eα24kp

et si vous faites les calculs, vous verrez que

α24kpδ24δ+2k=Θ(kδ)

on a

Pr{Y<k2}<eΘ(kδ)

ϵ

eΘ(kδ)ϵ

ou en d'autres termes

Θ(δ1lgϵ)k

NkkM

12

Kaveh
la source
7

En utilisant votre notation:

BPP={L:M,0<c1/2XPr[χL(X)=M(X)]12+c}

PP={L: une machine de Turing à temps polynomial probabiliste M tel que XPr[χL(X)=M(X)]>12}

La différence a été soulignée par adrianN, et vous pouvez également jeter un œil à Wikipedia PP vs BPP

Vor
la source