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

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 4 Beiträge

Tobias

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.

JCDenton

Hi Tobias,

Vielen Dank für deine Antwort!

Zitat:

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.

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

Tobias

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?

JCDenton

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

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