48m 8sLänge

1. [00:08] Asymptotische Komplexität ... 2. [00:36] Untere Schranken Sortieren ... 3. [01:44] Für untere Schranken reicht, ... 4. [03:26] Entscheidungsbaum Mergesort n größer 4 5. [05:07] Permutation identifizieren 6. [06:33] Mathematische Analyse 7. [08:01] Wirklich schwere Probleme 8. [08:20] Handlungsreisendenproblem (TSP) 9. [08:39] Rucksackproblem 10. [09:45] Steinerbaumproblem 11. [10:35] Mengenpackung/-überdeckung 12. [11:36] Clique / Unabhängige Menge 13. [12:06] Maximale Clique 14. [12:31] Was heißt schwer? 15. [13:20] Ansatz der Theorie 16. [14:15] Was ist polynomielle Laufzeit? 17. [15:40] Arten von Problemen 18. [17:39] Entscheidungsproblem abgeleitet 19. [19:39] Zertifikate 20. [22:40] Zertifikate beim TSP 21. [24:07] Problemklassen P und NP 22. [25:41] Reduktion von Problemen 23. [26:57] Reduktion auf kürzestes Pfade 24. [28:55] Reduktion von Problemen Fazit 25. [29:53] Polynomielle Reduktion 26. [30:30] Die Klasse NPC 27. [31:50] Circuit-SAT ist in NPC 28. [33:14] Beweisskizze Circuit-SAT ist in NPC 29. [38:17] Auch SAT ist in NPC 30. [39:13] Beweisskizze SAT in NPC 31. [39:56] Auch 3-CNF ist in NPC 32. [40:42] Beweis 3-CNF in NPC 33. [42:26] Auch CLIQUE ist in NPC 34. [43:32] Beweisskizze MAX-CLIQUE in NPC 35. [46:30] Grundprinzip der Argumentation