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

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 $\in$ EVPP. Auch leicht zu sehen, dass EBPP $\subset$ 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 $\in$ EVPPP. Während EBPP möglicherweise keine Untermenge von EVPPP ist, haben wir ERP $\subset$ EVPPP. Vielleicht können wir damit einen (nichtnegativen) Rang für Entscheidungsprobleme definieren.

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 $f$$Q$$Q$$f$$\mathbb{R}$$Q$$\mathbb{R}$ , das sich $f$in 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.$\Omega(N)$

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.

Dies ist eine teilweise Antwort; Vielleicht wird es jemand anderen inspirieren, ein besseres zu liefern. $\newcommand{\EBPP}{\mathsf{EBPP}}$ $\newcommand{\CP}{\mathsf{C}_=\mathsf{P}}$

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 dass$\EBPP$$\CP$$\CP$$L$$\CP$$V$

• wenn in L ist , dann  akzeptiert Pr w [ V ( x , w ) ] = $x$$L$$\Pr_w[V(x, w) \text{ accepts}] = \frac{3}{4}$ und
• wenn nicht in L ist , dann  akzeptiert Pr w [ V ( x , w ) ] ≠ $x$$L$ .$\Pr_w[V(x, w) \text{ accepts}] \neq \frac{3}{4}$

(Die Vollständigkeitswahrscheinlichkeit kann im Wesentlichen ein beliebiger fester Bruch sein; ich habe so dass es mit der in Ihrer Frage angegebenen Wahrscheinlichkeit übereinstimmt.)$\frac{3}{4}$

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

• wenn in L ist , dann  akzeptiert Pr w [ V ( x , w ) ] = $x$$L$ und$\Pr_w[V(x, w) \text{ accepts}] = \frac{3}{4}$
• wenn nicht in L ist , dann  akzeptiert Pr w [ V ( x , w ) ] = $x$$L$ .$\Pr_w[V(x, w) \text{ accepts}] = \frac{1}{4}$