Sei co-NP definiert mit { L| Komplement von L ist Element NP}
Zeigen Sie: Wenn co-NP eine NP-vollstaendige Sprache enthaelt,
so gilt co-NP = NP
Folgender Ansatz bisher:
Zz ist co-NP Teilmenge von NP
und NP Teilmenge von co-NP, dann ist die Gleichheit gezeigt.
Desweiteren nehme ich wenn L element co-NP dann ist L Komplement element NP (Komplement von Komplement L ist ja wieder L).
Dann noch Definition von NP-vollstaendigkeit geschickt hinschreiben,
eine magische Zeile einfuegen und fertig :)
Ich denke, es widerspricht dem Konzept von Übungsaufgaben,
hier (wieder) eine vollständige Lösung zu posten. [img]
http://www.fb18.de/gfx/25.gif[/img]
Daher ist es besser, nur eine grobe Anleitung zu geben:
1. Zunächst kann du dir überlegen, dass es reicht zu zeigen,
dass co-NP enthalten ist in NP.
2. Zeige, dass [img]
http://mokrates.de/cgi-bin/texstring?A%5Cle_%7Bpol%7D%20B%5CRightarrow%20%5Coverline%7BA%7D%5Cle_%7Bpol%7D%5Coverline%7BB%7D[/img]
3. Dann muss man bei der Aufgabe nur noch eine einfache
Implikationskette hinschreiben: angenommen, V ist in co-NP
und NP-vollständig. Dann:
L in co-NP => ... => L in NP.Die einzelnen Schritte sind alle recht einfach.
Wenn du irgendwo hängen bleibst, kann du ja nochmal
fragen.
huhu ich bins wieder eure lieblingswurstie,
wie die meisten anderen hat mich die grippe gepackt und ich
lieg mit fieber im bettchen, hab am montag morgen klausur und
wollte fragen ob ihr vielleicht doch nochmal den kompletten weg
hinschreiben koennt?
war heute auch nicht in den uebungen und muss erstmal kucken das
ich den aktuellen stoff nachgelernt krieg (rucksack sat 3sat etc)
in der klausur duerfen wir 2 beschriebene zettel mitnehmen und ich
wuerde diese aufgabe dann draufschreiben (ums verstehen kuemmer ich
mich wenn noch zeit ist)
koennt auch am datum sehen das bereits ueber ne woche rum ist und ich hier keinen verarschen will mit uebungsblaetter (hab beim aktuellen meine verdienten null punkte eingefahren wegen nicht-anwesenheit eben)
wuensche frohen endspurt und kommt gesund in die vorlesungsfreie
zeit, wers vor sich hat viel erfolg bei den pruefungen
OK, dann werde ich mal meine eigenen Tips beherzigen [img]
http://www.fb18.de/gfx/23.gif[/img]
1. Wir zeigen: wenn co-NP [img]
http://mokrates.de/cgi-bin/texstring?%5Csubseteq%20[/img] NP,
dann gilt bereits co-NP=NP. Denn sei [img]
http://mokrates.de/cgi-bin/texstring?L%5Cin%20NP[/img].
Dann ist [img]
http://mokrates.de/cgi-bin/texstring?%5Coverline%7BL%7D%5Cin%20co-NP%5Csubseteq%20NP[/img],
also [img]
http://mokrates.de/cgi-bin/texstring?%5Coverline%7BL%7D%5Cin%20NP[/img] und damit
[img]
http://mokrates.de/cgi-bin/texstring?L%5Cin%20co-NP[/img]. Beide Inklusionen gelten somit.
Für die ganze Aussage bleibt nun nur noch
[img]
http://mokrates.de/cgi-bin/texstring?co-NP%5Csubseteq%20NP[/img] zu zeigen.
Der Rest kommt gleich nach der Werbung (oder besser gesagt:
im nächsten Posting, wegen der Bildergrenze [img]
http://www.fb18.de/gfx/22.gif[/img])
