Komplexität #17 - HAMILTON-Pfad ist NP-hart

0:00 Einleitung
2:16 Reduktion
13:42 Korrektheit
20:23 NP-Härte für Varianten

Wir sehen eine Reduktion von 3SAT auf HAMILTON-Pfad an, wodurch wir zeigen, dass HAMILTON-Pfad NP-hart ist. Wir überlegen außerdem noch, dass die Reduktion auch für HAMILTON-Kreis und für gerichtete statt ungerichtete Graphen angepasst werden kann.

[GreenyDe]

OH MY LORD - Wer ist denn bitte auf das Gadget gekommen...Smart! Finde es super schwer die Idee zu finden für 3-SAT auf Graphen Reduktionen.... Aber cool wie schön man das an einem Beispiel veranschaulichen kann... Danke dafür!

[Cor-tex]

"Wir verpassen nichts wenn wir ein Video überspringen" ? Ich denke schon!! Die Videos und die Erklärungen sind einfach nur genial! Weiter so! 💪 Ich freue mich schon auf das nächste Video :)

[arnoclaude]

Hoffentlich sind die Reduktionen in der Klausur nicht so schwer :o das ist ja genius

[mk-pg]

14:58 Wieso kann man sich hier aussuchen die 2. Klausel nicht zusätzlich durch die Variale z zu besuchen? Dadurch wäre ja eine Klausel zwei mal besucht und damit der hamilton pfad kaputt.

[paulus.schmaulus]

Die Reduktion ist genial. Ich hab bei den Reduktionen die ich als Übungen machen muss immer das riesige Problem das ganze Formal aufzuschreiben. Aber das ist wahrscheinlich einfach Übungssache...

[jonah]

Müssten die Verbindungen nicht Pfeile sein, da dies ein gerichteter Graph ist/sein sollte?

[annikabusch]

Wirklich sehr hilfreiche Videos! Aber du sagst in deinen Überschriften, dass HAMILTON und SUBSET SUM NP-hart sind, aber die liegen doch beide in NP. Dachte ein Problem ist NP-hart, wenn darauf zwar alle Probleme aus NP in Poly'zeit reduzierbar sind, das Problem selbst aber nicht in NP liegt?

[herrhupfdohle]

Bei 15:30 sprichst du auf einmal von Hamilton Kreis. Meintest du nicht Pfad?

[BatmanBEGINS]

Du sagst von einem problem in ein anderes Problem übersetzt. Aber bei der Polynomiellen reduktion (das video dazu) hast du gesagt dass wenn man Problem L1 suf L2 reduziert(L1<L2) es so bedeutet dass Das Problem L2 eine Lösung hat womit man auch L1 löst??