Berechenbarkeit und Komplexität: NP-Vollständigkeit ausgewählter Zahlprobleme

Berechenbarkeit und Komplexität: NP-Vollständigkeit ausgewählter Zahlprobleme (Di, 13.12.2022)

00:00:55	Wiederholung
00:12:19	SUBSET-SUM
00:14:03	NP-Vollständigkeit von SUBSET-SUM
00:15:48	Reduktion 3-SAT auf SUBSET-SUM
00:45:45	NP-Vollständigkeit von PARTITION
00:54:17	NP-Vollständigkeit von Bin-Packing
00:57:52	NP-Vollständigkeit vom Rucksackproblem
01:02:31	Komplexitätslandschaft