P vs NP

zuerst mal zur quelle: lies hier kapitel 5, da sind alle Definitionen drin.

Zu Deiner Übungsaufgabe: ne, das Cliquenproblem ist genauso schwierig wie das 3 SAT Problem, und das 3 SAT Problem ist genauso schwer wie das SAT Problem, also ist 3SAT und Clique wie SAT in NPC.

"Warum beschreibt diese Vorgehensweise, dass das 3-Cliquen-Problem NP-schwer ist und dadurch nicht sicher in NP?"

Sorry, aber das kapiere ich nicht... was ist das 3 Cliquen Problem?

Wie gesagt, liess Kapitel 5, Kapitel 6 kann auch interessant sein, ordne Deine Sprache, vielleicht kann ich Dir dann helfen.

Nunja.
Ich hab in der Übungsaufgable das 3-Cliquen Problem - eben eine Clique mit festem k = 3 - auf das 3-Sat Problem reduziert. (3-Sat "<=p" 3-Clique)
Da 3-SAT € NPC ist und 3-Clique sich relativ einfach analog transformieren lässt, sollte 3-Clique doch auch € NPC und dadurch vorallem in NP liegen, oder?
Als Anmerkung zu meiner Reduktion bekam ich jedoch:"so zeigt man, dass 3-Clique NP-Schwer ist".
Und eben jenen Punkt verstehe ich nicht. 3-Sat € NPC, also folgt daraus doch bei einer Reduktion, dass auch 3-Clique € NPC ist, oder nicht?

Im Satz 5.19 wird auch nur angenommen, dass Clique € NP ist und das man mit der Reduktion nur noch NP-Schwer zeigen müsse. ( => Definition NPC ).
Würde dort nicht auch die Reduktion reichen, um NPC zu zeigen? - konkret also die Annahme € NP weglasen.

Ich glaube einfach, dass mein Übungsgruppenleiter da was falsch verstanden hat und mich total verwirrt hat.

Ich hoffe, dass du nun mein Anliegen verstehen konntest.

Da 3-SAT € NPC ist und 3-Clique sich relativ einfach analog transformieren lässt, sollte 3-Clique doch auch € NPC und dadurch vorallem in NP liegen, oder?

jein. 3-SAT und k-Clique sind gleich schwer wie in 5.19 bewiesen wird.
Dadurch, dass 3-SAT mindestens so schwer ist wie SAT ist es in NPC, aber das heißt noch nicht, dass es in NP sein muss. Es gibt Probleme in NPC die nicht in NP liegen.
ABER: man kann jede 3-SAT Formel in eine SAT Formel umbauen und vice versa.
SAT liegt in NP und dort in dem Teil von NP, der NPC ist. Also liegt auch 3-SAT in diesem Teil und damit auch k-Clique und damit auch 3-Clique.

"
Im Satz 5.19 wird auch nur angenommen, dass Clique € NP ist und das man mit der Reduktion nur noch NP-Schwer zeigen müsse. ( => Definition NPC ).
Würde dort nicht auch die Reduktion reichen, um NPC zu zeigen? - konkret also die Annahme € NP weglasen."

nein. Wie gesagt, es gibt NP, es gibt NPC und es gibt NP hard. NP hard sind Probleme, die nicht in NP liegen und schwerer als NP Probleme sind. Deswegen musst Du zeigen, dass Clique in NP liegt.

schau dir das bild oben rechts an.

mir persönlich hat folgende, wenn auch sehr simple darstellung geholfen

Soweit ich es verstanden habe, hast du in der Übungsaufgabe einfach das falsche gezeigt.
NP-schwer und in NP sind zwei verschiedene Dinge. Für NP-vollständig muss dann beides gelten.

NP = Problem von NTM in P lösbar oder einfach anders gesagt: Lösung raten, kann man in P testen, ob es eine Lösung ist -> in NP.
NP-schwer: Polynomielle Reduktion auf ein anderes NP-schweres Problem.
NP-vollst.: in NP + NP-schwer.

Zum Algorithmus angeben, das etwas in P liegt: Prinzipiell gibt's zwei Möglichkeiten:
a) Algorithmus angeben, Korrektheit zeigen und beweisen, dass die Laufzeit in P ist (also von Hand)
b) Zeigen, dass man das Problem in P in ein anderes Problem transformieren kann, dass in P ist.
Das gilt dann natürlich auch für NP, da P Teilmenge NP, aber natürlich nicht umgekehrt.

Original von MisterJ
Soweit ich es verstanden habe, hast du in der Übungsaufgabe einfach das falsche gezeigt.
NP-schwer und in NP sind zwei verschiedene Dinge. Für NP-vollständig muss dann beides gelten.

NP = Problem von NTM in P lösbar oder einfach anders gesagt: Lösung raten, kann man in P testen, ob es eine Lösung ist -> in NP.
NP-schwer: Polynomielle Reduktion auf ein anderes NP-schweres Problem.
NP-vollst.: in NP + NP-schwer.

Zum Algorithmus angeben, das etwas in P liegt: Prinzipiell gibt's zwei Möglichkeiten:
a) Algorithmus angeben, Korrektheit zeigen und beweisen, dass die Laufzeit in P ist (also von Hand)
b) Zeigen, dass man das Problem in P in ein anderes Problem transformieren kann, dass in P ist.
Das gilt dann natürlich auch für NP, da P Teilmenge NP, aber natürlich nicht umgekehrt.

Danke! Das hat mir sehr geholfen.
Aber auch Danke an die anderen