Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- co-RP (http://www.informatikerboard.de/board/thread.php?threadid=355)
Geschrieben von JCDenton am 23.01.2008 um 04:54:
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
Geschrieben von ed209 am 23.01.2008 um 09:46:
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
Geschrieben von JCDenton am 23.01.2008 um 16:18:
| 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
Geschrieben von Tobias am 23.01.2008 um 16:24:
| 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.
Geschrieben von JCDenton am 23.01.2008 um 16:43:
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
Geschrieben von Tobias am 23.01.2008 um 21:16:
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})
Geschrieben von JCDenton am 24.01.2008 um 16:11:
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
Geschrieben von Tobias am 24.01.2008 um 17:27:
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.
Forensoftware: Burning Board, entwickelt von WoltLab GmbH