In welcher Klasse befinden sich randomisierte Algorithmen, die mit einer Wahrscheinlichkeit von genau 25% fehlerhaft sind?

17

Angenommen, ich betrachte die folgende Variante von BPP, die wir E (xact) BPP nennen lassen: Eine Sprache ist in EBPP, wenn es eine polynomiell zeitlich zufällige TG gibt, die jedes Wort der Sprache mit einer Wahrscheinlichkeit von genau 3/4 akzeptiert und jedes Wort nicht in die Sprache mit genau 1/4 Wahrscheinlichkeit. Offensichtlich ist EBPP in BPP enthalten, aber sind sie gleich? Wurde das untersucht? Was ist mit dem ähnlich definierbaren ERP?

Motivation. Meine Hauptmotivation ist, dass ich wissen wollte, was das komplexitätstheoretische Analogon des randomisierten Algorithmus "Correct in Expected Value" von Faenza et al. (siehe http://arxiv.org/abs/1105.4127 ) wäre. Zunächst wollte ich verstehen, welche Entscheidungsprobleme ein solcher Algorithmus lösen kann (mit Worst-Case-Polynomlaufzeit). Bezeichnen wir diese Klasse mit E (xpected) V (alue) PP. Es ist leicht zu sehen, dass USAT EVPP. Auch leicht zu sehen, dass EBPP EVPP. Das war also meine Motivation. Jedes Feedback zu EVPP ist ebenfalls willkommen.

Tatsächlich gibt ihr Algorithmus immer eine nichtnegative Zahl aus. Wenn wir die Entscheidungen Probleme erkennbar durch einen solchen Algorithmus von EVP (ositive) PP bezeichnen, dann haben wir noch USAT EVPPP. Während EBPP möglicherweise keine Untermenge von EVPPP ist, haben wir ERP EVPPP. Vielleicht können wir damit einen (nichtnegativen) Rang für Entscheidungsprobleme definieren.

domotorp
quelle
10
Ich denke , Sie bereits dies realisieren, aber wenn Sie die Einschränkung zu akzeptieren Worte in der Sprache mit der Wahrscheinlichkeit entspannen 3/4±ε für ε1/poly(n) dann sollten die Klassen gleich sein.
Huck Bennett
3
@domotorp Was ist die Motivation hinter dieser Frage? Was haben Sie mit dieser semantischen Komplexitätsklasse vor? Sehen Sie eine Möglichkeit, EBPP irgendwo einzusetzen, um einen Satz zu beweisen? Können Sie näher darauf eingehen?
Tayfun Pay
1
Lesen Sie den Artikel "Probabilistic Complexity Classes and Lowness" von Uwe Schoning, 1989.
Tayfun Pay
1
@ Tayfun: Ich habe es ausprobiert, konnte aber nichts Relevantes finden. Könnten Sie genauer sein?
Domotorp
2
@HuckBennett: oder auch für & egr; exp ( - p o l y ( n ) ) . 3/4±ϵϵexp(poly(n))
Colin McQuillan

Antworten:

10

Nebenbei bemerkt, es ist nicht klar, dass EBPP eine robuste Klasse ist. Wenn der Algorithmus beispielsweise nicht zulässt, dass eine unbefangene Münze geworfen wird, sondern eine unbefangene 3-seitige Münze oder ein 6-seitiger Würfel, ist nicht klar, dass Sie dieselbe Klasse erhalten. BPP bleibt gleich, wenn Sie diese Details ändern.

Wie auch immer, Ihre primäre Frage ist, ob EBPP gleich BPP ist oder nicht. Es scheint mir, dass EBPP näher an P liegt als an BPP. Berücksichtigen Sie die Abfragekomplexität oder die Oracle-Version dieser Klassen, bei der sie Zugriff auf eine große Eingabezeichenfolge haben und Abfragen durchführen müssen, um Bits dieser Zeichenfolge zu lernen. Wenn Sie einen P - Algorithmus haben , die eine Funktion berechnet mit Q - Abfragen, dann gibt es eine exakte darstellt Polynom vom Grad Q für f über R . (Dies ist das übliche polynomielle Methodenargument.) Wenn Sie andererseits einen BPP-Algorithmus haben, erhalten Sie ein Grad- Q- Polynom über RfQQfRQR , das sich fin dem Sinne, dass sein Wert bei jedem Eingang in der Nähe des Wertes von .f

Gegeben sei ein EBPP-Algorithmus für eine Funktion f , können wir ein Polynom konstruieren, das 1/4 ausgibt, wenn die Antwort NEIN ist, und 3/4, wenn die Antwort JA ist. Indem Sie 1/2 subtrahieren und mit 2 multiplizieren, erhalten Sie genau wie bei P ein repräsentatives Polynom. Dies legt nahe, dass EBPP näher bei P liegt.

Diese Beobachtung kann auch verwendet werden, um eine Orakeltrennung zwischen EBPP und BPP zu zeigen. Betrachten Sie das Versprechen-Mehrheits-Problem, bei dem versprochen wird, dass der Eingang entweder mehr als 2N / 3 1s oder weniger als N / 3 1s hat, und Sie müssen entscheiden, was der Fall ist. Dies ist eindeutig in BPP. Mit dem oben beschriebenen Polynomargument kann gezeigt werden, dass für diese Funktion -Anfragen für eine EBPP-Maschine erforderlich sind . Beachten Sie jedoch, dass Sie eine Orakeltrennung auch in umgekehrter Richtung zwischen P und EBPP nachweisen können. Vielleicht sagen die Ergebnisse von Orakel nicht viel über dieses Problem aus? Oder vielleicht sagen sie, dass es schwierig sein wird, Gleichheit in beide Richtungen zu zeigen.Ω(N)

Robin Kothari
quelle
1
Ja, die Trennung von Orakeln scheint in beiden Fällen ziemlich einfach zu sein.
Domotorp
1

In Bezug auf Orakeltrennungen gibt es ein Orakel mit EBPP = BPP = EXP NP und ein Orakel mit P = ⊕P (und damit EBPP = P) und BPP = EXP NP .

Eine Konstruktion von BPP = EXP NP oracle (einschließlich der in BPP wikipedia article ) besteht darin, ein relativiertes EXP NP- Gesamtproblem zu wählen und rekursiv mit der Eingabegröße (für dieses Problem) fortzufahren, Ergebnisse für Probleminstanzen dieser Größe zu korrigieren und Geben Sie dann Antworten auf dieses Problem ein, wenn Sie eine Abfrage mit der Eingabe und einem Füllelement (mit der entsprechenden Länge) durchführen, das nicht behoben wurde. Für EBPP = EXP NP können wir, anstatt fast immer die richtigen Antworten zu geben, gerade genug falsche Antworten geben, um die Zählungen genau richtig zu machen. Es gibt auch ein Orakel, bei dem das Null-Fehler-Analogon von EBPP (genau die Hälfte der Wahrscheinlichkeit eines Meldefehlers) gleich EXP ist (und ein Orakel mit P = ⊕P, aber ZPP = EXP).

Das Orakel P = ⊕P und BPP = EXP NP wird hier notiert .

EBPP ist nicht nur in BPP und in C = P, sondern auch in ⊕P, da wir die Wahrscheinlichkeit auf die Anzahl der Zeugen reduzieren und diese Anzahl dann optimieren können.

In der nicht-relativen Welt ist BPP wahrscheinlich gleich P, aber die Evidenz für EBPP ist noch stärker. EBPP hängt von der genauen Anzahl der Pfade ab, die sich, sofern keine unerwartete Kündigung eintritt, im Wesentlichen nicht nutzen lassen.

Dmytro Taranovsky
quelle
0

Dies ist eine teilweise Antwort; Vielleicht wird es jemand anderen inspirieren, ein besseres zu liefern.

Ihre Klasse ist ein Spezialfall von C = P . Ich denke, eine Möglichkeit, C = P zu definieren, ist folgende (siehe Abschnitt 2 dieses Papiers ). Eine Sprache L ist in C = P, wenn es einen Polynomzeitprüfer V gibt, so dassEBPPC=PC=PLC=PV

  • wenn in L ist , dann  akzeptiert Pr w [ V ( x , w ) ] = 3xLPrw[V(x,w) accepts]=34 und
  • wenn nicht in L ist , dann  akzeptiert Pr w [ V ( x , w ) ] 3xL .Prw[V(x,w) accepts]34

(Die Vollständigkeitswahrscheinlichkeit kann im Wesentlichen ein beliebiger fester Bruch sein; ich habe so dass es mit der in Ihrer Frage angegebenen Wahrscheinlichkeit übereinstimmt.)34

Ein Weg, ist wie folgt. Eine Sprache L ist in E B P P, wenn es einen Polynomzeitprüfer V gibt, so dassEBPPLEBPPV

  • wenn in L ist , dann  akzeptiert Pr w [ V ( x , w ) ] = 3xL undPrw[V(x,w) accepts]=34
  • wenn nicht in L ist , dann  akzeptiert Pr w [ V ( x , w ) ] = 1xL .Prw[V(x,w) accepts]=14
Argentpepper
quelle
3
Es ist auch ein Sonderfall von BPP.
Peter Shor
@argentpepper Was Sie für einen Sonderfall von scheint nicht korrekt zu sein. Alle C = P- Maschinen müssen für alle Eingaben akzeptieren ODER ablehnen. Sie beschreiben eine kategoriale maschinensemantische Komplexitätsklasse. Es wird nicht akzeptiert oder abgelehnt, wenn die Wahrscheinlichkeit 1/2 beträgt. Das kann keine C = P- Maschine sein. C=PC=PC=P
Tayfun Pay
@PeterShor Genau
Tayfun Pay
1
@TayfunPay Ich halte deinen Kommentar nicht für sinnvoll. ist eine Menge von Sprachen, keine Maschinen, es gibt also keineC=P Maschine. argentpepper hat recht, dass EBPP tatsächlich eine Teilmenge von C = P ist . Es ist nur nicht klar, ob diese Einbeziehung hilfreich ist, zumal C = P eine mächtige Klasse istC=PC=PC=P
Sasho Nikolov
Nur eine andere Sichtweise auf das Problem ...
Argentpepper