Theoretische Informatik II

Theoretische Informatik II
¨
Ubungsblatt
1
(fu
¨ r die 16. Kalenderwoche)
zur Vorlesung von Prof. Dr. Mossakowski
im Sommersemester 2015
Magdeburg, 7. April 2015
1. Welche der folgenden Behauptungen sind wahr, welche falsch? Begr¨
unden Sie jeweils Ihre Antwort.
a) P ⊆ NP.
b) Falls A ∈ NP und B NP-schwer ist, dann gilt A P B.
c) Falls A P B und B ∈ NP gelten, dann gilt auch A ∈ NP.
2. Zeigen Sie, dass die Klasse P unter Komplement und Schnitt abgeschlossen ist. (P ist auch unter
Vereinigung, Konkatenation und Kleene Star abgeschlossen, aber das brauchen Sie nicht zu zeigen.)
3. Es sei
half-clique = {hGi | G = (V, E) ist ein ungerichteter Graph und es gibt eine
Teilmenge V ′ ⊆ V mit |V ′ | ≥ |V | / 2, so dass f¨
ur alle vi , vj ∈ V ′
mit vi 6= vj gilt, dass die Kante zwischen vi und vj zu E geh¨ort}.
Zeigen Sie, dass half-clique eine NP-vollst¨andige Sprache ist.
Hinweis: Zeigen Sie clique P half-clique.
4. Sei G = (V, E) ein ungerichteter Graph. Eine Knotenmenge V ′ ⊆ V heißt dominierend, falls
jeder Knoten aus V − V ′ durch eine Kante mit einem Knoten in V ′ verbunden ist. Zeigen Sie,
dass dominating-set = {hG, ki | G besitzt eine dominierende Knotenmenge der Gr¨oße k} eine
NP-vollst¨andige Sprache ist.
Hinweis: Konstruieren Sie zu einem ungerichteten Graphen G einen Graphen G′ wie im folgenden
Beispiel angedeutet und zeigen Sie dann, dass G eine u
¨berdeckende Knotenmenge (vertex cover)
der Gr¨oße k besitzt, genau dann wenn G′ eine dominierende Knotenmenge (dominating set) der
Gr¨oße k besitzt.
5. Es sei die Boolesche Formel
φ = (X1 ∨ X2 ∨ X3 ) ∧ (X1 ∨ X2 ∨ X4 ) ∧ (X1 ∨ X3 ∨ X4 )
gegeben. Konstruieren Sie, wie im Beweis der NP-Vollst¨andigkeit von 1-in-3-sat angegeben, eine
Boolesche Formel φ′ mit je drei Literalen pro Klausel, die genau dann so erf¨
ullbar ist, dass in jeder
Klausel genau ein Literal erf¨
ullt wird, wenn φ erf¨
ullbar ist.

Download Report