11: Übung: Nichtdeterministische Turingmaschine, Transformation, MAX2SAT

0:00:00 Starten 0:00:57 Nichtdeterministische Turingmaschine(n) 0:06:41 Die Klassen NP und ANP 0:11:10 A-NTMs sind nicht mächtiger als NTMs 0:23:31 Polynomiale Transformation 0:25:23 Polynomielle Transformation 0:29:26 Komplexitätsklassen und Werkzeugkasten 0:38:14 2SAT ∈ P 0:54:26 NP-Vollständigkeit 0:57:35 MAX2SAT 1:11:27 Tipps für Reduktion auf Max2Color Dozent: Dr. Torsten Ueckerdt | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik Vorlesungsaufzeichnung: KIT | WEBCAST http://webcast.kit.edu