anthropic/claude-opus-4.1

Exercise 7: Reduktion

Nehmen Sie PNP\P\ne\NP an. Entscheiden Sie unter dieser Annahme, welche der folgenden Aussagen gelten. Die Aussagen sind von der Gestalt „ApBA\le_p B“ für  Entscheidungsprobleme A,BA, B. Wenn die Aussage gilt, dann müssen Sie (1) eine präzise definierte Reduktionsfunktion angeben und (2) die Reduktionsfunktion auf die gegebene Instanz von Problem AA anwenden. Die Korrektheit der Reduktion müssen Sie nur skizzieren. Wenn die Aussage nicht gilt, dann müssen Sie dies beweisen.

Subproblem a (4.0/4.0P)

Sei G=(V,E)G=(V, E) ein ungerichteter Graph. Ein Hamilton-Pfad von GG ist eine Permutation v1,,vnv_1,\dotsc,v_n der Knoten von VV mit {vi,vi+1}E\{v_i, v_{i+1}\} \in E für jedes i{1,...,n1}i \in \{1, ..., n-1\}. Ein Hamilton-Kreis von GG ist ein Hamilton-Pfad von GG, der zusätzlich {vn,v1}E\{v_n, v_1\} \in E erfüllt.

Sei HAMILTON-PFAD das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Pfad hat. Sei HAMILTON-KREIS das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Kreis hat.

Aussage: HAMILTON-PFAD p\le_p HAMILTON-KREIS

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von HAMILTON-PFAD an.
Knoten: A, B, C, D, E
Kanten:
    A -- B
    A -- C
    B -- C
    C -- D
    C -- E
    D -- E
Die Aussage giltDie Aussage gilt nicht
Reduktionsfunktion: Gegeben ein Graph G=(V,E)G = (V, E), konstruiere G=(V,E)G' = (V', E') mit:
- V=V{x}V' = V \cup \{x\} (füge einen neuen Knoten xVx \notin V hinzu)
- E=E{{x,v}vV}E' = E \cup \{\{x, v\} \mid v \in V\} (verbinde xx mit allen ursprünglichen Knoten)

Anwendung auf die gegebene Instanz:
Der transformierte Graph GG' hat:
- Knoten: A, B, C, D, E, x
- Kanten: A--B, A--C, B--C, C--D, C--E, D--E, x--A, x--B, x--C, x--D, x--E

Korrektheitsskizze: 
GG hat einen Hamilton-Pfad \Leftrightarrow GG' hat einen Hamilton-Kreis, da:
- Vorwärts: Ein Hamilton-Pfad v1,,vnv_1, \ldots, v_n in GG wird zu einem Hamilton-Kreis x,v1,,vn,xx, v_1, \ldots, v_n, x in GG'
- Rückwärts: Jeder Hamilton-Kreis in GG' muss xx enthalten, und das Entfernen von xx liefert einen Hamilton-Pfad in GG

Subproblem b (3.0/3.0P)

Sei CFG-LEERHEIT das Entscheidungsproblem, ob eine gegebene kontextfreie Grammatik GG kein Wort erzeugt, also ob L(G)=L(G)=\emptyset gilt.

Aussage: 3KNF-SAT p\leq_p CFG-LEERHEIT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von 3KNF-SAT an.
(x1¬x2x3)(¬x1x2x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)
Die Aussage giltDie Aussage gilt nicht
Beweis, dass die Aussage nicht gilt:

CFG-LEERHEIT ist in P, da es einen Polynomialzeit-Algorithmus gibt, der die produktiven Nichtterminale einer kontextfreien Grammatik berechnet und prüft, ob das Startsymbol produktiv ist. Eine Grammatik erzeugt genau dann die leere Sprache, wenn ihr Startsymbol nicht produktiv ist.

3KNF-SAT ist NP-vollständig.

Annahme: Es gäbe eine Polynomialzeit-Reduktion 3KNF-SAT p\leq_p CFG-LEERHEIT.

Folgerung: Dann könnten wir 3KNF-SAT in Polynomialzeit lösen:
- Gegeben eine 3KNF-Formel φ, wende die Reduktion an und erhalte eine CFG G
- Teste in Polynomialzeit, ob L(G) = ∅
- Dies liefert die Antwort für die Erfüllbarkeit von φ

Das würde bedeuten 3KNF-SAT ∈ P, also P = NP, was unserer Annahme P ≠ NP widerspricht.

Konklusion: Die Reduktion 3KNF-SAT p\leq_p CFG-LEERHEIT kann unter der Annahme P ≠ NP nicht existieren.

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

Eingabe: Eine endliche Menge M={m1,...,mk}M=\{m_1, ..., m_k\} und eine Menge T={T1,...,Tn}T=\{T_1, ..., T_n\}  von Teilmengen von MM.

Ausgabe: Enthält TT eine exakte Überdeckung von MM, d.h. gibt es eine Menge STS \subseteq T, sodass jedes Element von MM in genau einer der Teilmengen in SS vorkommt?

Aussage: EXAKTE-ÜBERDECKUNG p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M{1,2,3,4}M\coloneqq\{1,2,3,4\}
T{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1{1}T_1\coloneqq\{1\},
T2{1,3}T_2\coloneqq\{1,3\},
T3{1,2,3}T_3\coloneqq\{1,2,3\},
T4{2,4}T_4\coloneqq\{2,4\},
T5T_5\coloneqq\emptyset.
Die Aussage giltDie Aussage gilt nicht
Reduktionsfunktion: Gegeben (M,T)(M, T) mit M={m1,,mk}M = \{m_1, \ldots, m_k\} und T={T1,,Tn}T = \{T_1, \ldots, T_n\}:
- Variablen: Für jedes TiT_i eine Variable xix_i (wahr gdw. TiT_i in der Überdeckung)
- Formel: Für jedes mjMm_j \in M mit Ij={imjTi}I_j = \{i \mid m_j \in T_i\}:
  - Mindestens eine Überdeckung: iIjxi\bigvee_{i \in I_j} x_i
  - Höchstens eine Überdeckung: i1<i2,i1,i2Ij(¬xi1¬xi2)\bigwedge_{i_1 < i_2, i_1,i_2 \in I_j} (\neg x_{i_1} \vee \neg x_{i_2})

Anwendung auf die gegebene Instanz:
Variablen: x1,x2,x3,x4,x5x_1, x_2, x_3, x_4, x_5

Für Element 1 (in T1,T2,T3T_1, T_2, T_3):
(x1x2x3)(¬x1¬x2)(¬x1¬x3)(¬x2¬x3)(x_1 \vee x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2) \wedge (\neg x_1 \vee \neg x_3) \wedge (\neg x_2 \vee \neg x_3)

Für Element 2 (in T3,T4T_3, T_4):
(x3x4)(¬x3¬x4)(x_3 \vee x_4) \wedge (\neg x_3 \vee \neg x_4)

Für Element 3 (in T2,T3T_2, T_3):
(x2x3)(¬x2¬x3)(x_2 \vee x_3) \wedge (\neg x_2 \vee \neg x_3)

Für Element 4 (in T4T_4):
x4x_4

Resultierende Formel:
ϕ=(x1x2x3)(¬x1¬x2)(¬x1¬x3)(¬x2¬x3)(x3x4)(¬x3¬x4)(x2x3)(¬x2¬x3)x4\phi = (x_1 \vee x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2) \wedge (\neg x_1 \vee \neg x_3) \wedge (\neg x_2 \vee \neg x_3) \wedge (x_3 \vee x_4) \wedge (\neg x_3 \vee \neg x_4) \wedge (x_2 \vee x_3) \wedge (\neg x_2 \vee \neg x_3) \wedge x_4

Korrektheitsskizze: Eine exakte Überdeckung existiert gdw. ϕ\phi erfüllbar ist. Die Belegung xi=x_i =  wahr entspricht der Auswahl von TiT_i.

anthropic/claude-sonnet-4

Exercise 7: Reduktion

Nehmen Sie PNP\P\ne\NP an. Entscheiden Sie unter dieser Annahme, welche der folgenden Aussagen gelten. Die Aussagen sind von der Gestalt „ApBA\le_p B“ für  Entscheidungsprobleme A,BA, B. Wenn die Aussage gilt, dann müssen Sie (1) eine präzise definierte Reduktionsfunktion angeben und (2) die Reduktionsfunktion auf die gegebene Instanz von Problem AA anwenden. Die Korrektheit der Reduktion müssen Sie nur skizzieren. Wenn die Aussage nicht gilt, dann müssen Sie dies beweisen.

Subproblem a (4.0/4.0P)

Sei G=(V,E)G=(V, E) ein ungerichteter Graph. Ein Hamilton-Pfad von GG ist eine Permutation v1,,vnv_1,\dotsc,v_n der Knoten von VV mit {vi,vi+1}E\{v_i, v_{i+1}\} \in E für jedes i{1,...,n1}i \in \{1, ..., n-1\}. Ein Hamilton-Kreis von GG ist ein Hamilton-Pfad von GG, der zusätzlich {vn,v1}E\{v_n, v_1\} \in E erfüllt.

Sei HAMILTON-PFAD das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Pfad hat. Sei HAMILTON-KREIS das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Kreis hat.

Aussage: HAMILTON-PFAD p\le_p HAMILTON-KREIS

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von HAMILTON-PFAD an.
Knoten: A, B, C, D, E
Kanten:
    A -- B
    A -- C
    B -- C
    C -- D
    C -- E
    D -- E
Die Aussage giltDie Aussage gilt nicht
Reduction function: Given graph G = (V, E), construct G' = (V ∪ {w}, E ∪ {(w,v) : v ∈ V}) where w is a new vertex connected to all vertices in V.

Application to given instance:
- Original graph G has vertices {A, B, C, D, E} and edges {AB, AC, BC, CD, CE, DE}
- Constructed graph G' has vertices {A, B, C, D, E, W} and edges {AB, AC, BC, CD, CE, DE, WA, WB, WC, WD, WE}
- Since G has Hamiltonian path A → B → C → D → E, then G' has Hamiltonian cycle A → B → C → D → E → W → A

Correctness sketch: G has a Hamiltonian path iff G' has a Hamiltonian cycle, because any Hamiltonian cycle in G' using the new vertex w corresponds to a Hamiltonian path in G, and vice versa.

Subproblem b (3.0/3.0P)

Sei CFG-LEERHEIT das Entscheidungsproblem, ob eine gegebene kontextfreie Grammatik GG kein Wort erzeugt, also ob L(G)=L(G)=\emptyset gilt.

Aussage: 3KNF-SAT p\leq_p CFG-LEERHEIT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von 3KNF-SAT an.
(x1¬x2x3)(¬x1x2x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)
Die Aussage giltDie Aussage gilt nicht
Proof that the statement does not hold:

CFG-LEERHEIT is in P, as there exists a polynomial-time algorithm to determine whether a context-free grammar generates the empty language.

3KNF-SAT is NP-complete.

If 3KNF-SAT ≤_p CFG-LEERHEIT existed, then since CFG-LEERHEIT ∈ P and polynomial reductions preserve membership in P, we would have 3KNF-SAT ∈ P.

Since 3KNF-SAT is NP-complete, 3KNF-SAT ∈ P would imply P = NP.

This contradicts our assumption that P ≠ NP.

Therefore, the reduction 3KNF-SAT ≤_p CFG-LEERHEIT cannot exist under the assumption P ≠ NP.

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

Eingabe: Eine endliche Menge M={m1,...,mk}M=\{m_1, ..., m_k\} und eine Menge T={T1,...,Tn}T=\{T_1, ..., T_n\}  von Teilmengen von MM.

Ausgabe: Enthält TT eine exakte Überdeckung von MM, d.h. gibt es eine Menge STS \subseteq T, sodass jedes Element von MM in genau einer der Teilmengen in SS vorkommt?

Aussage: EXAKTE-ÜBERDECKUNG p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M{1,2,3,4}M\coloneqq\{1,2,3,4\}
T{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1{1}T_1\coloneqq\{1\},
T2{1,3}T_2\coloneqq\{1,3\},
T3{1,2,3}T_3\coloneqq\{1,2,3\},
T4{2,4}T_4\coloneqq\{2,4\},
T5T_5\coloneqq\emptyset.
Die Aussage giltDie Aussage gilt nicht
Reduction function: Given EXAKTE-ÜBERDECKUNG instance (M, T) with M = {m₁, ..., mₖ} and T = {T₁, ..., Tₙ}, construct SAT formula φ as follows:
- For each Tᵢ ∈ T, introduce Boolean variable xᵢ
- For each element mⱼ ∈ M, let I(mⱼ) = {i : mⱼ ∈ Tᵢ}
- φ = ⋀_{mⱼ ∈ M} [(⋁_{i ∈ I(mⱼ)} xᵢ) ∧ ⋀_{i,i' ∈ I(mⱼ), i≠i'} (¬xᵢ ∨ ¬xᵢ')]

Application to given instance:
Variables: x₁, x₂, x₃, x₄, x₅

For element 1: (x₁ ∨ x₂ ∨ x₃) ∧ (¬x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ ¬x₃) ∧ (¬x₂ ∨ ¬x₃)
For element 2: (x₃ ∨ x₄) ∧ (¬x₃ ∨ ¬x₄)
For element 3: (x₂ ∨ x₃) ∧ (¬x₂ ∨ ¬x₃)
For element 4: x₄

Resulting SAT formula:
φ = (x₁ ∨ x₂ ∨ x₃) ∧ (¬x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ ¬x₃) ∧ (¬x₂ ∨ ¬x₃) ∧ (x₃ ∨ x₄) ∧ (¬x₃ ∨ ¬x₄) ∧ (x₂ ∨ x₃) ∧ (¬x₂ ∨ ¬x₃) ∧ x₄

Correctness sketch: The exact cover exists iff φ is satisfiable. The "at least one" clauses ensure every element is covered, while the "at most one" clauses ensure no element is covered twice. The reduction runs in polynomial time.

deepseek/deepseek-chat-v3.1

Exercise 7: Reduktion

Nehmen Sie PNP\P\ne\NP an. Entscheiden Sie unter dieser Annahme, welche der folgenden Aussagen gelten. Die Aussagen sind von der Gestalt „ApBA\le_p B“ für  Entscheidungsprobleme A,BA, B. Wenn die Aussage gilt, dann müssen Sie (1) eine präzise definierte Reduktionsfunktion angeben und (2) die Reduktionsfunktion auf die gegebene Instanz von Problem AA anwenden. Die Korrektheit der Reduktion müssen Sie nur skizzieren. Wenn die Aussage nicht gilt, dann müssen Sie dies beweisen.

Subproblem a (4.0/4.0P)

Sei G=(V,E)G=(V, E) ein ungerichteter Graph. Ein Hamilton-Pfad von GG ist eine Permutation v1,,vnv_1,\dotsc,v_n der Knoten von VV mit {vi,vi+1}E\{v_i, v_{i+1}\} \in E für jedes i{1,...,n1}i \in \{1, ..., n-1\}. Ein Hamilton-Kreis von GG ist ein Hamilton-Pfad von GG, der zusätzlich {vn,v1}E\{v_n, v_1\} \in E erfüllt.

Sei HAMILTON-PFAD das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Pfad hat. Sei HAMILTON-KREIS das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Kreis hat.

Aussage: HAMILTON-PFAD p\le_p HAMILTON-KREIS

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von HAMILTON-PFAD an.
Knoten: A, B, C, D, E
Kanten:
    A -- B
    A -- C
    B -- C
    C -- D
    C -- E
    D -- E
Die Aussage giltDie Aussage gilt nicht
Die Aussage gilt.

Reduktionsfunktion: Für einen gegebenen Graphen G=(V,E) G = (V, E)  für HAMILTON-PFAD, definiere einen neuen Graphen G=(V,E) G' = (V', E')  mit V=V{v} V' = V \cup \{v*\} , wobei v v*  ein neuer Knoten nicht in V V  ist, und E=E{{v,u}uV} E' = E \cup \{ \{v*, u\} \mid u \in V \} .

Angewendet auf die gegebene Instanz:
- Gegebener Graph G G : Knoten V={A,B,C,D,E} V = \{A, B, C, D, E\} , Kanten E={{A,B},{A,C},{B,C},{C,D},{C,E},{D,E}} E = \{ \{A,B\}, \{A,C\}, \{B,C\}, \{C,D\}, \{C,E\}, \{D,E\} \} .
- Dann G G' : Knoten V={A,B,C,D,E,X} V' = \{A, B, C, D, E, X\}  (wobei X X  für v v*  steht).
- Kanten E={{A,B},{A,C},{B,C},{C,D},{C,E},{D,E},{X,A},{X,B},{X,C},{X,D},{X,E}} E' = \{ \{A,B\}, \{A,C\}, \{B,C\}, \{C,D\}, \{C,E\}, \{D,E\}, \{X,A\}, \{X,B\}, \{X,C\}, \{X,D\}, \{X,E\} \} .

Skizze der Korrektheit:
- Wenn G G  einen Hamilton-Pfad hat, dann existiert eine Permutation der Knoten, die alle besucht. In G G'  kann man einen Hamilton-Kreis bilden, indem man v v*  an den Anfang und das Ende des Pfades einfügt (da v v*  mit allen Knoten verbunden ist), z.B. v,v1,v2,,vn,v v*, v_1, v_2, \dotsc, v_n, v* .
- Wenn G G'  einen Hamilton-Kreis hat, muss v v*  im Kreis sein mit zwei Nachbarn u u  und w w . Entfernt man v v* , erhält man einen Hamilton-Pfad von u u  nach w w  in G G .
Daher gilt G G  hat einen Hamilton-Pfad genau dann, wenn G G'  einen Hamilton-Kreis hat.

Subproblem b (3.0/3.0P)

Sei CFG-LEERHEIT das Entscheidungsproblem, ob eine gegebene kontextfreie Grammatik GG kein Wort erzeugt, also ob L(G)=L(G)=\emptyset gilt.

Aussage: 3KNF-SAT p\leq_p CFG-LEERHEIT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von 3KNF-SAT an.
(x1¬x2x3)(¬x1x2x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)
Die Aussage giltDie Aussage gilt nicht
Die Aussage gilt nicht. Beweis: CFG-LEERHEIT ist in P entscheidbar, da die Leerheit einer kontextfreien Grammatik in polynomieller Zeit überprüft werden kann, beispielsweise durch Analyse der Erreichbarkeit und Produktivität von Symbolen. 3KNF-SAT ist NP-vollständig. Unter der Annahme P ≠ NP kann 3KNF-SAT nicht in P liegen. Wenn 3KNF-SAT ≤p CFG-LEERHEIT gelten würde, dann folgt aus CFG-LEERHEIT ∈ P, dass 3KNF-SAT ∈ P, was ein Widerspruch zu P ≠ NP ist. Daher ist die Reduktion nicht möglich.

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

Eingabe: Eine endliche Menge M={m1,...,mk}M=\{m_1, ..., m_k\} und eine Menge T={T1,...,Tn}T=\{T_1, ..., T_n\}  von Teilmengen von MM.

Ausgabe: Enthält TT eine exakte Überdeckung von MM, d.h. gibt es eine Menge STS \subseteq T, sodass jedes Element von MM in genau einer der Teilmengen in SS vorkommt?

Aussage: EXAKTE-ÜBERDECKUNG p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M{1,2,3,4}M\coloneqq\{1,2,3,4\}
T{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1{1}T_1\coloneqq\{1\},
T2{1,3}T_2\coloneqq\{1,3\},
T3{1,2,3}T_3\coloneqq\{1,2,3\},
T4{2,4}T_4\coloneqq\{2,4\},
T5T_5\coloneqq\emptyset.
Die Aussage giltDie Aussage gilt nicht
Die Aussage gilt.

Reduktionsfunktion: Gegeben eine Instanz von EXAKTE-ÜBERDECKUNG mit Menge M={m1,,mk} M = \{m_1, \dotsc, m_k\}  und Teilmengen T={T1,,Tn} T = \{T_1, \dotsc, T_n\} , wird eine CNF-Formel für SAT wie folgt konstruiert:
- Für jede Teilmenge Ti T_i  wird eine boolesche Variable xi x_i  eingeführt, die wahr ist, wenn Ti T_i  in der exakten Überdeckung enthalten ist.
- Für jedes Element mM m \in M :
  - Sei Cm={imTi} C_m = \{ i \mid m \in T_i \}  die Menge der Indizes von Teilmengen, die m m  enthalten.
  - Füge eine Klausel hinzu: iCmxi \bigvee_{i \in C_m} x_i  (stellt sicher, dass m m  mindestens einmal covered wird).
  - Für jedes Paar i,jCm i, j \in C_m  mit i<j i < j , füge eine Klausel hinzu: ¬xi¬xj \neg x_i \lor \neg x_j  (stellt sicher, dass m m  höchstens einmal covered wird).

Die SAT-Formel ist die Konjunktion aller dieser Klauseln.

Angewendet auf die gegebene Instanz:
- M={1,2,3,4} M = \{1, 2, 3, 4\} 
- T={T1,T2,T3,T4,T5} T = \{T_1, T_2, T_3, T_4, T_5\}  mit T1={1} T_1 = \{1\} , T2={1,3} T_2 = \{1,3\} , T3={1,2,3} T_3 = \{1,2,3\} , T4={2,4} T_4 = \{2,4\} , T5= T_5 = \emptyset 
- Variablen: x1,x2,x3,x4,x5 x_1, x_2, x_3, x_4, x_5  für T1,T2,T3,T4,T5 T_1, T_2, T_3, T_4, T_5 

Klauseln für jedes Element:
- Element 1: C1={1,2,3} C_1 = \{1,2,3\}  → Klauseln: x1x2x3 x_1 \lor x_2 \lor x_3 , ¬x1¬x2 \neg x_1 \lor \neg x_2 , ¬x1¬x3 \neg x_1 \lor \neg x_3 , ¬x2¬x3 \neg x_2 \lor \neg x_3 
- Element 2: C2={3,4} C_2 = \{3,4\}  → Klauseln: x3x4 x_3 \lor x_4 , ¬x3¬x4 \neg x_3 \lor \neg x_4 
- Element 3: C3={2,3} C_3 = \{2,3\}  → Klauseln: x2x3 x_2 \lor x_3 , ¬x2¬x3 \neg x_2 \lor \neg x_3 
- Element 4: C4={4} C_4 = \{4\}  → Klausel: x4 x_4 

Die vollständige SAT-Formel ist:
(x1x2x3)(¬x1¬x2)(¬x1¬x3)(¬x2¬x3)(x3x4)(¬x3¬x4)(x2x3)(¬x2¬x3)(x4)
(x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor \neg x_2) \land (\neg x_1 \lor \neg x_3) \land (\neg x_2 \lor \neg x_3) \land (x_3 \lor x_4) \land (\neg x_3 \lor \neg x_4) \land (x_2 \lor x_3) \land (\neg x_2 \lor \neg x_3) \land (x_4)


Skizze der Korrektheit: Die Formel ist genau dann erfüllbar, wenn es eine Auswahl von Teilmengen gibt, die jedes Element genau einmal covered. Die Klauseln garantieren, dass für jedes Element mindestens eine und höchstens eine Teilmenge, die es enthält, ausgewählt ist.

deepseek/deepseek-r1-0528

Exercise 7: Reduktion

Nehmen Sie PNP\P\ne\NP an. Entscheiden Sie unter dieser Annahme, welche der folgenden Aussagen gelten. Die Aussagen sind von der Gestalt „ApBA\le_p B“ für  Entscheidungsprobleme A,BA, B. Wenn die Aussage gilt, dann müssen Sie (1) eine präzise definierte Reduktionsfunktion angeben und (2) die Reduktionsfunktion auf die gegebene Instanz von Problem AA anwenden. Die Korrektheit der Reduktion müssen Sie nur skizzieren. Wenn die Aussage nicht gilt, dann müssen Sie dies beweisen.

Subproblem a (4.0/4.0P)

Sei G=(V,E)G=(V, E) ein ungerichteter Graph. Ein Hamilton-Pfad von GG ist eine Permutation v1,,vnv_1,\dotsc,v_n der Knoten von VV mit {vi,vi+1}E\{v_i, v_{i+1}\} \in E für jedes i{1,...,n1}i \in \{1, ..., n-1\}. Ein Hamilton-Kreis von GG ist ein Hamilton-Pfad von GG, der zusätzlich {vn,v1}E\{v_n, v_1\} \in E erfüllt.

Sei HAMILTON-PFAD das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Pfad hat. Sei HAMILTON-KREIS das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Kreis hat.

Aussage: HAMILTON-PFAD p\le_p HAMILTON-KREIS

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von HAMILTON-PFAD an.
Knoten: A, B, C, D, E
Kanten:
    A -- B
    A -- C
    B -- C
    C -- D
    C -- E
    D -- E
Die Aussage giltDie Aussage gilt nicht
Die Reduktionsfunktion ff wird wie folgt definiert:  
Gegeben einen ungerichteten Graphen G=(V,E)G = (V, E) als Instanz von HAMILTON-PFAD, konstruieren wir einen neuen Graphen f(G)=G=(V,E)f(G) = G' = (V', E'), wobei:
- V=V{s}V' = V \cup \{s\} mit einem neuen Knoten sVs \notin V,
- E=E{{s,v}vV}E' = E \cup \{\{s, v\} \mid v \in V\}.

Diese Reduktion ist polynomiell, da nur ein zusätzlicher Knoten und n=Vn = |V| Kanten hinzugefügt werden.

Korrektheitsskizze:  
- Ja-Instanzen: Hat GG einen Hamilton-Pfad v1,v2,,vnv_1, v_2, \dots, v_n, so bildet s,v1,v2,,vn,ss, v_1, v_2, \dots, v_n, s einen Hamilton-Kreis in GG', da ss mit allen Knoten verbunden ist und somit direkt an v1v_1 und vnv_n angeschlossen ist.  
- Nein-Instanzen: Hat GG' einen Hamilton-Kreis, muss dieser den Knoten ss enthalten. Die beiden Nachbarn von ss im Kreis sind Knoten uu und ww aus VV. Der Pfad zwischen uu und ww in diesem Kreis (ohne ss) ist ein Hamilton-Pfad in GG, da alle Knoten aus VV durchlaufen werden und die Kanten in EE liegen.  

Anwendung auf die gegebene Instanz:  
- Eingabe (HAMILTON-PFAD):  
  - Knoten: V={A,B,C,D,E}V = \{A, B, C, D, E\}  
  - Kanten: E={{A,B},{A,C},{B,C},{C,D},{C,E},{D,E}}E = \{\{A,B\}, \{A,C\}, \{B,C\}, \{C,D\}, \{C,E\}, \{D,E\}\}  
- Ausgabe (HAMILTON-KREIS):  
  - Knoten: V={A,B,C,D,E,s}V' = \{A, B, C, D, E, s\}  
  - Kanten: E=E{{s,A},{s,B},{s,C},{s,D},{s,E}}E' = E \cup \{\{s,A\}, \{s,B\}, \{s,C\}, \{s,D\}, \{s,E\}\}  
  Explizit:  
  - Ursprüngliche Kanten: {A,B},{A,C},{B,C},{C,D},{C,E},{D,E}\{A,B\}, \{A,C\}, \{B,C\}, \{C,D\}, \{C,E\}, \{D,E\}  
  - Hinzugefügte Kanten: {s,A},{s,B},{s,C},{s,D},{s,E}\{s,A\}, \{s,B\}, \{s,C\}, \{s,D\}, \{s,E\}

Subproblem b (3.0/3.0P)

Sei CFG-LEERHEIT das Entscheidungsproblem, ob eine gegebene kontextfreie Grammatik GG kein Wort erzeugt, also ob L(G)=L(G)=\emptyset gilt.

Aussage: 3KNF-SAT p\leq_p CFG-LEERHEIT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von 3KNF-SAT an.
(x1¬x2x3)(¬x1x2x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)
Die Aussage giltDie Aussage gilt nicht
Die Aussage gilt nicht.  
Beweis:  
Angenommen, 3KNF-SATpCFG-LEERHEIT3\text{KNF-SAT} \leq_p \text{CFG-LEERHEIT}.  
- CFG-LEERHEITP\text{CFG-LEERHEIT} \in \P, da in Polynomzeit entscheidbar ist, ob L(G)=L(G) = \emptyset durch Entfernen unerreichbarer/ohne Terminierbarkeit nicht-produktiver Symbole.  
- Unter PNP\P \neq \NP folgt 3KNF-SATP3\text{KNF-SAT} \in \P, da die Reduktion und CFG-LEERHEITP\text{CFG-LEERHEIT} \in \P eine Polynomzeitalgorithmus für 3KNF-SAT3\text{KNF-SAT} implizieren.  
- Aber 3KNF-SAT3\text{KNF-SAT} ist NP\NP-vollständig, sodass 3KNF-SATP3\text{KNF-SAT} \in \P NPP\NP \subseteq \P und somit P=NP\P = \NP impliziert, im Widerspruch zur Annahme PNP\P \neq \NP.  
Folglich existiert keine polynomielle Reduktion von 3KNF-SAT3\text{KNF-SAT} auf CFG-LEERHEIT\text{CFG-LEERHEIT}.

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

Eingabe: Eine endliche Menge M={m1,...,mk}M=\{m_1, ..., m_k\} und eine Menge T={T1,...,Tn}T=\{T_1, ..., T_n\}  von Teilmengen von MM.

Ausgabe: Enthält TT eine exakte Überdeckung von MM, d.h. gibt es eine Menge STS \subseteq T, sodass jedes Element von MM in genau einer der Teilmengen in SS vorkommt?

Aussage: EXAKTE-ÜBERDECKUNG p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M{1,2,3,4}M\coloneqq\{1,2,3,4\}
T{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1{1}T_1\coloneqq\{1\},
T2{1,3}T_2\coloneqq\{1,3\},
T3{1,2,3}T_3\coloneqq\{1,2,3\},
T4{2,4}T_4\coloneqq\{2,4\},
T5T_5\coloneqq\emptyset.
Die Aussage giltDie Aussage gilt nicht
Reduktionsfunktion:  
Gegeben eine Instanz (M,T)(M, T) von EXAKTE-ÜBERDECKUNG mit M={m1,,mk}M = \{m_1, \dotsc, m_k\} und T={T1,,Tn}T = \{T_1, \dotsc, T_n\}, konstruieren wir eine boolesche Formel ϕ\phi in KNF wie folgt:
- Variablen: Für jede Teilmenge TiT_i definieren wir eine Variable xix_i, die wahr ist, wenn TiT_i in der Überdeckung SS enthalten ist.
- Klauseln: 
  1. Für jedes Element mMm \in M:
     - Klausel für Mindestüberdeckung: i:mTixi\bigvee_{i: m \in T_i} x_i (mindestens ein TiT_i mit mTim \in T_i wird ausgewählt).
     - Klauseln für Eindeutigkeit: Für jedes Paar i,ji, j mit i<ji < j und mTiTjm \in T_i \cap T_j die Klausel ¬xi¬xj\neg x_i \lor \neg x_j (höchstens ein TiT_i wird ausgewählt).
  2. Leere Teilmengen Ti=T_i = \emptyset führen zu keiner Klausel, da keine Elemente abgedeckt werden.

Die Formel ϕ\phi ist die Konjunktion aller Klauseln. Die Reduktion läuft in Polynomzeit, da die Anzahl der Klauseln durch O(kn2)O(k \cdot n^2) beschränkt ist (mit M=k|M| = k, T=n|T| = n).

Korrektheitsskizze:  
- Ja-Instanzen: Wenn es eine exakte Überdeckung STS \subseteq T gibt, setze xi=1x_i = 1 für TiST_i \in S, sonst 00. Jede Klausel ist erfüllt: Die Mindestüberdeckungs-Klausel gilt für jedes mm, da genau ein TiT_i mit mTim \in T_i in SS ist. Die Eindeutigkeits-Klauseln sind erfüllt, da kein mm in mehreren TiST_i \in S vorkommt.
- Nein-Instanzen: Wenn kein exakte Überdeckung existiert, ist ϕ\phi unerfüllbar, da entweder ein Element nicht abgedeckt wird (Mindestüberdeckung verletzt) oder sich Überlappungen ergeben (Eindeutigkeit verletzt).

Anwendung auf die gegebene Instanz:  
- Eingabe:
  - M={1,2,3,4}M = \{1, 2, 3, 4\}
  - T={T1,T2,T3,T4,T5}T = \{T_1, T_2, T_3, T_4, T_5\} mit T1={1}T_1 = \{1\}, T2={1,3}T_2 = \{1, 3\}, T3={1,2,3}T_3 = \{1, 2, 3\}, T4={2,4}T_4 = \{2, 4\}, T5=T_5 = \emptyset.
- Variablen: x1x_1 für T1T_1, x2x_2 für T2T_2, x3x_3 für T3T_3, x4x_4 für T4T_4, x5x_5 für T5T_5 (entfällt, da in keiner Klausel).
- Klauseln:
  - m=1m=1:  
    - I1={1,2,3}I_1 = \{1,2,3\} → Klausel: x1x2x3x_1 \lor x_2 \lor x_3  
    - Paare: (1,2),(1,3),(2,3)(1,2),(1,3),(2,3) → Klauseln: ¬x1¬x2\neg x_1 \lor \neg x_2, ¬x1¬x3\neg x_1 \lor \neg x_3, ¬x2¬x3\neg x_2 \lor \neg x_3  
  - m=2m=2:  
    - I2={3,4}I_2 = \{3,4\} → Klausel: x3x4x_3 \lor x_4  
    - Paar: (3,4)(3,4) → Klausel: ¬x3¬x4\neg x_3 \lor \neg x_4  
  - m=3m=3:  
    - I3={2,3}I_3 = \{2,3\} → Klausel: x2x3x_2 \lor x_3  
    - Paar: (2,3)(2,3) → Klausel: ¬x2¬x3\neg x_2 \lor \neg x_3 (bereits vorhanden)  
  - m=4m=4:  
    - I4={4}I_4 = \{4\} → Klausel: x4x_4  
    - Kein Paar.  
- KNF-Formel ϕ\phi:  
  (x1x2x3)(¬x1¬x2)(¬x1¬x3)(¬x2¬x3)(x3x4)(¬x3¬x4)(x2x3)(x4)
  (x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor \neg x_2) \land (\neg x_1 \lor \neg x_3) \land (\neg x_2 \lor \neg x_3) \land (x_3 \lor x_4) \land (\neg x_3 \lor \neg x_4) \land (x_2 \lor x_3) \land (x_4)
  

google/gemini-2.5-pro

Exercise 7: Reduktion

Nehmen Sie PNP\P\ne\NP an. Entscheiden Sie unter dieser Annahme, welche der folgenden Aussagen gelten. Die Aussagen sind von der Gestalt „ApBA\le_p B“ für  Entscheidungsprobleme A,BA, B. Wenn die Aussage gilt, dann müssen Sie (1) eine präzise definierte Reduktionsfunktion angeben und (2) die Reduktionsfunktion auf die gegebene Instanz von Problem AA anwenden. Die Korrektheit der Reduktion müssen Sie nur skizzieren. Wenn die Aussage nicht gilt, dann müssen Sie dies beweisen.

Subproblem a (4.0/4.0P)

Sei G=(V,E)G=(V, E) ein ungerichteter Graph. Ein Hamilton-Pfad von GG ist eine Permutation v1,,vnv_1,\dotsc,v_n der Knoten von VV mit {vi,vi+1}E\{v_i, v_{i+1}\} \in E für jedes i{1,...,n1}i \in \{1, ..., n-1\}. Ein Hamilton-Kreis von GG ist ein Hamilton-Pfad von GG, der zusätzlich {vn,v1}E\{v_n, v_1\} \in E erfüllt.

Sei HAMILTON-PFAD das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Pfad hat. Sei HAMILTON-KREIS das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Kreis hat.

Aussage: HAMILTON-PFAD p\le_p HAMILTON-KREIS

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von HAMILTON-PFAD an.
Knoten: A, B, C, D, E
Kanten:
    A -- B
    A -- C
    B -- C
    C -- D
    C -- E
    D -- E
Die Aussage giltDie Aussage gilt nicht
Die Aussage HAMILTON-PFAD $\le_p$ HAMILTON-KREIS gilt.

#### (1) Reduktionsfunktion

Sei $G=(V, E)$ eine beliebige Instanz von HAMILTON-PFAD. Wir konstruieren eine Instanz $G'=(V', E')$ von HAMILTON-KREIS wie folgt:

1.  Wir fügen einen neuen Knoten $w$ hinzu, der nicht in $V$ ist. Die neue Knotenmenge ist $V' = V \cup \{w\}$.
2.  Wir behalten alle Kanten aus $E$ bei und fügen für jeden Knoten $v \in V$ eine Kante zwischen $v$ und dem neuen Knoten $w$ hinzu. Die neue Kantenmenge ist $E' = E \cup \{ \{v, w\} \mid v \in V \}$.

Diese Konstruktion kann in Polynomialzeit bezüglich der Größe von $G$ durchgeführt werden.

#### (2) Anwendung auf die gegebene Instanz

Die gegebene Instanz von HAMILTON-PFAD ist der Graph $G=(V,E)$ mit:
*   Knoten $V = \{\text{A, B, C, D, E}\}$
*   Kanten $E = \{\{\text{A, B}\}, \{\text{A, C}\}, \{\text{B, C}\}, \{\text{C, D}\}, \{\text{C, E}\}, \{\text{D, E}\}\}$

Wir wenden die obige Reduktion an, um den Graphen $G'=(V',E')$ zu konstruieren:
*   **Neue Knotenmenge $V'$**: Wir fügen einen neuen Knoten hinzu, den wir $W$ nennen.
    $V' = \{\text{A, B, C, D, E, W}\}$
*   **Neue Kantenmenge $E'$**: Wir behalten alle Kanten aus $E$ und fügen Kanten von $W$ zu allen anderen Knoten hinzu.
    $E' = E \cup \{\{\text{W, A}\}, \{\text{W, B}\}, \{\text{W, C}\}, \{\text{W, D}\}, \{\text{W, E}\}\}$

Der resultierende Graph $G'$ hat somit die folgenden Kanten:
$\{\text{A, B}\}, \{\text{A, C}\}, \{\text{B, C}\}, \{\text{C, D}\}, \{\text{C, E}\}, \{\text{D, E}\}, \{\text{W, A}\}, \{\text{W, B}\}, \{\text{W, C}\}, \{\text{W, D}\}, \{\text{W, E}\}$.

*Zur Veranschaulichung: Der gegebene Graph $G$ hat einen Hamilton-Pfad, z.B. A-B-C-E-D. Gemäß unserer Reduktion sollte $G'$ einen Hamilton-Kreis haben. Der Pfad A-B-C-E-D in $G$ wird zu dem Kreis A-B-C-E-D-W-A in $G'$.*

#### Skizze der Korrektheit

Wir müssen zeigen, dass $G$ genau dann einen Hamilton-Pfad hat, wenn $G'$ einen Hamilton-Kreis hat.

**($\Rightarrow$) Annahme: $G$ hat einen Hamilton-Pfad.**
Sei $P = (v_1, v_2, \dots, v_n)$ ein Hamilton-Pfad in $G$. Dieser Pfad besucht jeden Knoten in $V$ genau einmal. Die Endknoten des Pfades sind $v_1$ und $v_n$.
In $G'$ können wir den Kreis $C = (v_1, v_2, \dots, v_n, W, v_1)$ bilden.
*   Die Kanten $\{v_i, v_{i+1}\}$ für $i \in \{1, \dots, n-1\}$ sind Kanten von $P$ und somit in $E \subseteq E'$.
*   Die Kanten $\{v_n, W\}$ und $\{W, v_1\}$ wurden bei der Konstruktion von $G'$ hinzugefügt und sind somit in $E'$.
Der Kreis $C$ besucht alle Knoten in $V' = V \cup \{W\}$ genau einmal. Also ist $C$ ein Hamilton-Kreis in $G'$.

**($\Leftarrow$) Annahme: $G'$ hat einen Hamilton-Kreis.**
Sei $C$ ein Hamilton-Kreis in $G'$. Da $W$ ein Knoten in $G'$ ist, muss $C$ den Knoten $W$ enthalten. Die Nachbarn von $W$ sind ausschließlich Knoten aus $V$. Seien $v_i, v_j \in V$ die beiden Nachbarn von $W$ in dem Kreis $C$. Der Kreis hat also die Form $(v_i, \dots, v_j, W, v_i)$.
Das Teilstück von $v_i$ nach $v_j$, nennen wir es $P'$, muss alle Knoten in $V$ genau einmal besuchen, da $C$ ein Hamilton-Kreis ist und alle Knoten aus $V'$ besucht. Da $W$ nicht zwischen $v_i$ und $v_j$ auf dem Pfad $P'$ liegt, können alle Kanten in $P'$ nur Knoten aus $V$ verbinden. Somit müssen alle Kanten von $P'$ aus der ursprünglichen Kantenmenge $E$ stammen.
Folglich ist $P'$ ein Pfad im Graphen $G$, der alle Knoten von $V$ genau einmal besucht. $P'$ ist also ein Hamilton-Pfad in $G$.

Subproblem b (3.0/3.0P)

Sei CFG-LEERHEIT das Entscheidungsproblem, ob eine gegebene kontextfreie Grammatik GG kein Wort erzeugt, also ob L(G)=L(G)=\emptyset gilt.

Aussage: 3KNF-SAT p\leq_p CFG-LEERHEIT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von 3KNF-SAT an.
(x1¬x2x3)(¬x1x2x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)
Die Aussage giltDie Aussage gilt nicht
Die Aussage „3KNF-SAT $\le_p$ CFG-LEERHEIT“ gilt nicht unter der Annahme $\P \ne \NP$.

#### Beweis

Wir führen einen Widerspruchsbeweis.

1.  **Annahme:** Nehmen wir an, die Aussage gilt, d.h., es existiert eine polynomialzeitliche Reduktion $f$ von 3KNF-SAT auf CFG-LEERHEIT. Das bedeutet, für jede 3KNF-Formel $\phi$ können wir in Polynomialzeit eine kontextfreie Grammatik $G_\phi = f(\phi)$ konstruieren, sodass gilt:
    $\phi$ ist erfüllbar $\iff L(G_\phi) \ne \emptyset$.
    Dies ist äquivalent zu:
    $\phi$ ist **nicht** erfüllbar $\iff L(G_\phi) = \emptyset$.

2.  **Analyse von CFG-LEERHEIT:** Das Problem CFG-LEERHEIT, also zu entscheiden, ob für eine gegebene CFG $G$ die Sprache $L(G)$ leer ist, liegt in der Komplexitätsklasse $\P$.
    *   *Skizze des Algorithmus:* Man kann die Menge aller Nichtterminalsymbole bestimmen, die eine Kette von Terminalsymbolen erzeugen können.
        1.  Initialisiere eine Menge $M$ mit allen Nichtterminalen $A$, für die eine Regel $A \to w$ existiert, wobei $w$ nur aus Terminalen besteht.
        2.  Füge iterativ zu $M$ jedes Nichtterminal $B$ hinzu, für das eine Regel $B \to \alpha$ existiert, wobei alle Symbole in $\alpha$ (sowohl Terminale als auch Nichtterminale) bereits in $M$ bzw. der Menge der Terminale sind.
        3.  Wiederhole Schritt 2, bis sich $M$ nicht mehr ändert.
        4.  $L(G)$ ist genau dann nicht leer, wenn das Startsymbol $S$ in der finalen Menge $M$ enthalten ist.
    *_Dieser Algorithmus terminiert in polynomialer Zeit bezüglich der Größe der Grammatik._

3.  **Widerspruchsargumentation:**
    *   Wenn 3KNF-SAT $\le_p$ CFG-LEERHEIT gilt und CFG-LEERHEIT $\in \P$, dann würde aus der Definition der polynomialen Reduktion folgen, dass auch 3KNF-SAT $\in \P$ sein muss.
    *   *Begründung:* Ein Algorithmus für 3KNF-SAT könnte eine gegebene Formel $\phi$ mittels der Reduktion $f$ in eine Grammatik $G_\phi$ umwandeln und dann den P-Zeit-Algorithmus für CFG-LEERHEIT (bzw. dessen Komplement) auf $G_\phi$ anwenden, um die Erfüllbarkeit von $\phi$ zu entscheiden. Die Gesamtlaufzeit wäre polynomial.
    *   Das Problem 3KNF-SAT ist jedoch NP-vollständig. Wenn ein NP-vollständiges Problem in $\P$ liegt, dann folgt daraus, dass $\P = \NP$.
    *   Dies steht im direkten Widerspruch zur expliziten Annahme der Aufgabe, dass $\P \ne \NP$ gilt.

4.  **Schlussfolgerung:** Unsere ursprüngliche Annahme, dass 3KNF-SAT $\le_p$ CFG-LEERHEIT gilt, muss falsch sein. Daher gilt die Aussage nicht.

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

Eingabe: Eine endliche Menge M={m1,...,mk}M=\{m_1, ..., m_k\} und eine Menge T={T1,...,Tn}T=\{T_1, ..., T_n\}  von Teilmengen von MM.

Ausgabe: Enthält TT eine exakte Überdeckung von MM, d.h. gibt es eine Menge STS \subseteq T, sodass jedes Element von MM in genau einer der Teilmengen in SS vorkommt?

Aussage: EXAKTE-ÜBERDECKUNG p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M{1,2,3,4}M\coloneqq\{1,2,3,4\}
T{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1{1}T_1\coloneqq\{1\},
T2{1,3}T_2\coloneqq\{1,3\},
T3{1,2,3}T_3\coloneqq\{1,2,3\},
T4{2,4}T_4\coloneqq\{2,4\},
T5T_5\coloneqq\emptyset.
Die Aussage giltDie Aussage gilt nicht
Die Aussage EXAKTE-ÜBERDECKUNG $\le_p$ SAT gilt. Da EXAKTE-ÜBERDECKUNG NP-vollständig ist und SAT ebenfalls NP-vollständig ist, existiert eine solche Reduktion. Wir geben eine konkrete Reduktionsfunktion an.

#### (1) Reduktionsfunktion

Sei eine Instanz von EXAKTE-ÜBERDECKUNG gegeben durch eine Menge $M=\{m_1, ..., m_k\}$ und eine Menge von Teilmengen $T=\{T_1, ..., T_n\}$. Wir konstruieren eine aussagenlogische Formel $\phi$ in konjunktiver Normalform (KNF), die genau dann erfüllbar ist, wenn eine exakte Überdeckung existiert.

1.  **Variablen:** Für jede Teilmenge $T_i \in T$ (für $i=1, ..., n$) führen wir eine boolesche Variable $x_i$ ein. Die Intuition ist, dass $x_i$ genau dann wahr ist, wenn die Teilmenge $T_i$ für die exakte Überdeckung ausgewählt wird.

2.  **Klauseln:** Wir konstruieren $\phi$ als Konjunktion zweier Arten von Klauseln:

    a.  **Jedes Element von $M$ wird überdeckt:** Für jedes Element $m_j \in M$ muss es mindestens eine ausgewählte Teilmenge $T_i$ geben, die $m_j$ enthält. Dies wird durch die folgende Klausel für jedes $j \in \{1,...,k\}$ sichergestellt:
        \[ C_j^{\text{cover}} = \bigvee_{i \text{ s.d. } m_j \in T_i} x_i \]
        Falls für ein $m_j$ keine Teilmenge $T_i$ existiert, die es enthält, ist die Disjunktion leer und somit falsch, was die resultierende Formel unerfüllbar macht (korrekt, da keine Überdeckung möglich ist).

    b.  **Jedes Element von $M$ wird höchstens einmal überdeckt:** Für jedes Element $m_j \in M$ und für jedes Paar von verschiedenen Teilmengen $T_i, T_l \in T$ (mit $i \neq l$), die beide $m_j$ enthalten, können nicht beide für die Überdeckung ausgewählt werden. Dies wird durch die folgende Klausel für jedes $j \in \{1,...,k\}$ und jedes Paar $i,l$ mit $i < l$, sodass $m_j \in T_i$ und $m_j \in T_l$, sichergestellt:
        \[ C_{j,i,l}^{\text{unique}} = (\neg x_i \vee \neg x_l) \]

Die finale Formel $\phi$ ist die Konjunktion all dieser Klauseln:
\[ \phi = \left( \bigwedge_{j=1}^{k} C_j^{\text{cover}} \right) \wedge \left( \bigwedge_{j=1}^{k} \bigwedge_{\substack{i<l \\ m_j \in T_i \\ m_j \in T_l}} C_{j,i,l}^{\text{unique}} \right) \]
Die Konstruktion dieser Formel kann in Polynomialzeit bezüglich der Größe der EXAKTE-ÜBERDECKUNG-Instanz $(|M|, |T|)$ erfolgen.

#### (2) Anwendung auf die gegebene Instanz

Gegebene Instanz:
$M=\{1,2,3,4\}$
$T=\{T_1=\{1\}, T_2=\{1,3\}, T_3=\{1,2,3\}, T_4=\{2,4\}, T_5=\emptyset\}$

Wir führen Variablen $x_1, x_2, x_3, x_4, x_5$ ein.

**a. Klauseln für die Überdeckung:**
*   Für $m=1$ (in $T_1, T_2, T_3$): $(x_1 \vee x_2 \vee x_3)$
*   Für $m=2$ (in $T_3, T_4$): $(x_3 \vee x_4)$
*   Für $m=3$ (in $T_2, T_3$): $(x_2 \vee x_3)$
*   Für $m=4$ (in $T_4$): $(x_4)$
(Anmerkung: $T_5$ enthält kein Element und taucht daher in diesen Klauseln nicht auf).

**b. Klauseln für die Eindeutigkeit:**
*   Für $m=1$ (in $T_1, T_2, T_3$): Wir benötigen Klauseln für die Paare $(T_1,T_2), (T_1,T_3), (T_2,T_3)$.
    $(\neg x_1 \vee \neg x_2) \wedge (\neg x_1 \vee \neg x_3) \wedge (\neg x_2 \vee \neg x_3)$
*   Für $m=2$ (in $T_3, T_4$): Wir benötigen eine Klausel für das Paar $(T_3, T_4)$.
    $(\neg x_3 \vee \neg x_4)$
*   Für $m=3$ (in $T_2, T_3$): Wir benötigen eine Klausel für das Paar $(T_2, T_3)$.
    $(\neg x_2 \vee \neg x_3)$ (Diese Klausel wurde bereits für $m=1$ erzeugt).
*   Für $m=4$ (nur in $T_4$): Keine Paare, also keine Klauseln.

**Die resultierende SAT-Formel $\phi$ ist:**
$ (x_1 \vee x_2 \vee x_3) \wedge (x_3 \vee x_4) \wedge (x_2 \vee x_3) \wedge (x_4) \wedge $
$ (\neg x_1 \vee \neg x_2) \wedge (\neg x_1 \vee \neg x_3) \wedge (\neg x_2 \vee \neg x_3) \wedge (\neg x_3 \vee \neg x_4) $

*Zur Veranschaulichung:* Die gegebene Instanz hat eine exakte Überdeckung $S=\{T_2, T_4\}$. Die entsprechende Belegung ist $x_2=\text{wahr}, x_4=\text{wahr}$ und $x_1=x_3=x_5=\text{falsch}$. Man kann leicht überprüfen, dass diese Belegung die Formel $\phi$ erfüllt.*

#### Skizze der Korrektheit

Wir zeigen, dass die gegebene EXAKTE-ÜBERDECKUNG-Instanz $(M, T)$ eine Lösung hat genau dann, wenn die konstruierte Formel $\phi$ erfüllbar ist.

**($\Rightarrow$) Annahme: Es existiert eine exakte Überdeckung $S \subseteq T$.**
Wir definieren eine Variablenbelegung $A$ wie folgt: $A(x_i) = \text{wahr}$, falls $T_i \in S$, und $A(x_i) = \text{falsch}$, falls $T_i \notin S$.
*   Die Klauseln der Art $C_j^{\text{cover}}$ sind erfüllt: Da $S$ eine Überdeckung ist, ist jedes $m_j \in M$ in mindestens einem (sogar genau einem) $T_i \in S$ enthalten. Für dieses $T_i$ gilt $A(x_i)=\text{wahr}$, was die Disjunktion $C_j^{\text{cover}}$ wahr macht.
*   Die Klauseln der Art $C_{j,i,l}^{\text{unique}}$ sind erfüllt: Diese Klausel hat die Form $(\neg x_i \vee \neg x_l)$. Wäre sie falsch, müssten $A(x_i)$ und $A(x_l)$ beide wahr sein. Das würde bedeuten, $T_i \in S$ und $T_l \in S$. Da aber $m_j$ in beiden Mengen ist, $T_i \cap T_l \ne \emptyset$, widerspricht dies der Eigenschaft von $S$, eine exakte Überdeckung zu sein (d.h. die Mengen in $S$ müssen paarweise disjunkt sein). Also kann dieser Fall nicht eintreten.
Somit erfüllt $A$ die Formel $\phi$.

**($\Leftarrow$) Annahme: Die Formel $\phi$ ist erfüllbar.**
Sei $A$ eine erfüllende Belegung. Wir definieren eine Lösungsmenge $S = \{ T_i \mid A(x_i)=\text{wahr} \}$. Wir müssen zeigen, dass $S$ eine exakte Überdeckung von $M$ ist.
*   Sei $m_j \in M$ ein beliebiges Element. Da die Klausel $C_j^{\text{cover}} = \bigvee_{i \text{ s.d. } m_j \in T_i} x_i$ erfüllt sein muss, muss mindestens ein $A(x_i)$ wahr sein für ein $i$, wo $m_j \in T_i$. Das bedeutet, $m_j$ ist in mindestens einer Menge aus $S$ enthalten.
*   Angenommen, $m_j$ ist in zwei verschiedenen Mengen $T_i, T_l \in S$ enthalten ($i \neq l$). Dann wären $A(x_i)$ und $A(x_l)$ beide wahr. Dies würde aber die Klausel $C_{j,i,l}^{\text{unique}} = (\neg x_i \vee \neg x_l)$ falsch machen, was der Annahme widerspricht, dass $A$ eine erfüllende Belegung ist.
Somit ist jedes Element von $M$ in genau einer Menge aus $S$ enthalten. $S$ ist also eine exakte Überdeckung.

openai/gpt-5

Exercise 7: Reduktion

Nehmen Sie PNP\P\ne\NP an. Entscheiden Sie unter dieser Annahme, welche der folgenden Aussagen gelten. Die Aussagen sind von der Gestalt „ApBA\le_p B“ für  Entscheidungsprobleme A,BA, B. Wenn die Aussage gilt, dann müssen Sie (1) eine präzise definierte Reduktionsfunktion angeben und (2) die Reduktionsfunktion auf die gegebene Instanz von Problem AA anwenden. Die Korrektheit der Reduktion müssen Sie nur skizzieren. Wenn die Aussage nicht gilt, dann müssen Sie dies beweisen.

Subproblem a (4.0/4.0P)

Sei G=(V,E)G=(V, E) ein ungerichteter Graph. Ein Hamilton-Pfad von GG ist eine Permutation v1,,vnv_1,\dotsc,v_n der Knoten von VV mit {vi,vi+1}E\{v_i, v_{i+1}\} \in E für jedes i{1,...,n1}i \in \{1, ..., n-1\}. Ein Hamilton-Kreis von GG ist ein Hamilton-Pfad von GG, der zusätzlich {vn,v1}E\{v_n, v_1\} \in E erfüllt.

Sei HAMILTON-PFAD das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Pfad hat. Sei HAMILTON-KREIS das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Kreis hat.

Aussage: HAMILTON-PFAD p\le_p HAMILTON-KREIS

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von HAMILTON-PFAD an.
Knoten: A, B, C, D, E
Kanten:
    A -- B
    A -- C
    B -- C
    C -- D
    C -- E
    D -- E
Die Aussage giltDie Aussage gilt nicht
Reduktionsfunktion f:
Gegeben einen ungerichteten Graphen G = (V, E). Erzeuge G' = (V', E') mit
- V' = V ∪ {s}, wobei s ein neuer Knoten ist,
- E' = E ∪ {{s, v} | v ∈ V}.
Also: Füge einen neuen Knoten s hinzu und verbinde ihn mit allen Knoten aus V.
Laufzeit: O(|V| + |E|).

Korrektheit (Skizze):
- (⇒) Hat G einen Hamilton-Pfad v1, …, vn, so ist s–v1–…–vn–s ein Hamilton-Kreis in G', da s mit v1 und vn adjazent ist.
- (⇐) Hat G' einen Hamilton-Kreis, so muss dieser s enthalten (da s neu und alle Grad ≥ 2; insbesondere s ist mit allen verbunden). Entfernt man s aus dem Kreis, bleibt ein Hamilton-Pfad in G.

Anwendung auf die gegebene Instanz:
G = (V, E) mit
- V = {A, B, C, D, E}
- E = {A–B, A–C, B–C, C–D, C–E, D–E}
Dann ist f(G) = G' = (V', E') mit
- V' = {A, B, C, D, E, s}
- E' = {A–B, A–C, B–C, C–D, C–E, D–E, s–A, s–B, s–C, s–D, s–E}

(Beispiel eines Hamilton-Kreises in G': s–A–B–C–D–E–s.)

Subproblem b (3.0/3.0P)

Sei CFG-LEERHEIT das Entscheidungsproblem, ob eine gegebene kontextfreie Grammatik GG kein Wort erzeugt, also ob L(G)=L(G)=\emptyset gilt.

Aussage: 3KNF-SAT p\leq_p CFG-LEERHEIT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von 3KNF-SAT an.
(x1¬x2x3)(¬x1x2x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)
Die Aussage giltDie Aussage gilt nicht
Beweis, dass die Aussage (unter Annahme P ≠ NP) nicht gilt:

- CFG-LEERHEIT ist in P: Man kann in Polynomialzeit die Menge der „erzeugenden“ Nichtterminale berechnen (Fixpunkt-Verfahren: Ein Nichtterminal ist erzeugend, wenn es eine Regel hat, deren rechte Seite nur aus Terminalen und bereits als erzeugend markierten Nichtterminalen besteht). Dann gilt L(G) = ∅ genau dann, wenn das Startsymbol nicht erzeugend ist. Diese Prozedur läuft in Zeit poly(|G|).

- Angenommen, es gäbe eine polynomielle Many-One-Reduktion 3KNF-SAT ≤p CFG-LEERHEIT. Dann ließe sich 3KNF-SAT in Polynomialzeit lösen, indem man zu einer Formel φ die Grammatik f(φ) berechnet und CFG-LEERHEIT in Polynomialzeit entscheidet. Das impliziert 3KNF-SAT ∈ P, also NP ⊆ P und damit P = NP — im Widerspruch zur Annahme P ≠ NP.

Folglich kann eine solche Reduktion nicht existieren.

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

Eingabe: Eine endliche Menge M={m1,...,mk}M=\{m_1, ..., m_k\} und eine Menge T={T1,...,Tn}T=\{T_1, ..., T_n\}  von Teilmengen von MM.

Ausgabe: Enthält TT eine exakte Überdeckung von MM, d.h. gibt es eine Menge STS \subseteq T, sodass jedes Element von MM in genau einer der Teilmengen in SS vorkommt?

Aussage: EXAKTE-ÜBERDECKUNG p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M{1,2,3,4}M\coloneqq\{1,2,3,4\}
T{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1{1}T_1\coloneqq\{1\},
T2{1,3}T_2\coloneqq\{1,3\},
T3{1,2,3}T_3\coloneqq\{1,2,3\},
T4{2,4}T_4\coloneqq\{2,4\},
T5T_5\coloneqq\emptyset.
Die Aussage giltDie Aussage gilt nicht
Reduktionsfunktion f:
Gegeben (M = {m_1, …, m_k}, T = {T_1, …, T_n}). Erzeuge eine CNF-Formel φ über Variablen x_1, …, x_n, wobei x_j = 1 bedeutet „T_j wird in die Überdeckung gewählt“.
Für jedes Element m_i definiere J_i := { j ∈ {1,…,n} | m_i ∈ T_j } und füge hinzu:
- Genau-eins-Nebenbedingung pro m_i durch
  • Mindestens-eins: (∨_{j ∈ J_i} x_j)  (falls J_i = ∅, füge die leere Klausel hinzu)
  • Höchstens-eins: für alle j ≠ ℓ in J_i die Klausel (¬x_j ∨ ¬x_ℓ).
Ausgabe ist φ = ∧_{i=1}^k [ (∨_{j∈J_i} x_j) ∧ ∧_{j<ℓ, j,ℓ∈J_i} (¬x_j ∨ ¬x_ℓ) ].
Laufzeit: polynomiell in |M| + ∑_j |T_j|.

Korrektheit (Skizze):
- (⇒) Hat S ⊆ T eine exakte Überdeckung, setze x_j = 1 genau für T_j ∈ S. Dann ist für jedes m_i genau ein j ∈ J_i gewählt: „mindestens-eins“ und alle „höchstens-eins“-Klauseln sind erfüllt.
- (⇐) Erfüllt eine Belegung φ, dann hat für jedes m_i genau eine der x_j mit j ∈ J_i den Wert 1. Die gewählten Mengen sind paarweise disjunkt und überdecken M: genau eine Treffermenge pro Element ⇒ exakte Überdeckung.

Anwendung auf die Instanz:
M = {1,2,3,4}, T_1={1}, T_2={1,3}, T_3={1,2,3}, T_4={2,4}, T_5=∅.
J-Mengen:
- J_1 = {1,2,3}, J_2 = {3,4}, J_3 = {2,3}, J_4 = {4}.

CNF-Formel φ:
- Mindestens-eins:
  (x_1 ∨ x_2 ∨ x_3) ∧ (x_3 ∨ x_4) ∧ (x_2 ∨ x_3) ∧ (x_4)
- Höchstens-eins (einzigartige Paare):
  (¬x_1 ∨ ¬x_2) ∧ (¬x_1 ∨ ¬x_3) ∧ (¬x_2 ∨ ¬x_3) ∧ (¬x_3 ∨ ¬x_4)

Hinweis: x_5 kommt in keiner Klausel vor (T_5 = ∅).

Beispielbelegung, die φ erfüllt: x_2 = 1, x_4 = 1, x_1 = x_3 = 0 (x_5 beliebig). Dies entspricht der exakten Überdeckung S = {T_2, T_4}.

openai/gpt-oss-120b

Exercise 7: Reduktion

Nehmen Sie PNP\P\ne\NP an. Entscheiden Sie unter dieser Annahme, welche der folgenden Aussagen gelten. Die Aussagen sind von der Gestalt „ApBA\le_p B“ für  Entscheidungsprobleme A,BA, B. Wenn die Aussage gilt, dann müssen Sie (1) eine präzise definierte Reduktionsfunktion angeben und (2) die Reduktionsfunktion auf die gegebene Instanz von Problem AA anwenden. Die Korrektheit der Reduktion müssen Sie nur skizzieren. Wenn die Aussage nicht gilt, dann müssen Sie dies beweisen.

Subproblem a (4.0/4.0P)

Sei G=(V,E)G=(V, E) ein ungerichteter Graph. Ein Hamilton-Pfad von GG ist eine Permutation v1,,vnv_1,\dotsc,v_n der Knoten von VV mit {vi,vi+1}E\{v_i, v_{i+1}\} \in E für jedes i{1,...,n1}i \in \{1, ..., n-1\}. Ein Hamilton-Kreis von GG ist ein Hamilton-Pfad von GG, der zusätzlich {vn,v1}E\{v_n, v_1\} \in E erfüllt.

Sei HAMILTON-PFAD das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Pfad hat. Sei HAMILTON-KREIS das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Kreis hat.

Aussage: HAMILTON-PFAD p\le_p HAMILTON-KREIS

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von HAMILTON-PFAD an.
Knoten: A, B, C, D, E
Kanten:
    A -- B
    A -- C
    B -- C
    C -- D
    C -- E
    D -- E
Die Aussage giltDie Aussage gilt nicht
**Reduktionsfunktion $f$ (Hamilton‑Pfad → Hamilton‑Kreis)**  

Eingabe: ein ungerichteter Graph $G=(V,E)$.  
Ausgabe: der Graph $G' = f(G) = (V\cup\{u\}, E')$, wobei  

\[
E' = E \;\cup\; \bigl\{\,\{u,v\}\mid v\in V\,\bigr\}.
\]

Der neue Knoten $u$ wird also zu allen ursprünglichen Knoten adjazent gemacht (ein *universeller* Knoten).

---

**Anwendung von $f$ auf die gegebene Instanz**

Ursprüngliche Knoten: $V=\{A,B,C,D,E\}$  

Ursprüngliche Kanten:  
\[
\{A,B\},\; \{A,C\},\; \{B,C\},\; \{C,D\},\; \{C,E\},\; \{D,E\}.
\]

Wir führen einen neuen Knoten $U$ ein und verbinden ihn mit allen vorhandenen Knoten:

\[
\{U,A\},\{U,B\},\{U,C\},\{U,D\},\{U,E\}.
\]

Damit ist das Ergebnis‑Graph $G' = (V\cup\{U\},E')$ mit  

Knoten: $A,B,C,D,E,U$  

Kanten:
\[
\begin{aligned}
& A\!-\!B,\; A\!-\!C,\; B\!-\!C,\; C\!-\!D,\; C\!-\!E,\; D\!-\!E,\\
& U\!-\!A,\; U\!-\!B,\; U\!-\!C,\; U\!-\!D,\; U\!-\!E.
\end{aligned}
\]

---

**Korrektheit (Skizze)**  

*„$\Rightarrow$“*:  
Angenommen $G$ besitzt einen Hamilton‑Pfad $v_1,\dots ,v_n$.  
Füge den neuen Knoten $u$ am Anfang und am Ende des ein:
\[
u, v_1, v_2,\dots ,v_n, u .
\]
Da $u$ zu jedem $v_i$ adjazent ist, bilden diese Knoten eine Hamilton‑Kreis in $G'$.

*„$\Leftarrow$“*:  
Angenommen $G'$ besitzt einen Hamilton‑Kreis.  
Da $u$ der einzige mit Grad $|V|$ ist, muss $u$ im Kreis genau zweimal vorkommen – unmittelbar vor und nach zwei Nachbarn $x,y\in V$.  
Entfernt man $u$ aus dem Kreis, bleibt ein Pfad $x,\dots ,y$ der alle ursprünglichen Knoten $V$ exakt einmal besucht; also ist das ein Hamilton‑Pfad in $G$.

Damit gilt $G$ hat einen Hamilton‑Pfad  ⇔  $f(G)$ hat einen Hamilton‑Kreis, also ist $f$ eine polynomialzeit‑berechenbare Reduktion.

∎

Subproblem b (3.0/3.0P)

Sei CFG-LEERHEIT das Entscheidungsproblem, ob eine gegebene kontextfreie Grammatik GG kein Wort erzeugt, also ob L(G)=L(G)=\emptyset gilt.

Aussage: 3KNF-SAT p\leq_p CFG-LEERHEIT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von 3KNF-SAT an.
(x1¬x2x3)(¬x1x2x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)
Die Aussage giltDie Aussage gilt nicht
**Beweis, dass die Reduktion nicht existieren kann (unter der Annahme \(P\neq NP\)).**

1. **Komplexität von CFG‑LEERHEIT**  
   Das Problem, zu entscheiden, ob die von einer kontextfreien Grammatik \(G\) erzeugte Sprache leer ist, kann in linearer Zeit gelöst werden (z.\;B. durch Berechnung der erreichbaren Nichtterminalsymbole). Damit liegt **CFG‑LEERHEIT in \(P\)**.

2. **Komplexität von 3‑KNF‑SAT**  
   Das Erfüllbarkeitsproblem für 3‑KNF‑Formeln ist **NP‑voll**. Insbesondere ist es **NP‑schwer**; jede Sprache in \(NP\) lässt sich in polynomieller Zeit auf 3‑KNF‑SAT reduzieren.

3. **Folgerung einer hypothetischen Reduktion**  
   Angenommen, es gäbe eine polynomialzeit‑many‑one‑Reduktion  
   \[
   f : \text{3KNF‑SAT} \longrightarrow \text{CFG‑LEERHEIT}.
   \]
   Dann könnte man für jede 3‑KNF‑Formel \(\varphi\) zunächst \(f(\varphi)\) in polynomialer Zeit konstruieren und anschließend das Ergebnis von CFG‑LEERHEIT in polynomialer Zeit entscheiden. Damit gäbe es ein deterministisches Polynomzeit‑Verfahren für 3‑KNF‑SAT, also **\( \text{3KNF‑SAT} \in P\)**.

4. **Widerspruch zur Annahme \(P\neq NP\)**  
   Da 3‑KNF‑SAT NP‑voll ist, würde \(\text{3KNF‑SAT} \in P\) die Inklusion \(NP \subseteq P\) implizieren, also \(P = NP\). Das steht im Widerspruch zur Voraussetzung \(P \neq NP\).

5. **Schluss**  
   Unter der Annahme \(P\neq NP\) **kann keine polynomialzeit‑Reduktion von 3‑KNF‑SAT auf CFG‑LEERHEIT existieren**. Folglich ist die Aussage **falsch**.

∎

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

Eingabe: Eine endliche Menge M={m1,...,mk}M=\{m_1, ..., m_k\} und eine Menge T={T1,...,Tn}T=\{T_1, ..., T_n\}  von Teilmengen von MM.

Ausgabe: Enthält TT eine exakte Überdeckung von MM, d.h. gibt es eine Menge STS \subseteq T, sodass jedes Element von MM in genau einer der Teilmengen in SS vorkommt?

Aussage: EXAKTE-ÜBERDECKUNG p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M{1,2,3,4}M\coloneqq\{1,2,3,4\}
T{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1{1}T_1\coloneqq\{1\},
T2{1,3}T_2\coloneqq\{1,3\},
T3{1,2,3}T_3\coloneqq\{1,2,3\},
T4{2,4}T_4\coloneqq\{2,4\},
T5T_5\coloneqq\emptyset.
Die Aussage giltDie Aussage gilt nicht
**Reduktionsfunktion $f$ (EXAKTE‑ÜBERDECKUNG → SAT)**  

*Eingabe:*  ein Paar \((M,T)\) mit  
\(M=\{m_1,\dots ,m_k\}\) und \(T=\{T_1,\dots ,T_n\}\)  (jede \(T_i\subseteq M\)).  

*Ausgabe:*  eine aussagenlogische Formel \(\Phi = f(M,T)\) in konjunktiver Normalform.

1. **Variablen.**  Für jedes Teilmengenelement \(T_i\) führen wir eine boolesche Variable \(x_i\) ein.  
   \(x_i = 1\) bedeutet, dass \(T_i\) in die gesuchte exakte Überdeckung aufgenommen wird.

2. **„mindestens‑ein‑Set‑für‑jedes‑Element“-Klauseln.**  
   Für jedes Element \(m\in M\) bilden wir die Klausel  
   \[
   C_m^{\;\text{at‑least}} \;=\; \bigvee_{i:\,m\in T_i} x_i .
   \]
   (Falls kein \(T_i\) das Element enthält, ist die Instanz sofort **nicht** lösbar – die Reduktion erzeugt die triviale unbefriedigbare Formel.)

3. **„höchstens‑ein‑Set‑für‑jedes‑Element“-Klauseln.**  
   Für jedes \(m\in M\) und jedes ungeordnete Paar \((i,j)\) mit \(i<j\) und \(m\in T_i\cap T_j\) fügen wir die Klausel  
   \[
   C_{m,i,j}^{\;\text{at‑most}} \;=\; \lnot x_i \;\lor\; \lnot x_j .
   \]
   Diese Klauseln verhindern, dass ein Element von zwei unterschiedlichen gewählten Teilmengen gedeckt wird.

4. **Gesamte Formel.**  
   \[
   \Phi \;=\; \bigwedge_{m\in M}\;C_m^{\;\text{at‑least}}
               \;\;\land\;\;
               \bigwedge_{m\in M}\;\bigwedge_{i<j,\;m\in T_i\cap T_j}\;C_{m,i,j}^{\;\text{at‑most}} .
   \]

Die Konstruktion ist eindeutig, benötigt nur das Durchsuchen aller Elemente von \(M\) und aller Mengen von \(T\) und erzeugt polynomial viele Klauseln (höchstens \(|M|\cdot n^2\)).  Damit ist \(f\) eine polynomialzeit‑many‑one‑Reduktion.

---

### Korrektheit (Skizze)

*→*   Angenommen, es gibt eine exakte Überdeckung \(S\subseteq T\).  
Setze \(x_i=1\) genau für die Mengen \(T_i\in S\) und \(x_i=0\) sonst.  
Für jedes \(m\in M\) ist wegen der Exaktheit genau ein \(T_i\in S\) mit \(m\in T_i\); damit erfüllt \(C_m^{\;\text{at‑least}}\) und alle „höchstens‑ein‑“‑Klauseln (da nie zwei gewählte Mengen dasselbe Element teilen).  Somit ist \(\Phi\) erfüllbar.

*←*   Angenommen, \(\Phi\) ist erfüllbar und sei \(\alpha\) eine erfüllende Belegung.  
Definiere \(S=\{\,T_i\mid \alpha(x_i)=1\,\}\).  
Die „at‑least“‑Klauseln garantieren, dass jedes Element \(m\) in mindestens einer Menge aus \(S\) vorkommt.  
Die „at‑most“‑Klauseln verhindern, dass ein Element in zwei verschiedenen Mengen aus \(S\) vorkommt.  
Also enthält jedes \(m\) genau eine Menge aus \(S\); das heißt, \(S\) ist eine exakte Überdeckung von \(M\).

Damit gilt: \((M,T)\) hat eine exakte Überdeckung  ⇔  \(\Phi\) ist erfüllbar.  Somit ist die Reduktion korrekt.

---

## Anwendung auf die gegebene Instanz

**Instanz von EXAKTE‑ÜBERDECKUNG**

\[
\begin{aligned}
M &= \{1,2,3,4\},\\[2pt]
T_1 &= \{1\},\\
T_2 &= \{1,3\},\\
T_3 &= \{1,2,3\},\\
T_4 &= \{2,4\},\\
T_5 &= \emptyset .
\end{aligned}
\]

Wir führen Variablen \(x_1,\dots ,x_5\) ein.

### Klauseln für jedes Element

*Element 1* (in \(T_1,T_2,T_3\)):  
\[
\begin{aligned}
C_1^{\text{at‑least}} &: \; (x_1 \lor x_2 \lor x_3)\\
C_{1,1,2}^{\text{at‑most}} &: \;lnot x_1 \lor \lnot x_2)\\
C_{1,1,3}^{\text{at‑most}} &: \; (\lnot x_1 \lor \lnot x_3)\\
C_{1,2,3}^{\text{at‑most}} &: \; (\lnot x_2 \lor \lnot x_3)
\end{aligned}
\]

*Element 2* (in \(T_3,T_4\)):  
\[
\begin{aligned}
C_2^{\text{at‑least}} &: \; (x_3 \lor x_4)\\
C_{2,3,4}^{\text{at‑most}} &: \; (\lnot x_3 \lor \lnot x_4)
\end{aligned}
\]

*Element 3* (in \(T_2,T_3\)):  
\[
\begin{aligned}
C_3^{\text{at‑least}} &: \; (x_2 \lor x_3)\\
C_{3,2,3}^{\text{at‑most}} &: \; (\lnot x_2 \lor \lnot x_3)
\end{aligned}
\]

*Element 4* (in \(T_4\) allein):  
\[
C_4^{\text{at‑least}} :\; (x_4)
\]
(keine „at‑most“‑Klauseln, weil nur ein Set das Element enthält).

\(T_5\) ist leer und erzeugt keine Klauseln.

### Gesamte CNF‑Formel \(\Phi\)

\[
\begin}
\Phi =\;& (x_1 \lor x_2 \lor x_3) \;\land\;
          (\lnot x_1 \lor \lnot x_2) \;\land\;
          (\lnot x_1 \lor \lnot x_3) \;\land\;
          (\lnot x_2 \lor \lnot x_3) \\[2pt]
        &\land\; (x_3 \lor x_4) \;\land\;
          (\lnot x_3 \lor \lnot x_4) \\[2pt]
        &\land\; (x_2 \lor x_3) \;\land\;
          (\lnot x_2 \lor \lnot x_3) \\[2pt]
        &\land\; (x_4).
\end{aligned}
\]

**Interpretation:**  
Die Belegung \(x_2 = 1,\; x_4 = 1\) und \(x_1 = x_3 = x_5 = 0\) erfüllt \(\Phi\).  
Sie entspricht genau der Auswahl der Teilmengen \(T_2=\{1,3\}\) und \(T_4=\{2,4\}\), die jedes Element aus \(M\) **einmal** und nur einmal abdecken – also einer exakten Überdeckung.

Damit ist die Reduktion auf die gegebene Instanz vollzogen. ∎

qwen/qwen3-235b-a22b

Exercise 7: Reduktion

Nehmen Sie PNP\P\ne\NP an. Entscheiden Sie unter dieser Annahme, welche der folgenden Aussagen gelten. Die Aussagen sind von der Gestalt „ApBA\le_p B“ für  Entscheidungsprobleme A,BA, B. Wenn die Aussage gilt, dann müssen Sie (1) eine präzise definierte Reduktionsfunktion angeben und (2) die Reduktionsfunktion auf die gegebene Instanz von Problem AA anwenden. Die Korrektheit der Reduktion müssen Sie nur skizzieren. Wenn die Aussage nicht gilt, dann müssen Sie dies beweisen.

Subproblem a (4.0/4.0P)

Sei G=(V,E)G=(V, E) ein ungerichteter Graph. Ein Hamilton-Pfad von GG ist eine Permutation v1,,vnv_1,\dotsc,v_n der Knoten von VV mit {vi,vi+1}E\{v_i, v_{i+1}\} \in E für jedes i{1,...,n1}i \in \{1, ..., n-1\}. Ein Hamilton-Kreis von GG ist ein Hamilton-Pfad von GG, der zusätzlich {vn,v1}E\{v_n, v_1\} \in E erfüllt.

Sei HAMILTON-PFAD das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Pfad hat. Sei HAMILTON-KREIS das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Kreis hat.

Aussage: HAMILTON-PFAD p\le_p HAMILTON-KREIS

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von HAMILTON-PFAD an.
Knoten: A, B, C, D, E
Kanten:
    A -- B
    A -- C
    B -- C
    C -- D
    C -- E
    D -- E
Die Aussage giltDie Aussage gilt nicht
<ul>
<li><strong>Reduktionsfunktion:</strong></li>
Dabei wird für einen gegebenen Graphen G=(V,E) G = (V, E)  ein neuer Graph G=(V{w},E{{w,v}vV}) G' = (V \cup \{w\}, E \cup \{\{w, v\} \mid v \in V\})  konstruiert. Ein Hamilton-Kreis in G G'  korrespondiert mit einem Hamilton-Pfad in G G .
<li><strong>Anwendung auf den Graphen:</strong></li>
Der Originalgraph G G  mit Knoten A,B,C,D,E A, B, C, D, E  wird um den Knoten w w  erweitert, der mit allen existierenden Knoten verbunden ist. Die Kanten von w w  zu den Knoten sind: wA,wB,wC,wD,wE w\text{--}A, w\text{--}B, w\text{--}C, w\text{--}D, w\text{--}E .

<li><strong>Korrektheitsargument (Skizze):</strong></li>
    <ul>
        <li> \Rightarrow : Ein Hamilton-Pfad ABCDE A\text{--}B\text{--}C\text{--}D\text{--}E  in G G  wird zu einem Hamilton-Kreis ABCDEwA A\text{--}B\text{--}C\text{--}D\text{--}E\text{--}w\text{--}A  in G G'  erweitert.</li>
        <li> \Leftarrow : Ein Hamilton-Kreis in G G'  durchläuft alle Knoten, einschließlich w w . w w  hat nur Kanten zu G G , daher muss ein Pfad durch alle Knoten von G G  existieren, sobald w w  entfernt wird.</li>
    </ul>
</ul>

Subproblem b (3.0/3.0P)

Sei CFG-LEERHEIT das Entscheidungsproblem, ob eine gegebene kontextfreie Grammatik GG kein Wort erzeugt, also ob L(G)=L(G)=\emptyset gilt.

Aussage: 3KNF-SAT p\leq_p CFG-LEERHEIT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von 3KNF-SAT an.
(x1¬x2x3)(¬x1x2x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)
Die Aussage giltDie Aussage gilt nicht
Beweis der Unmöglichkeit:

Schlüsselargument: CFG-LEERHEIT liegt in P, da die Leerheit einer kontextfreien Grammatik in linearer Zeit entschieden werden kann (z. B. durch Erreichbarkeitsanalyse der Startvariablen).

Angenommen, die Aussage gelte. Dann gäbe es eine Reduktion von 3KNF-SAT auf CFG-LEERHEIT. Dies würde bedeuten, dass 3KNF-SAT ∈ P. 

Widerspruch zu P ≠ NP: Unter der Annahme P ≠ NP ist dies unmöglich, da 3KNF-SAT ein NP-vollständiges Problem ist. Ein polynomieller Algorithmus für 3KNF-SAT würde somit die Annahme P ≠ NP verletzen. 

Daher gilt die Aussage nicht.

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

Eingabe: Eine endliche Menge M={m1,...,mk}M=\{m_1, ..., m_k\} und eine Menge T={T1,...,Tn}T=\{T_1, ..., T_n\}  von Teilmengen von MM.

Ausgabe: Enthält TT eine exakte Überdeckung von MM, d.h. gibt es eine Menge STS \subseteq T, sodass jedes Element von MM in genau einer der Teilmengen in SS vorkommt?

Aussage: EXAKTE-ÜBERDECKUNG p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M{1,2,3,4}M\coloneqq\{1,2,3,4\}
T{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1{1}T_1\coloneqq\{1\},
T2{1,3}T_2\coloneqq\{1,3\},
T3{1,2,3}T_3\coloneqq\{1,2,3\},
T4{2,4}T_4\coloneqq\{2,4\},
T5T_5\coloneqq\emptyset.
Die Aussage giltDie Aussage gilt nicht
<ul>
<li><strong>Reduktionsfunktion:</strong></li>
Für jede Teilmengeproblem-Instanz $ (M, T) $ wird ein SAT-Problem wie folgt konstruiert:
<ul>
<li>Eine Variable $ x_j $ wird für jede Teilmenge $ T_j \in T $ eingeführt.</li>
<li>Für jedes Element $ m \in M $ werden zwei Arten von Klauseln hinzugefügt:
<ol>
<li><em>Mindestens eine:</em> $ \bigvee_{T_j \ni m} x_j $ (Deckel der alle $ m $ enthalten).</li>
<li><em>Höchstens eine:</em> $ \neg x_j \vee \neg x_{j'} $ für alle Paare $ T_j, T_{j'} \ni m $ mit $ j \ne j' $.</li>
</ol>
</ul>
Die Reduktion führt in polynomialer Zeit aus einer exakten Überdeckung eine erfüllbare Belegung und umgekehrt.

<li><strong>Anwendung auf die Instanz:</strong></li>
Variablen: $ x_1, x_2, x_3, x_4, x_5 $ für $ T_1, T_2, T_3, T_4, T_5 $.

**Element $ 1 $:** Klauseln
\begin{align*}
\text{Mindestens eine:} & x_1 \vee x_2 \vee x_3 \\
\text{Höchstens eine:} & \text{(nur Paare, die 1 enthalten)} \\
& \neg x_1 \vee \neg x_2,\, \neg x_1 \vee \neg x_3,\, \neg x_2 \vee \neg x_3
\end{align*}

**Element $ 2 $:** Klauseln
\begin{align*}
\text{Mindestens eine:} & x_3 \vee x_4 \\
\text{Höchstens eine:} & \neg x_3 \vee \neg x_4
\end{align*}

**Element $ 3 $:** Klauseln
\begin{align*}
\text{Mindestens eine:} & x_2 \vee x_3 \\
\text{Höchstens eine:} & \neg x_2 \vee \neg x_3
\end{align*}

**Element $ 4 $:** Klauseln
\begin{align*}
\text{Mindestens eine:} & x_4 \\
\text{(Trivial: Höchstens eine, da nur $ T_4 $ enthält 4)}
\end{align*}

<li><strong>Korrektheitsargument (Skizze):</strong></li>
<ul>
<li>$ \Rightarrow $: Existiert eine exakte Überdeckung $ S \subseteq T $, dann ist $ x_j = \top $ für $ T_j \in S $. Für jedes Element $ m $ ist genau eine Variable in allen Klauseln wahr, und für Paare gilt $ \neg x_j \vee \neg x_{j'} $, da keine zweifache Abdeckung.</li>
<li>$ \Leftarrow $: Eine erfüllende Belegung definiert $ S \subseteq T $ durch $ T_j \in S \iff x_j = \top $. Klauseln fuer Mindestens-eine und Höchstens-eine garantieren, dass $ S $ eine exakte Überdeckung ist.</li>
</ul>
</ul>

qwen/qwen3-235b-a22b-thinking-2507

Exercise 7: Reduktion

Nehmen Sie PNP\P\ne\NP an. Entscheiden Sie unter dieser Annahme, welche der folgenden Aussagen gelten. Die Aussagen sind von der Gestalt „ApBA\le_p B“ für  Entscheidungsprobleme A,BA, B. Wenn die Aussage gilt, dann müssen Sie (1) eine präzise definierte Reduktionsfunktion angeben und (2) die Reduktionsfunktion auf die gegebene Instanz von Problem AA anwenden. Die Korrektheit der Reduktion müssen Sie nur skizzieren. Wenn die Aussage nicht gilt, dann müssen Sie dies beweisen.

Subproblem a (4.0/4.0P)

Sei G=(V,E)G=(V, E) ein ungerichteter Graph. Ein Hamilton-Pfad von GG ist eine Permutation v1,,vnv_1,\dotsc,v_n der Knoten von VV mit {vi,vi+1}E\{v_i, v_{i+1}\} \in E für jedes i{1,...,n1}i \in \{1, ..., n-1\}. Ein Hamilton-Kreis von GG ist ein Hamilton-Pfad von GG, der zusätzlich {vn,v1}E\{v_n, v_1\} \in E erfüllt.

Sei HAMILTON-PFAD das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Pfad hat. Sei HAMILTON-KREIS das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Kreis hat.

Aussage: HAMILTON-PFAD p\le_p HAMILTON-KREIS

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von HAMILTON-PFAD an.
Knoten: A, B, C, D, E
Kanten:
    A -- B
    A -- C
    B -- C
    C -- D
    C -- E
    D -- E
Die Aussage giltDie Aussage gilt nicht
Reduktionsfunktion: Sei G=(V,E)G = (V, E) eine Instanz von HAMILTON-PFAD. Definiere die Reduktionsfunktion ff, die GG auf einen neuen Graphen G=(V,E)G' = (V', E') abbildet, wobei:
- V=V{u}V' = V \cup \{u\} (uu ist ein neu hinzugefügter Knoten),
- E=E{{u,v}vV}E' = E \cup \{\{u, v\} \mid v \in V\}.

Anwendung auf die gegebene Instanz:  
Gegebener Graph GG mit Knoten {A,B,C,D,E}\{A, B, C, D, E\} und Kanten {AB,AC,BC,CD,CE,DE}\{A\text{--}B, A\text{--}C, B\text{--}C, C\text{--}D, C\text{--}E, D\text{--}E\}.  
Der transformierte Graph G=f(G)G' = f(G) hat:
- Knoten: A,B,C,D,E,uA, B, C, D, E, u,
- Kanten: Alle Kanten von GG und zusätzliche Kanten {uA,uB,uC,uD,uE}\{u\text{--}A, u\text{--}B, u\text{--}C, u\text{--}D, u\text{--}E\}.

Korrektheit (Skizze):  
- Hinrichtung: Besitzt GG einen Hamilton-Pfad v1vnv_1\text{--}\dots\text{--}v_n, so bildet uv1vnuu\text{--}v_1\text{--}\dots\text{--}v_n\text{--}u einen Hamilton-Kreis in GG', da uu mit allen Knoten verbunden ist.
- Rückrichtung: Enthält GG' einen Hamilton-Kreis, so muss dieser uu enthalten. Durch Entfernen von uu und Verbinden seiner Nachbarn entsteht ein Hamilton-Pfad in GG.
- Die Reduktion ist offensichtlich in polynomieller Zeit berechenbar, da sie lediglich einen Knoten und nn Kanten hinzufügt.

Subproblem b (3.0/3.0P)

Sei CFG-LEERHEIT das Entscheidungsproblem, ob eine gegebene kontextfreie Grammatik GG kein Wort erzeugt, also ob L(G)=L(G)=\emptyset gilt.

Aussage: 3KNF-SAT p\leq_p CFG-LEERHEIT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von 3KNF-SAT an.
(x1¬x2x3)(¬x1x2x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)
Die Aussage giltDie Aussage gilt nicht
Beweis, dass die Aussage nicht gilt:  
Unter der Annahme PNP\P \ne \NP gilt, dass CFG-LEERHEIT in P\P liegt. Das Problem CFG-LEERHEIT ist effizient lösbar: Ein Algorithmus mit Laufzeit O(G)\mathcal{O}(|G|) prüft, ob das Startsymbol der Grammatik GG terminale Zeichen ableiten kann (durch Markieren von Symbolen, die zu Terminalen reduzieren). Da 3KNF-SAT3\text{KNF-SAT} NP\NP-vollständig ist, würde eine polynomielle Reduktion 3KNF-SATpCFG-LEERHEIT3\text{KNF-SAT} \leq_p \text{CFG-LEERHEIT} implizieren, dass 3KNF-SAT3\text{KNF-SAT} in P\P liegt. Dies widerspricht PNP\P \ne \NP. Somit kann die Reduktion nicht existieren.

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

Eingabe: Eine endliche Menge M={m1,...,mk}M=\{m_1, ..., m_k\} und eine Menge T={T1,...,Tn}T=\{T_1, ..., T_n\}  von Teilmengen von MM.

Ausgabe: Enthält TT eine exakte Überdeckung von MM, d.h. gibt es eine Menge STS \subseteq T, sodass jedes Element von MM in genau einer der Teilmengen in SS vorkommt?

Aussage: EXAKTE-ÜBERDECKUNG p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M{1,2,3,4}M\coloneqq\{1,2,3,4\}
T{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1{1}T_1\coloneqq\{1\},
T2{1,3}T_2\coloneqq\{1,3\},
T3{1,2,3}T_3\coloneqq\{1,2,3\},
T4{2,4}T_4\coloneqq\{2,4\},
T5T_5\coloneqq\emptyset.
Die Aussage giltDie Aussage gilt nicht
**Reduktionsfunktion:**  
Sei $(M, T)$ eine Instanz von EXAKTE-ÜBERDECKUNG mit $M = \{m_1, \dotsc, m_k\}$ und $T = \{T_1, \dotsc, T_n\}$. Definiere eine SAT-Instanz mit Variablen $x_1, \dotsc, x_n$, wobei $x_i$ angibt, ob $T_i \in S$ gilt. Für jedes $m_j \in M$ sei $I_j = \{i \mid m_j \in T_i\}$. Die SAT-Formel besteht aus:  
1. **„Mindestens ein“-Klauseln**: $\bigvee_{i \in I_j} x_i$ für jedes $m_j \in M$,  
2. **„Höchstens ein“-Klauseln**: $(\neg x_i \vee \neg x_{i'})$ für alle $i < i' \in I_j$ und jedes $m_j \in M$.  

**Anwendung auf die gegebene Instanz:**  
$M = \{1,2,3,4\}$, $T = \{T_1, T_2, T_3, T_4, T_5\}$ mit $T_1 = \{1\}$, $T_2 = \{1,3\}$, $T_3 = \{1,2,3\}$, $T_4 = \{2,4\}$, $T_5 = \emptyset$.  
- Variablen: $x_1, x_2, x_3, x_4, x_5$.  
- **Klauseln**:  
  - Für $m=1$ ($I_1 = \{1,2,3\}$):  
    $(x_1 \vee x_2 \vee x_3)$,  
    $(\neg x_1 \vee \neg x_2)$, $(\neg x_1 \vee \neg x_3)$, $(\neg x_2 \vee \neg x_3)$.  
  - Für $m=2$ ($I_2 = \{3,4\}$):  
    $(x_3 \vee x_4)$, $(\neg x_3 \vee \neg x_4)$.  
  - Für $m=3$ ($I_3 = \{2,3\}$):  
    $(x_2 \vee x_3)$, $(\neg x_2 \vee \neg x_3)$.  
  - Für $m=4$ ($I_4 = \{4\}$):  
    $(x_4)$.  
  - $T_5$ enthält kein Element, also keine Klauseln für $x_5$.  
- Resultierende CNF:  
\[
(x_1 \vee x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2) \wedge (\neg x_1 \vee \neg x_3) \wedge (\neg x_2 \vee \neg x_3) \wedge \\
(x_3 \vee x_4) \wedge (\neg x_3 \vee \neg x_4) \wedge (x_2 \vee x_3) \wedge (\neg x_2 \vee \neg x_3) \wedge (x_4).
\]

**Korrektheit (Skizze):**  
- **Hinrichtung:** Eine exakte Überdeckung $S \subseteq T$ definiert eine erfüllende Belegung mit $x_i = 1 \iff T_i \in S$. Die Klauseln garantieren, dass jedes Element *genau* einmal abgedeckt wird.  
- **Rückrichtung:** Eine erfüllende Belegung induziert ein $S = \{T_i \mid x_i = 1\}$, das eine exakte Überdeckung ist, da die Klauseln die Disjunktheit und Vollständigkeit der Abdeckung erzwingen.  
- Die Reduktion ist polynomiell, da die Anzahl der Klauseln $\mathcal{O}(k \cdot n^2)$ ist ($k = |M|$, $n = |T|$).

x-ai/grok-4

Exercise 7: Reduktion

Nehmen Sie PNP\P\ne\NP an. Entscheiden Sie unter dieser Annahme, welche der folgenden Aussagen gelten. Die Aussagen sind von der Gestalt „ApBA\le_p B“ für  Entscheidungsprobleme A,BA, B. Wenn die Aussage gilt, dann müssen Sie (1) eine präzise definierte Reduktionsfunktion angeben und (2) die Reduktionsfunktion auf die gegebene Instanz von Problem AA anwenden. Die Korrektheit der Reduktion müssen Sie nur skizzieren. Wenn die Aussage nicht gilt, dann müssen Sie dies beweisen.

Subproblem a (4.0/4.0P)

Sei G=(V,E)G=(V, E) ein ungerichteter Graph. Ein Hamilton-Pfad von GG ist eine Permutation v1,,vnv_1,\dotsc,v_n der Knoten von VV mit {vi,vi+1}E\{v_i, v_{i+1}\} \in E für jedes i{1,...,n1}i \in \{1, ..., n-1\}. Ein Hamilton-Kreis von GG ist ein Hamilton-Pfad von GG, der zusätzlich {vn,v1}E\{v_n, v_1\} \in E erfüllt.

Sei HAMILTON-PFAD das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Pfad hat. Sei HAMILTON-KREIS das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Kreis hat.

Aussage: HAMILTON-PFAD p\le_p HAMILTON-KREIS

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von HAMILTON-PFAD an.
Knoten: A, B, C, D, E
Kanten:
    A -- B
    A -- C
    B -- C
    C -- D
    C -- E
    D -- E
Die Aussage giltDie Aussage gilt nicht
Reduktionsfunktion:  
Gegeben sei ein ungerichteter Graph G=(V,E)G = (V, E). Konstruiere G=(V,E)G' = (V', E') wie folgt:  
- V=V{k}V' = V \cup \{k\}, wobei kk ein neuer Knoten ist (nicht in VV).  
- E=E{{k,v}vV}E' = E \cup \bigl\{ \{k, v\} \mid v \in V \bigr\}.  

Die Reduktionsfunktion ff bildet die Instanz GG auf GG' ab. Diese Konstruktion ist in polynomieller Zeit möglich (Addition eines Knotens und V|V| Kanten).  

Skizze der Korrektheit:  
GG hat einen Hamilton-Pfad \Leftrightarrow GG' hat einen Hamilton-Kreis.  

- (\Rightarrow) Sei p1p2pnp_1 - p_2 - \dots - p_n ein Hamilton-Pfad in GG (V={p1,,pn}V = \{p_1, \dots, p_n\}). Dann ist pnkp1p2pnp_n - k - p_1 - p_2 - \dots - p_n ein Hamilton-Kreis in GG' (da {pn,k}\{p_n, k\} und {k,p1}\{k, p_1\} in EE').  
- (\Leftarrow) Sei ein Hamilton-Kreis in GG' gegeben. Da kk Grad V|V| hat, tritt kk im Kreis zwischen zwei Knoten a,bVa, b \in V auf: akba\dots - a - k - b - \dots - a. Der Teil von bb nach aa ist ein Pfad in GG, der alle Knoten aus VV genau einmal besucht (also ein Hamilton-Pfad in GG).  

Anwendung auf die gegebene Instanz:  
Gegebener Graph G=(V,E)G = (V, E) mit  
- V={A,B,C,D,E}V = \{A, B, C, D, E\},  
- E={{A,B},{A,C},{B,C},{C,D},{C,E},{D,E}}E = \bigl\{ \{A, B\}, \{A, C\}, \{B, C\}, \{C, D\}, \{C, E\}, \{D, E\} \bigr\}.  

Der reduzierte Graph G=(V,E)G' = (V', E') ist:  
- V={A,B,C,D,E,K}V' = \{A, B, C, D, E, K\} (wähle KK als neuen Knoten),  
- E=E{{K,A},{K,B},{K,C},{K,D},{K,E}}E' = E \cup \bigl\{ \{K, A\}, \{K, B\}, \{K, C\}, \{K, D\}, \{K, E\} \bigr\}.

Subproblem b (3.0/3.0P)

Sei CFG-LEERHEIT das Entscheidungsproblem, ob eine gegebene kontextfreie Grammatik GG kein Wort erzeugt, also ob L(G)=L(G)=\emptyset gilt.

Aussage: 3KNF-SAT p\leq_p CFG-LEERHEIT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von 3KNF-SAT an.
(x1¬x2x3)(¬x1x2x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)
Die Aussage giltDie Aussage gilt nicht
Die Aussage gilt nicht unter der Annahme PNP\P \ne \NP.  

Beweis: Angenommen, es gäbe eine polynomielle Reduktion von 3KNF-SAT nach CFG-LEERHEIT. Das bedeutet, es existiert eine in polynomieller Zeit berechenbare Funktion ff, die eine 3CNF-Formel ϕ\phi auf eine kontextfreie Grammatik G=f(ϕ)G = f(\phi) abbildet, sodass ϕ\phi erfüllbar ist genau dann, wenn L(G)=L(G) = \emptyset.  

Es ist bekannt, dass CFG-LEERHEIT P\in \P (man kann in polynomieller Zeit alle produktiven Nichtterminale bestimmen und prüfen, ob das Startsymbol produktiv ist).  

Falls eine solche Reduktion existiert, könnte man 3KNF-SAT wie folgt in polynomieller Zeit entscheiden: Berechne G=f(ϕ)G = f(\phi) (poly-Zeit) und entscheide dann, ob L(G)=L(G) = \emptyset (poly-Zeit). Dies würde bedeuten, dass 3KNF-SAT P\in \P. Da 3KNF-SAT NP\NP-vollständig ist, folgte P=NP\P = \NP, was der Annahme widerspricht.  

Somit kann keine solche polynomielle Reduktion existieren.

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

Eingabe: Eine endliche Menge M={m1,...,mk}M=\{m_1, ..., m_k\} und eine Menge T={T1,...,Tn}T=\{T_1, ..., T_n\}  von Teilmengen von MM.

Ausgabe: Enthält TT eine exakte Überdeckung von MM, d.h. gibt es eine Menge STS \subseteq T, sodass jedes Element von MM in genau einer der Teilmengen in SS vorkommt?

Aussage: EXAKTE-ÜBERDECKUNG p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M{1,2,3,4}M\coloneqq\{1,2,3,4\}
T{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1{1}T_1\coloneqq\{1\},
T2{1,3}T_2\coloneqq\{1,3\},
T3{1,2,3}T_3\coloneqq\{1,2,3\},
T4{2,4}T_4\coloneqq\{2,4\},
T5T_5\coloneqq\emptyset.
Die Aussage giltDie Aussage gilt nicht
Reduktionsfunktion:  
Gegeben eine Instanz (M,T)(M, T) von EXAKTE-ÜBERDECKUNG mit M={m1,,mk}M = \{m_1, \dots, m_k\} und T={T1,,Tn}T = \{T_1, \dots, T_n\}. Konstruiere eine CNF-Formel ϕ\phi wie folgt:  

- Variablen: x1,,xnx_1, \dots, x_n, wobei xix_i wahr bedeutet, dass TiT_i in der exakten Überdeckung gewählt wird.  

Für jedes Element mjMm_j \in M (für j=1,,kj = 1, \dots, k):  
Lasse Ij={imjTi}I_j = \{ i \mid m_j \in T_i \} die Indizes der Teilmengen sein, die mjm_j enthalten.  

- At least one: Füge die Klausel iIjxi\bigvee_{i \in I_j} x_i hinzu (falls Ij=I_j = \emptyset, ist dies die leere Disjunktion, was falsch ist; aber in gültigen Instanzen sollte jedes Element in mindestens einer Teilmenge vorkommen, andernfalls ist es trivial nicht überdeckbar).  
- At most one: Für jedes Paar i<li < l mit i,lIji, l \in I_j füge die Klausel (¬xi¬xl)(\neg x_i \lor \neg x_l) hinzu.  

Die Formel ϕ\phi ist die Konjunktion aller dieser Klauseln. Die Konstruktion ist in polynomieller Zeit möglich ( polynomiell viele Klauseln, da O(n2)O(n^2) pro Element, insgesamt O(kn2)O(k n^2)).  

Skizze der Korrektheit:  
ϕ\phi ist erfüllbar \Leftrightarrow es existiert eine exakte Überdeckung STS \subseteq T.  

- (\Rightarrow) Sei β\beta eine erfüllende Belegung von ϕ\phi. Definiere S={Tiβ(xi)=1}S = \{ T_i \mid \beta(x_i) = 1 \}. Für jedes mjm_j stellt "at least one" sicher, dass mindestens eine TiT_i mit mjTim_j \in T_i gewählt ist, und "at most one" stellt sicher, dass höchstens eine solche gewählt ist. Also ist SS eine exakte Überdeckung.  
- (\Leftarrow) Sei SS eine exakte Überdeckung. Setze β(xi)=1\beta(x_i) = 1 gdw. TiST_i \in S. Da jedes mjm_j in genau einer TiST_i \in S vorkommt, ist für jedes jj genau eine xix_i mit iIji \in I_j wahr, was beide Bedingungen ("at least one" und "at most one") erfüllt. (Falls leere Mengen in TT sind, können sie optional gewählt werden, ohne die Bedingungen zu verletzen, und entsprechen mehreren möglichen SS, aber die Existenz bleibt erhalten.)  

Anwendung auf die gegebene Instanz:  
M={1,2,3,4}M = \{1,2,3,4\}, T={T1={1},T2={1,3},T3={1,2,3},T4={2,4},T5=}T = \{T_1 = \{1\}, T_2 = \{1,3\}, T_3 = \{1,2,3\}, T_4 = \{2,4\}, T_5 = \emptyset\}.  

Variablen: x1,x2,x3,x4,x5x_1, x_2, x_3, x_4, x_5.  

Klauseln:  

- Für 1 (I1={1,2,3}I_1 = \{1,2,3\}):  
  At least one: (x1x2x3)(x_1 \lor x_2 \lor x_3)  
  At most one: (¬x1¬x2)(\neg x_1 \lor \neg x_2), (¬x1¬x3)(\neg x_1 \lor \neg x_3), (¬x2¬x3)(\neg x_2 \lor \neg x_3)  

- Für 2 (I2={3,4}I_2 = \{3,4\}):  
  At least one: (x3x4)(x_3 \lor x_4)  
  At most one: (¬x3¬x4)(\neg x_3 \lor \neg x_4)  

- Für 3 (I3={2,3}I_3 = \{2,3\}):  
  At least one: (x2x3)(x_2 \lor x_3)  
  At most one: (¬x2¬x3)(\neg x_2 \lor \neg x_3)  

- Für 4 (I4={4}I_4 = \{4\}):  
  At least one: (x4)(x_4)  
  At most one: (keine Paare)  

(T_5 betrifft keine Elemente, also keine zusätzlichen Klauseln für x5x_5.)  

Die CNF-Formel ϕ\phi ist die Konjunktion all dieser Klauseln.