Komplexitätstheorie

Prof. Dr. Henning Fernau

Vorlesungsankündigung

Folien

Achtung!

Die Vorlesung am Mo, 04.01., entfällt. Stattdessen finden Vorlesung und Übungen am Fr, 08.01., ab 09:00 h s.t. im Raum HZ 201 statt.

Übungsblätter

In den ersten zwei Terminen wird der Übungsbetrieb vorlesungsartig erfolgen.

Aufgrund eines Krankheitsfalls am Lehrstuhl beginnt der Übungsbetrieb erst in der zweiten VL-Woche.

Für die 5. VL nehmen wir uns folgende Übungen vor:

Weisen Sie für das "einfache Pebble-Spiel" aus der VL sowie für 2-UNSAT unterhalten NL-Vollständigkeit) nach.

Eine Instanz von 2-UNSAT ist gegeben durch eine Boolesche Formel in CNF, bei der jede Klausel höchstens zwei Literale enthält und bei der gefragt ist, ob die Formel unerfüllbar ist.

.

  • Übungen zu VL 6
  • .

  • Übungen zu VL 7
  • Ü8: Vertiefung von Min-UnSAT. Diskutiere: Verhältnis zu MaxSAT. Wo gibt es polynomiell lösbare Fälle? Wie ist es mit Max2SAT? Ist die Frage, ob das Löschen von höchstens k Knoten aus einem Graphen genügt, um ihn kreisfrei zu machen, NP-vollständig?
  •