Wann entspricht BPP mit einer voreingenommenen Münze dem Standard-BPP?

10

Lassen Sie eine probabilistische Turing-Maschine Zugriff auf eine unfaire Münze haben, die mit der Wahrscheinlichkeit auftaucht (Flips sind unabhängig). Definieren Sie B P P p als die Klasse von Sprachen, die von einer solchen Maschine in Polynomzeit erkannt werden. Es ist eine Standardübung, um Folgendes zu beweisen:pBPPp

A) Wenn rational oder sogar ist B P P -computable dann B P P p = B P P . (Mit B P P -berechnbar meine ich: Es gibt einen randomisierten Polynomalgorithmus, der mit n in unären Mengen gespeist wird, wenn das binäre Rationale mit dem Nenner 2 n innerhalb von 2 - n - 1 von p liegt .)pBPPBPPp=BPPBPPn2n2n1p

B) Für einige unberechenbare die Klasse B P P P eine unentscheidbare Sprache enthält und somit größer als B P P . Solche Werte von p bilden eine dichte Menge in ( 0 , 1 ) .pBPPpBPPp(0,1)

Meine Frage lautet wie folgt: Was passiert dazwischen? Gibt es ein Kriterium für ? Speziell:BPPp=BPP

1) Gibt es in berechenbare Wahrscheinlichkeiten p , so dass B P P p = B P P ist ? (Sie können in einigen höheren Klassen berechenbar sein).BPPpBPPp=BPP

2) Ist für alle nicht berechenbaren p breiter als B P P ? (Die fraglichen Parameter sind diejenigen, deren binäre Erweiterung sehr lange Folgen von Nullen und / oder Einsen enthält. In diesem Fall kann das Berechnen von Bits durch zufällige Abtastung sehr lange, sogar nicht berechenbare Zeit dauern, und das Problem kann nicht auf die Polynomzeit neu skaliert werden Schwierigkeiten können durch eine andere Expansionsbasis überwunden werden, aber bestimmte p können alle Basen täuschen).BPPpBPPpp

Daniil Musatov
quelle
Was genau meinst du damit, dass p (nicht) berechenbar ist?
Daniello
Ich habe die Definition von -berechnbar hinzugefügt. Für berechenbare im Allgemeinen kann man einfach die Wörter "randomisiertes Polynom" fallen lassen oder einfach sagen, dass die binäre Erweiterung berechenbar ist. (Mit begrenzten Ressourcen ist dies nicht dasselbe.)BPP
Daniil Musatov
Ich denke, für jedes nicht berechenbare p, weil man bei einer p- voreingenommenen Münze das n -te Bit von p durch Abtasten berechnen kann . Angenommen , wir berechnen kann , die n -te Bit in der Zeit f ( n ) , dann ist die Sprache , die enthält 1 x für alle x , so dass die f - 1 ( x ) -te Bit von p ist 1 ist in B P P PBPPpBPPppnpnf(n)1xxf1(x)p1BPPp, aber klar ist es nicht berechenbar.
Daniello
Dies gilt definitiv für die überwiegende Mehrheit der nicht berechenbaren . Es gibt jedoch eine Einschränkung: Wenn p sehr lange Folgen von Nullen und Einsen enthält, ist möglicherweise eine sehr lange Abtastung erforderlich, um das n -te Bit zu bestimmen . Diese Abtastung kann so lang sein, dass f ( n ) nicht berechenbar wäre (wie die Busy Beavers-Funktion). Ich bezweifle auch, dass es aus der Stichprobe selbst genau berechnet werden kann. Und es scheint, dass man ohne Berechnung von f ( n ) die erwähnte Sprache nicht erkennen kann. ppnf(n)f(n)
Daniil Musatov

Antworten:

1

LEXPBPPEXPnLn2s222p=nL1/npBPPpPBPPp

BPPp1/n1/2n

2n2n1

2nnpBPPp

domotorp
quelle
22n2n2n|p12|<ϵ1ϵ2
BPPp0.011111111111
ppi2i1p
2np