Komplexität von Algorithmen, Beispielaufgabe 9
Channel: ThI Videos
Date: 01/04/2021

In diesem Video erkläre ich, wie die Aufgabe 9 aus dem Musterlösungszettel gelöst wird.
Hierbei soll man zeigen, dass das Problem INDEPENDENT-SET NP-vollständig ist.


0:00 Vorspann
0:08 Aufgabenstellung
1:11 Mitgliedschaft in NP
7:54 NP-Schwere