| Die letzten 8 Beiträge |
| Tobias |
Da stellst du aber eine komplizierte Frage. 
Es ist bekannt, dass
![[latex]\operatorname{P} \subseteq \operatorname{RP} \subseteq \operatorname{NP} = \operatorname{RP}^\ast[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\operatorname{P} \subseteq \operatorname{RP} \subseteq \operatorname{NP} = \operatorname{RP}^\ast)
Welche von diesen Inklusionen echt sind ist nicht bekannt. Stell dir vor jemand beweist P = NP, dann ist sofort auch RP = NP bewiesen.
Der Grund, warum man RP* = NP zeigen kann hängt mit der Definition der Komplexitätsklassen zusammen. Eine randomisierte Turingmaschine, die in polynomieller Zeit mit einer Fehlerwahrscheinlichkeit von 0 eine Sprache entscheidet ist von ihrem Verhalten mit einer nichtdeterministischen Turingmaschine gleichzusetzen. Betrachtet man die Konfigurationspfade der TM ist es gleichgültig, ob die TM durch Zauberhand (= Nichtdeterminismus) den richtigen Pfad erwischt oder durch zufälliges aber IMMER richtiges Raten. |
| JCDenton |
Wow, vielen Dank für deine Antwort! Jetzt verstehe ich es! 
Nach merhmaligen Überlegen hab ich mich aber gefragt, warum ausgerechnet RP*=NP und nicht ZPP, EP, PP, BPP oder RP(1/2) gleich NP sind.
Die anderen sind ja schließlich auch randomisiert und mit Probability Amplification läßt sich jede Fehlerwahrscheinlichkeit beliebig klein machen....
Irgendwie fällt mir keine einleuchtende Begründe dafür (für RP*) oder gegen die anderen ein.
Gibt es explizite Gründe für RP* und gegen die anderen?
JCD |
| Tobias |
Aha. Ich nehme also Folgendes an:
![[latex]\operatorname{RP}^\ast = \operatorname{NP}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\operatorname{RP}^\ast = \operatorname{NP}) und ![[latex]\operatorname{co-RP}^\ast = \operatorname{co-NP}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\operatorname{co-RP}^\ast = \operatorname{co-NP})
Außerdem ist bekannt, dass ![[latex]\operatorname{P} \subseteq \operatorname{co-NP}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\operatorname{P} \subseteq \operatorname{co-NP}) .
Damit wird jetzt deine Behauptung bewiesen:
| Zitat: |
| Wenn co-RP* eine Teilmenge von P ist, folgt daraus, dass dann P=NP ist? |
![[latex]\operatorname{co-RP}^\ast = \operatorname{co-NP} \subseteq \operatorname{P} \subseteq \operatorname{co-NP} \quad \Rightarrow \operatorname{co-NP} = \operatorname{P}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\operatorname{co-RP}^\ast = \operatorname{co-NP} \subseteq \operatorname{P} \subseteq \operatorname{co-NP} \quad \Rightarrow \operatorname{co-NP} = \operatorname{P})
Da P unter dem Komplement abgeschlossen ist, muss (wegen Gleichheit) auch co-NP unter dem Komplement abgeschlossen sein, also
![[latex]\operatorname{co-NP} = \operatorname{P} = \operatorname{NP}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\operatorname{co-NP} = \operatorname{P} = \operatorname{NP}) |
| JCDenton |
RP*
Akzeptieren:
x nicht in L: Wkeit 0
x in L: Wkeit 1 (bei RP 1/2)
Verwerfen:
x nicht in L: Wkeit 1
x in L: Wkeit 0 (bei RP 1/2)
RP* arbeitet also genau wie eine nichtdeterministische Turingmaschine. Die NDTM akzeptiert wie RP* auf mindestens einem Rechenweg und falls sie nicht akzeptiert verwirft sie.
JCD |
| Tobias |
| Zitat: |
Original von JCDenton
Also ein Problem gehört zu RP* wenn gilt €(n) < 1 ist aus RP(€(n)). |
Schreib mal lieber eure exakte Definition auf. So kann man das kaum verstehen. |
| JCDenton |
| Zitat: |
Erste Frage: Was ist co-RP*? Eine Erweiterung von co-RP?
|
Also ein Problem gehört zu RP* wenn gilt €(n) < 1 ist aus RP(€(n)). Bei RP war die Fehlerwahrscheinlichkeit € bekanntlich 1/2.
co-RP* ist das Komplement vpn RP*.
| Zitat: |
Zweitens: Was weisst du ueber das Verhaeltnis von co-RP, co-RP*, P und NP? (z.B "P ist eine Teilmenge von NP")
|
Außerdem weiß ich dass co-RP*=Co-NP und RP*=NP gilt. Außerdem weiß ich noch, dass P eine Teilmenge von NP ist. ZPP=RP UND Co-RP.
JCD |
| ed209 |
RE: co-RP
Erste Frage: Was ist co-RP*? Eine Erweiterung von co-RP?
Zweitens: Was weisst du ueber das Verhaeltnis von co-RP, co-RP*, P und NP? (z.B "P ist eine Teilmenge von NP")
Gruss,
ED |
| JCDenton |
co-RP
Hallo,
habe eine Verständnis Frage: Was bedeutet co-RP* ist Teilmenge von P ? Und macht diese Aussage Sinn?
Wenn co-RP* eine Teilmenge von P ist, folgt daraus, dass dann P=NP ist?
JCD |
