Rp(1/2)=rp(1/3)? |
| 22.01.2008, 19:35 | Auf diesen Beitrag antworten » | ||
| 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 |
||
|
|
|||
| 22.01.2008, 20:11 | Auf diesen Beitrag antworten » | ||
| Tobias | Man kann sogar noch weiter gehen: 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 Setze also
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. |
||
| 22.01.2008, 20:59 | Auf diesen Beitrag antworten » | ||
| JCDenton | Hi Tobias, Vielen Dank für deine Antwort!
Aber warum denn ausgerechnet 1/3 ? RP(1/4) wäre (für mich) durch die probability amplicication einleuchtender. Also warum 1/3? 
Vielleicht ist es ganz einleuchtend, aber ich checks gerade nicht
JCD |
||
| 22.01.2008, 21:10 | Auf diesen Beitrag antworten » | ||
| 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. |
||
| Anzeige | |||
|
|
|||
|
|