Komplexität von Algorithmen, Satz 18
Channel: ThI Videos
Date: 11/03/2020

In diesem Video beweisen wir die NP-Vollständigkeit vom Problem CLIQUE.

0:00 Satz 18
1:05 Beweisidee
5:07 Reduktion am Beispiel
9:10 Korrektheit der Reduktion: Hinrichtung
13:53 Korrektheit der Reduktion: Rückrichtung
17:37 Laufzeitberechnung