Diskussion:BPP (Komplexitätsklasse)

Verweis auf Arthur-Merlin-Spiele fehlt. Siehe Wegener, S. 158. 141.35.20.90 18:41, 21. Jan. 2008 (CET)

Artikel ist fehlerhaft: Eine Fehlerwahrscheinlichkeit von [0,1/2) beinhaltet auch 1/2-epsilon, was bei entsprechend kleinem epsilon eben nicht durch pa ausreichend verringert werden kann. (nicht signierter Beitrag von 109.42.204.171 (Diskussion) 16:21, 29. Apr. 2011 (CEST))

Definition von BPP

Wikipedia gibt momentan folgende Definition:

 Ein Problem liegt in BPP, wenn es eine polynomiell zeitbeschränkte probabilistische Turingmaschine gibt, 
 die das Problem löst und deren Fehlerwahrscheinlichkeit höchstens 1/3 beträgt.

In

Peter Rechenberg, Gustav Pomberger: Informatik-Handbuch. 2. Auflage. Carl Hanser Verlag, Wien 1999, ISBN 3-446-19601-3. 

steht:

 BPP (bounded error): Für ein $\varepsilon >0$ sind die Entscheidungen für jede Eingabe mit einer Wahrscheinlichkeit, die größer als 1/2 ist, korrekt.

In den Vorlesungsfolien von Frau Prof. Dr. Wagner (KIT, Link, Vorlesung 8, Folie 4-1) steht:

 Die Klasse ${\mathcal {BPP}}$ (bounded error PP) ist die Klasse der Entscheidungsprobleme $\Pi$, für die es einen polynomiellen, 
 randomisierten Algorithmus A gibt, so dass für alle Instanzen $I$ gilt:
 $I\in Y_{\Pi }\rightarrow Pr[A(I)istJa]\geq {\frac {3}{4}}$
 $I\notin Y_{\Pi }\rightarrow Pr[A(I)istJa]\leq {\frac {1}{4}}$

Was ist nun richtig? Wo kommt das 1/3 her? --Martin Thoma 21:37, 15. Feb. 2013 (CET)

alle drei definitionen sind aequivalent, wie im ersten abschnitt des artikels erklaert. --Mario d 13:59, 16. Feb. 2013 (CET)

Für die aktuell in der Wikipedia und in dem Informatik-Handbuch verwendete Definition verstehe ich die Äquivalenz.

Aber was ist mit der Definition von Frau Prof. Wagner? Macht es nicht einen unterschied, ob man die Fehler-Eigenschaft < 1/2 getrennt für Ja- und Nein-Instanzen fordert?

Darf ich die Konstante zu 1/2 ändern und dann als Einzelnachweis das Buch einfügen? --Martin Thoma 10:55, 17. Feb. 2013 (CET)

ich bin davon ausgegangen, dass du die definition im buch durch das zitieren zu sehr verkuerzt hast. warum hat er $\varepsilon$ definitiert, wenn es danach in der definition gar nicht verwendet wird? gemeint ist mit groesser als 1/2 sicherlich eine fehlerwahrscheinlichkeit von $1/2-\varepsilon$, wobei $\varepsilon$ eine konstante ist, d.h. nicht von der eingabe abhaengen darf. zu 1/2 darfst du die fehlerwahrscheinlichkeit nicht aendern, das waere ja die definition von PP und das buch sagt ja auch groesser als 1/2. zu der definition von frau Wagner: BPP fordert eine fehlerw'keit von max. 1/3, damit sind beide fehler gemeint, also

$I\in Y_{\Pi }\rightarrow Pr[A(I){\text{ ist nicht Ja}}]\leq {\frac {1}{3}}$

$I\notin Y_{\Pi }\rightarrow Pr[A(I){\text{ ist Ja}}]\leq {\frac {1}{3}}$

das kann man im artikel sicher noch praezisieren, wie ueblich ist die englische WP deutlich besser: en:PP_(complexity)#PP vs BPP. --Mario d 12:43, 17. Feb. 2013 (CET)

Ich habe den Abschnitt "Defintion" aus der en-wiki übersetzt und hier ergänzt. Für mich ist dieser Diskussionsfaden damit beendet. --Martin Thoma 09:25, 5. Mär. 2013 (CET)

Jeder RP-Algorithmus ist ein BPP-Algorithmus

Laut der aktuellen Version des Artikels gilt $RP\subseteq BPP$

Diese Aussage ist nicht belegt. Ich gehe gerade Klausuren durch und laut einer Klausur-Lösung (Letzte Seite, letzte Frage) ist diese Aussage falsch.

Die Definition in der Wikipedia zu BPP ist:

Ein Problem liegt in BPP, wenn es eine polynomiell zeitbeschränkte probabilistische Turingmaschine gibt, die das Problem löst und deren Fehlerwahrscheinlichkeit höchstens 1/3 beträgt.

Die Definition zu RP ist:

RP [...] bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus A mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für jede zu akzeptierende Eingabe der Länge n eine durch (n) beschränkte Fehlerwahrscheinlichkeit hat.

Ist nun ein Fehler in der Lösung der Klausur? Kann jemand die Aussate "$RP\subseteq BPP$" belegen? --Martin Thoma 22:18, 21. Feb. 2013 (CET)

sinn der diskussionsseiten ist ja die artikelverbesserung; es waere daher schoen, wenn du die artikel dahingehend verbesserst, dass das, was du vorher nicht verstanden hast, besser erklaert ist. gerade bei RP wuerde eine bessere einleitung jedem leser das verstaendnis erleichtern und du wuerdest leichter sehen, warum RP in BPP enthalten ist und die klausuraufgabe trotzdem richtig. --Mario d 14:13, 22. Feb. 2013 (CET)

Die Aussage in der Klausur ist eine andere, i.e. jeder RP-Algorithmus ist ein BPP-Algorithmus.

$RP\subseteq BPP$ bedeutet nur dass wenn es einen RP-Alg. gibt dann gibt es auch einen BPP-Alg (das kann aber ein ganz anderer Alg. sein)

Wenn man jetzt die präzisieren Definitionen aus der englischen wikipedia nimmt dann erlauben RP-Alg. für yes instanzen eine Fehlerwahrscheinlichkeit <= 1/2 während BPP-Alg. nur <= 1/3 erlauben - deshalb falsch

bleibt noch $RP\subseteq BPP$ zu belegen

ich würde das so Argumentieren: hat man einen RP-Alg. dann kann dieser, bis auf die Fehlerwahrscheinlichkeit, als BPP Alg gesehen werden. Dann führen wir diesen einfach zweimal hintereinander aus und nehmen YES wenn mindestens einer der Versuche YES ergibt und NO sonst. Das liefert eine fehler <= 1/4 --Wdvorak (Diskussion) 14:53, 22. Feb. 2013 (CET)

Ok, ich habe also "Problem" und "Algorithmus" hier unpassenderweise gleichgesetzt.

Zu einer Aussage von dir:

"[...] dann erlauben RP-Alg. für yes instanzen eine Fehlerwahrscheinlichkeit <= 1/2 während BPP-Alg. nur <= 1/3 erlauben - deshalb falsch"

Es gibt aber nuch andere Definitionen für BPP als die mit 1/3. Aber die sind alle "< 1/2" und nicht "<= 1/2", deshalb geht es auch mit diesen Definitionen nicht, oder?

Das heißt, obwohl nicht jeder RP-Algorithmus ein BPP-Algorithmus ist, kann man auf triviale Weise (durch wiederholtes Anwenden) aus jedem RP-Algorithmus einen BPP-Algorithmus machen. Korrekt?

@Mario: Sobald ich das Gefühl habe, es wirklich verstanden zu haben, werde ich die Einleitung verbessern. Ich finde es macht wenig Sinn, die Einleitung zu verbessern, obwohl für mich das ganze noch nicht klar ist und ich mir dessen bewusst bin. --Martin Thoma 16:26, 22. Feb. 2013 (CET)

es gibt mehrere moeglichkeiten, BPP zu definieren, die sind aber alle aequivalent, das heisst, es ist egal welche du benutzt. "< 1/2" gehort nicht dazu, das ist die definition von PP (s. antwort auf deine vorherige frage). --Mario d 16:44, 22. Feb. 2013 (CET) nachtrag: @korrekt: ja, so sehe ich das auch. --Mario d 12:11, 26. Feb. 2013 (CET)

Obwohl ich immer noch keine Quelle dafür habe, habe ich das Ergebnis der Diskussion in den Artikel eingebunden. Auch dieser Diskussionsfaden ist damit für mich beendet. Vielen Dank für eure Hilfe! --Martin Thoma 09:33, 5. Mär. 2013 (CET)

fuer was genau moechtest du eine quelle? ich fand deine einfuegung eher verwirrend. --Mario d 14:15, 5. Mär. 2013 (CET)

Ich hätte z.B. für die Definition gerne einen Einzelnachweis. Oder auch für die Mengenbeziehung der Komplexitätsklassen. --Martin Thoma 16:19, 5. Mär. 2013 (CET)

das faende ich auch gut. frag doch mal deinen uebungsleiter oder schau in der unibib nach, ich habe leider keinen zugriff auf deutschsprachige lehrbuecher. die beiden, die ich schon eingefuegt habe sind nicht optimal, der eine ist das originalpaper, der andere ein englisches lehrbuch. --Mario d 17:26, 5. Mär. 2013 (CET)

Ich für die Definition mal complexity zoo als Nachweis eingefügt (dort ist es genau so definiert)

Meiner Erfahrung nach gibt es kaum (gute) deutschsprachige Literatur in dem Gebiet - aber umso besser wenn du etwas finden solltest --Wdvorak (Diskussion) 09:17, 6. Mär. 2013 (CET)

ich habe den nachweis durch ein lehrbuch ersetzt. natuerlich gibt es am complexity zoo nichts auszusetzen, er steht ja auch noch unter weblinks, aber ein lehrbuch hat mMn doch ein wenig mehr gewicht. --Mario d 21:06, 9. Mär. 2013 (CET)