Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Rp(1/2)=rp(1/3)?

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Rp(1/2)=rp(1/3)?

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

JCDenton
Grünschnabel

Dabei seit: 22.01.2008
Beiträge: 6

Rp(1/2)=rp(1/3)?

Zitatantwort auf diesen Beitrag erstellen

Es gilt ja RP(1/2) = RP(1/3). Woher stammt der Wert 1/3? Ich weiß, dass man die Fehlerwahrscheinlichkeit durch Probability Amplification von 1/2 durch k-maliges Wiederholen von 1/2 senken kann. Also (1/2)^k. Dann wäre nach 2maligen Wiederholen des RP algos die Fehlerwahrscheinlichkeit 1/4, nach 3maligen 1/8 usw...
Kann ich die 1/3 so verstehen, dass die Komplexitätsklasse RP(1/3) alle Algos mit den Fehlerwahrscheinlichkeiten.... 1/16, 1/8, 1/4 < 1/3 abdeckt?

JCD

22.01.2008 19:35

Nehmen Sie JCDenton in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Man kann sogar noch weiter gehen:

$[latex]\operatorname{RP}(1/2) = \operatorname{RP}(2^{-q(n)})[/latex]$ für ein beliebiges Polynom q >= 1.

Der Beweis läuft genau so ab, wie du beschrieben hast. Man wiederholt den Algorithmus mit Akzeptanzwahrscheinlichkeit 1/2 genau q(n) mal (sofern er nicht vorher akzeptiert) und kommt so auf die Akzeptanzwahrscheinlichkeit $[latex]1 - 2^{-q(n)}[/latex]$ . Wichtig ist dabei die Beobachtung, dass die Laufzeit polynomiell bleibt.

Setze also $[latex]q(n) := \log_2(3) \geq 1[/latex]$

Zitat:

Kann ich die 1/3 so verstehen, dass die Komplexitätsklasse RP(1/3) alle Algos mit den Fehlerwahrscheinlichkeiten.... 1/16, 1/8, 1/4 < 1/3 abdeckt?

Du kannst RP(1/3) so verstehen, dass alle Probleme, die in RP(1/2) sind auch in RP(1/3) enthalten sein müssen. In Komplexitätsklassen sind allgemein keine Algorithmen sondern (Entscheidungs-)Probleme. Algorithmen sind Beweiswerkzeuge, um die Komplexität von Problemen einzuordnen.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tobias: 22.01.2008 20:21.

22.01.2008 20:11

Nehmen Sie Tobias in Ihre Freundesliste auf

JCDenton
Grünschnabel

Dabei seit: 22.01.2008
Beiträge: 6

Hi Tobias,

Vielen Dank für deine Antwort!

Zitat:

Aber warum denn ausgerechnet 1/3 ?
RP(1/4) wäre (für mich) durch die probability amplicication einleuchtender. Also warum 1/3? smile

Vielleicht ist es ganz einleuchtend, aber ich checks gerade nicht smile

JCD

22.01.2008 20:59

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Ich weiß auch nicht woher die 1/3 kommen. Das muss sich doch aus einem Kontext erschließen, den nur du kennst (Übungsaufgabe, Beweis von xy, ..).

Es kann z.B. sein, dass die 1/3 einfach exemplarisch gewählt wurden, um zu veranschaulichen, dass die 1/2, die oft in der Definition von RP benutzt wird, rein praktische Bedeutung hat und ersetzt werden kann durch z.B. 1/3 oder 1/5 oder Pipapo.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tobias: 22.01.2008 21:11.

22.01.2008 21:10

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Rp(1/2)=rp(1/3)?