 co-RP |
JCDenton
Grünschnabel
Dabei seit: 22.01.2008
Beiträge: 6
 |
|
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
|
|
23.01.2008 04:54 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
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
|
|
|
23.01.2008 09:46 |
|
|
JCDenton
Grünschnabel
Dabei seit: 22.01.2008
Beiträge: 6
|
|
| 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
|
|
|
23.01.2008 16:18 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
| 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.
|
|
|
23.01.2008 16:24 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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})
|
|
|
23.01.2008 21:16 |
|
|
JCDenton
Grünschnabel
Dabei seit: 22.01.2008
Beiträge: 6
|
|
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
|
|
|
24.01.2008 16:11 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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.
|
|
|
24.01.2008 17:27 |
|
|
|
