EDIT Vorweg: Ich weiß nicht wieso, aber sobald ICH einen Beitrag abschicke, konvertiert das Forum-System erstmal alle Sonderzeichen und Umlaute aus diesem Beitrag in tollen Zeichensalat um. Deswegen Sorry für die schlechte Leserlichkeit...
Eigentliche Frage:
Nochmal grundsätzliches zu diesen P, NP Geschichten:
Also wenn ich das richtig verstanden habe sieht das so aus:
P : Klasse der Entscheidungsprobleme, die sich in polynomialer Zeit l�sen lassen
NP: Klasse der Entscheidungsprobleme, für die für eine vorgebene Lösung in polynomialer Zeit entschieden werden kann, ob sich das Problem mit "ja" löst.
Ich finde jetzt aber die Definition für NP - hart etwas verwirrend. Sei das Problem mal mit K bezeichnet, dann ist die Def.
K ist NP hart, wenn
K Element aus P , P = NP
Mir geht das Verständnis dafür überhaupt nicht in den Kopf. Übertragen auf diese Skizze mit den Mengen-Blasen (Seite 36 im Skript) müsste dann die Menge "NP-hart" doch gerade die Fläche NP einschließlich P sein?
Das ist für mich gerade so wie wenn man versucht zu deuten, wo das Universum endet und einem irgendwann der Kopf vor lauter Überlegung platzt. Auf Deutsch würde doch die Def. für NP - hart bedeuten:
"K ist ein Entscheidungsproblem, das in polynomialer Zeit lösbar ist, für das für eine vorgegebene Lösung in polynomialer Zeit entschieden werden kann, ob es sich mit "Ja" löst".
Vielleicht hat ja noch jemand eine verständlichere Erklärung auf Lager...
Woran erkennt man dann eigentlich, ob ein Problem nur NP oder sogar NP-hart ist?
S&A Entscheidungsprobleme
Moderator: (M) Mod.-Team Allgemein
Ein Problem K nennt man NP-hart, genau dann wenn gilt:
"Falls K in P liegen sollte, folgt daraus, dass P = NP", oder mit Formelzeichen:[tex] K \in P \rightarrow P = NP[/tex]
Es ist überhaupt nichts darüber ausgesagt, ob K tatsächlich in P oder NP liegt. Wenn du allerdings ein NP-hartes Problem finden würdest, welches in P liegt, dann hättest du gezeigt, dass gilt P = NP. Und damit wärst du ein reicher Mann, weil es vor dir noch niemanden gelungen ist, dies zu zeigen (oder zu widerlegen).
Ein Problem ist NP-vollständig, wenn es NP-hart ist und in NP liegt.
edit: Siehe auch: http://www.claymath.org/millennium/P_vs_NP/
"Falls K in P liegen sollte, folgt daraus, dass P = NP", oder mit Formelzeichen:[tex] K \in P \rightarrow P = NP[/tex]
Es ist überhaupt nichts darüber ausgesagt, ob K tatsächlich in P oder NP liegt. Wenn du allerdings ein NP-hartes Problem finden würdest, welches in P liegt, dann hättest du gezeigt, dass gilt P = NP. Und damit wärst du ein reicher Mann, weil es vor dir noch niemanden gelungen ist, dies zu zeigen (oder zu widerlegen).
Ein Problem ist NP-vollständig, wenn es NP-hart ist und in NP liegt.
edit: Siehe auch: http://www.claymath.org/millennium/P_vs_NP/
Five exclamation marks, the sure sign of an insane mind. Terry Pratchett
Man kann zeigen, dass ein Problem NP-hart ist, indem man ein z.b. ein anderes NP-hartes Problem her nimmt und dann zeigt, dass man in O(n^k) Schritten das eine Problem in das andere Umwandln kann. Das ist aber (denke ich) viel zu schwer für eine Klausuraufgabe.
Five exclamation marks, the sure sign of an insane mind. Terry Pratchett
Re: S&A Entscheidungsprobleme
Ich habe mal im anderem Forum darauf geantwortet: http://forum.tu-talking.de/viewtopic ... 0554#40554Silversurfer hat geschrieben:EDIT Vorweg: Ich weiß nicht wieso, aber sobald ICH einen Beitrag abschicke, konvertiert das Forum-System erstmal alle Sonderzeichen und Umlaute aus diesem Beitrag in tollen Zeichensalat um. Deswegen Sorry für die schlechte Leserlichkeit...