Quand le BPP avec une pièce biaisée est-il égal au BPP standard?

Permettez à une machine de Turing probabiliste d'avoir accès à une pièce de monnaie injuste qui génère des probabilités (les flips sont indépendants). Définissez comme la classe de langages reconnaissable par une telle machine en temps polynomial. Il s'agit d'un exercice standard pour prouver que: $p$ $BPP_p$

A) Si est rationnel ou même calculable par alors . (Par calculable, je veux dire: il y a un algorithme polynomial randomisé qui étant alimenté en unaire renvoie whp le rationnel binaire avec le dénominateur qui se trouve à de .) $p$ $BPP$ $BPP_p=BPP$ $BPP$ $n$ $2^n$ $2^{-n-1}$ $p$

B) Pour certains calculables, la classe contient un langage indécidable et est donc plus grande que . Ces valeurs de forment un ensemble dense en . $p$ $BPP_p$ $BPP$ $p$ $(0,1)$

Ma question est la suivante: que se passe-t-il entre les deux? Existe-t-il un critère pour ? En particulier: $BPP_p=BPP$

1) Existe-t-il des probabilités calculables dans telles que ? (Ils peuvent être calculés dans certaines classes supérieures). $BPP$ $p$ $BPP_p=BPP$

2) est- plus large que pour tout calculable ? (Les paramètres en question sont ceux dont l'expansion binaire contient de très longues séquences de zéros et / ou de uns. Dans ce cas, le calcul des bits par échantillonnage aléatoire peut prendre un temps très long, voire non calculable, et le problème ne peut pas être redimensionné en temps polynomial. Parfois, le la difficulté peut être surmontée par une autre base d'expansion, mais certains peuvent tromper toutes les bases). $BPP_p$ $BPP$ $p$ $p$

cc.complexity-theory randomized-algorithms probabilistic-complexity Daniil Musatov
la source

Qu'entendez-vous exactement par p étant (non) calculable?

daniello

J'ai ajouté la définition de

calculable. Pour le calculable en général, on peut simplement supprimer les mots "polynôme randomisé" ou simplement dire que l'expansion binaire est calculable. (Avec des ressources limitées, ce n'est pas la même chose.)

B P P

$BPP$

Daniil Musatov

Je pense que

pour chaque non calculable

parce que donné une

d' une pièce -biased peut calculer la

ième bit de

par échantillonnage. Supposons que l' on peut calculer le

-ième bit dans le temps

, alors la langue qui contient

pour tous les

de telle sorte que le

ième bit de

est

est en

B P P_{p} \neq B P P

$BPP_p \neq BPP$

p

$p$

p

$p$

n

$n$

p

$p$

n

$n$

f (n)

$f(n)$

1^{x}

$1^x$

x

$x$

f^{- 1} (x)

$f^{-1}(x)$

p

$p$

1

$1$

B P P_{p}

$BPP_p$ , mais il est clair que ce n'est pas calculable.

daniello

Cela est certainement vrai pour la grande majorité des

calculables . Mais il y a une mise en garde: si

contient des séquences très longues de zéros et ceux alors il peut avoir besoin très long échantillonnage pour déterminer le

ième bit. Cet échantillonnage peut être si long que

ne serait pas calculable (comme la fonction Busy Beavers). Je doute également qu'il puisse être calculé avec précision à partir de l'échantillonnage lui-même. Et il semble que sans calculer

on ne puisse pas reconnaître le langage mentionné.

p

$p$

p

$p$

n

$n$

f (n)

$f(n)$

f (n)

$f(n)$

Daniil Musatov

Réponses:

1) Oui, mais uniquement à cause de votre définition. Prenez un langage unaire (oui, je sais que cela pourrait être vide, dans ce cas, prenez simplement quelque chose de plus grand que ), ce qui est très rare dans le sens où si n'est pas une tour de , par exemple, de la forme . Définissez . Ce n'est pas $L\in EXP\setminus BPP$ $EXP$ $n\notin L$ $n$ $2's$ $2^{2^{2^\ldots}}$ $p=\sum_{n\in L} 1/n$ $p$ calculable, mais peut être approximé en jusqu'à une erreur additive suffisamment petite qui permet la simulation d'unemachine . $BPP$ $p$ $P$ $BPP_p$

Si vous aviez défini -calculable tel que vous voulez approximativement à une erreur additif ( au lieu de ) en temps polynomial, les choses seraient différentes. $BPP$ $p$ $1/n$ $1/2^n$

Mise à jour. La réponse ci-dessous concerne le cas où l'erreur additive que nous autorisons est au lieu de . $2^{-n}$ $2^{-n-1}$

2) Oui, parce que là , vous pouvez oublier la restriction polynomiale sur les classes et par échantillonnage fois , vous pouvez obtenir le - ième bit en . $2^n$ $n$ $p$ $BPP_p$

domotorp
la source

2) Je pense que le théorème de la limite centrale suggère que l'on devrait échantillonner

, et non

, fois pour acquérir une précision de

. Mais le principal problème est que parfois nous avons besoin d'une précision beaucoup plus grande. Dis, si

2^{2 n}

$2^{2n}$

2^{n}

$2^n$

2^{- n}

$2^{-n}$

alors il faut

| p - \frac{1}{2} | < ϵ

$|p-\frac12|<\epsilon$

échantillons pour calculer même le premier chiffre. Et le nombre d'échantillons nécessaires peut être arbitrairement, même de façon non calculable, important. Le point est un peu clarifié dans le montage.

\frac{1}{ϵ^{2}}

$\frac1{\epsilon^2}$

Daniil Musatov

@Daniil: Comme j'ai également commenté la question, vous n'avez pas demandé le calcul des chiffres dans votre définition de

calculable. Donc, si

est égal à, disons,

, alors on devrait deviner

pour le premier chiffre après la virgule en fonction de votre déf.

B P P

$BPP$

p

$p$

0.01111111111

$0.01111111111$

1

$1$

domotorp

Nous parlons maintenant de

calculable , n'est-ce pas? Si je vous comprends bien, vous proposez de ne pas calculer en échantillonnant les chiffres de

, mais plutôt de calculer si le

ème chiffre de

approximation rationnelle binaire de

est 1. Mais ici, nous sommes confrontés au même problème: calculer le premier chiffre dont nous avons besoin pour distinguer 0,010000000001 et 0,001111111110.

p

$p$

p

$p$

i

$i$

2^{- i - 1}

$2^{-i-1}$

p

$p$

Daniil Musatov

@Daniil: OK, mon mauvais, je pensais que vous vouliez un rationnel binaire dont la distance est au plus

. J'ai mis à jour ma réponse en conséquence. Êtes-vous satisfait de ma solution 1)?

2^{- n}

$2^{-n}$

p

$p$

domotorp