Theoretische Informatik II ¨ Ubungsblatt 2 (fu ¨ r die 17. Kalenderwoche) zur Vorlesung von Prof. Dr. Mossakowski im Sommersemester 2015 Magdeburg, 13. April 2015 1. Gegeben sei die Boolesche Formel φ = (X1 ∨ X2 ∨ X3 ) ∧ (X1 ∨ X2 ∨ X4 ) ∧ (X1 ∨ X3 ∨ X4 ). Konstruieren Sie, wie im Beweis der NP-Vollst¨andigkeit von positive-1-in-3-sat angegeben, eine Boolesche Formel φ′′ ohne negierte Variable mit je drei Literalen pro Klausel, die genau dann so erf¨ ullbar ist, dass in jeder Klausel genau ein Literal erf¨ ullt wird, wenn φ′ aus Aufgabe 5 vom ¨ Ubungsblatt 1 so erf¨ ullbar ist, dass in jeder Klausel genau ein Literal erf¨ ullt wird. 2. Zeigen Sie, dass die Sprache max-2-sat = {hφ, ki | φ ist eine Boolesche Formel in konjunktiver Normalform, in der alle Klauseln aus genau zwei Literalen bestehen und f¨ ur die es eine Belegung der Variablen gibt, die mindestens k Klauseln erf¨ ullt} eine NP-vollst¨andige Sprache ist. Hinweis: Reduzieren Sie 3-sat auf max-2-sat: F¨ ur jede Klausel Ck = (λ1,k ∨ λ2,k ∨ λ3,k ) f¨ ugen Sie die zehn Klauseln (Yk ), (λ1,k ), (λ2,k ), (λ3,k ), (λ1,k ∨ λ2,k ), (λ1,k ∨ λ3,k ), (λ2,k ∨ λ3,k ), (λ1,k ∨ Yk ), (λ2,k ∨ Yk ), (λ3,k ∨ Yk ) hinzu. Schauen Sie dann, wie viele dieser Klausseln bei einer Ck erf¨ ullenden Belegung erf¨ ullt sind und wie viele bei einer Ck nicht erf¨ ullenden Belegung. ODER Reduzieren Sie nae-3-sat auf max-2-sat: F¨ ur jede Klausel Ck = (λ1,k ∨ λ2,k ∨ λ3,k ) f¨ ugen Sie die sechs Klauseln (λ1,k ∨ λ2,k ), (λ1,k ∨ λ3,k ), (λ2,k ∨ λ3,k ), (λ1,k ∨ λ2,k ), (λ1,k ∨ λ3,k ), (λ2,k ∨ λ3,k ) hinzu. Schauen Sie, wie viele dieser Klausseln bei einer nae-erf¨ ullenden Belegung erf¨ ullt sind und wie viele sonst. 3. In der Vorlesung Theorie I hatten wir das Problem hamilton-kreis als NP-vollst¨andig nachgewiesen. Zeigen Sie nun, dass die Sprache hamilton-pfad = {hGi | G ist ein gerichteter Graph, der einen Hamilton-Pfad besitzt} NP-vollst¨ andig ist, wobei ein Hamilton-Pfad in einem gerichteten Graphen G ein einfacher Pfad ist, bei dem jeder Knoten genau einmal besucht wird. 4. Sei G = (V, E) ein einfacher ungerichteter Graph. Ein Hamilton-Pfad in G ist ein einfacher Pfad, bei dem jeder Knoten genau einmal besucht wird. Zeigen Sie, dass die Sprache ungerichteter-hamilton-pfad = {hGi | G ist ein einfacher ungerichteter Graph, der einen Hamilton-Pfad besitzt} NP-vollst¨ andig ist. Die folgenden Graphen sind ein Hinweis f¨ ur die Reduktion. 5. Zeigen Sie, dass minimum-leaves-spanning-tree = {hG, ki | G ist ein einfacher ungerichteter Graph, der einen aufspannenden Baum besitzt, der h¨ochstens k Bl¨atter (= Knoten vom Grad 1) besitzt} eine NP-vollst¨ andige Sprache ist. 6. Gegeben sei die Boolesche Formel φ = (X1 ∨ X2 ∨ X3 ) ∧ (X1 ∨ X2 ∨ X4 ) ∧ (X1 ∨ X3 ∨ X4 ). Konstruieren Sie, wie im Beweis der NP-Vollst¨andigkeit von max-cut angegeben, einen Graphen G mit 17 Knoten und 22 Kanten, der genau dann einen Cut der Gr¨oße 19 besitzt, wenn φ nae-3-saterf¨ ullbar ist.