Seite 1 von 1

Übungsblatt 13 - SAT

BeitragVerfasst: 17 Mär 2014, 20:55
von cmw
Hallo zusammen,

auf dem Übungsblatt 13 gibt es zwei Aufgaben zum Thema NP - Vollständigkeit (A10 und A11). Diese decken jedoch bei Weitem nicht den Stoff von Schönings Kapitel 3 ab, welches ja komplett dem Übungsblatt zugeordnet ist. Gilt nun für die dritte Klausur
a) die gleiche Beschränkung "nach oben" wie in der zweiten Klausur ("Auch den letzten Vorlesungsteil über NP-Vollständigkeit werden wir nicht prüfen")
b) der gesamte Aufgabeninhalt von Übungsblatt 13 wird geprüft
oder c) das vollständige Kapitel 3 ist noch Teil der Klausur, d.h. wir müssen auch Reduktionen von SAT / 3SAT auf andere Probleme zeigen können?

Vielen Dank schonmal für die Antwort!

LG,
cmw

Re: Übungsblatt 13 - SAT

BeitragVerfasst: 18 Mär 2014, 15:52
von jkaiser
Wir habe in den letzten zwei Vorlesungen kurz über Reduktionen gesprochen, insbesonder über SAT, 3SAT, ... und dabei angerissen wie genau man von einem Problem zum nächsten reduziert. Die Reduktionen hier wurden jedoch nicht im vollen Umfang ausgearbeitet. Folglich sind die Reduktionen auf diesem intuitiven Level durchaus prüfbar, ebenso wie die Inhalte aller gestellten Übungsaufgaben zu diesem Thema.