co-RP

23.01.2008, 04:54

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

23.01.2008, 09:46

Auf diesen Beitrag antworten »

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

23.01.2008, 16:18

Auf diesen Beitrag antworten »

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

23.01.2008, 16:24

Auf diesen Beitrag antworten »

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.

23.01.2008, 16:43

Auf diesen Beitrag antworten »

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

23.01.2008, 21:16

Auf diesen Beitrag antworten »

Tobias

Aha. Ich nehme also Folgendes an:

$[latex]\operatorname{RP}^\ast = \operatorname{NP}[/latex]$ und $[latex]\operatorname{co-RP}^\ast = \operatorname{co-NP}[/latex]$

Außerdem ist bekannt, dass $[latex]\operatorname{P} \subseteq \operatorname{co-NP}[/latex]$ .

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]$

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]$

24.01.2008, 16:11

Auf diesen Beitrag antworten »

JCDenton

Wow, vielen Dank für deine Antwort! Jetzt verstehe ich es! smile

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, 17:27

Auf diesen Beitrag antworten »

Tobias

Da stellst du aber eine komplizierte Frage. geschockt

Es ist bekannt, dass
$[latex]\operatorname{P} \subseteq \operatorname{RP} \subseteq \operatorname{NP} = \operatorname{RP}^\ast[/latex]$
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.

Neue Frage »

Antworten »

co-RP

Verwandte Themen