anthropic/claude-opus-4.1

Exercise 7: Reduktion

Zeigen Sie für jedes der folgenden Probleme AA entweder, dass es in P\mathsf{P} liegt, oder, dass es NP\mathsf{NP}-hart ist.
Geben Sie hierfür jeweils eine geeignete polynomielle Reduktion an und begründen Sie deren Korrektheit.

Reduktionsfunktionen müssen präzise definiert sein und Sie müssen klar angeben, welche Probleme Sie reduzieren. Die Korrektheit der Reduktion müssen Sie aber nur skizzieren und nicht formal beweisen.

Achtung: Auch um zu zeigen, dass das Problem in P\mathsf{P} liegt, ist eine Reduktion anzugeben!

Hinweis: Um zu zeigen, dass ein Problem AA in P\mathsf{P} liegt, geben Sie eine Reduktion ApBA\le_p B für ein BPB\in\mathsf{P} an, reduzieren Sie also AA auf ein Problem BB, von dem wir wissen, dass es in P\mathsf{P} liegt, z.B. 2COL\mathsf{2COL} oder 2KNF-SAT\mathsf{2KNF\text{-}SAT}.

Um zu zeigen, dass ein Problem AA NP\mathsf{NP}-hart ist, geben Sie eine Reduktion BpAB\le_p A an, wobei BB ein bekanntes NP-hartes Problem ist, etwa 3COL\mathsf{3COL}, SAT\mathsf{SAT}, oder CLIQUE\mathsf{CLIQUE}.

Subproblem a (6.0/6.0P)

Gegeben: Drei KNF-Formeln F1,F2,F3F_1, F_2, F_3 mit Variablen aus VV.

Problem AA: Gibt es eine Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\}, die genau zwei der drei Formeln erfüllt?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: SATpA\mathsf{SAT} \le_p A
Begründung:
Gegeben eine CNF-Formel FF mit Variablen aus VV, konstruiere ich drei CNF-Formeln wie folgt:
- F1=FF_1 = F
- F2=(z)F_2 = (z) wobei zz eine neue Variable ist (nicht in VV)
- F3=(¬z)F_3 = (\neg z)

Diese Reduktion ist polynomiell, da wir nur zwei triviale einelementige Klauseln hinzufügen.

Korrektheit:
- Falls FF erfüllbar ist: Sei σ\sigma eine erfüllende Belegung für FF. Erweitere σ\sigma um z=1z=1. Dann erfüllt diese Belegung F1F_1 (da FF erfüllt ist) und F2F_2 (da z=1z=1), aber nicht F3F_3 (da ¬z=0\neg z = 0). Also werden genau 2 Formeln erfüllt.

- Falls FF nicht erfüllbar ist: Für jede Belegung ist F1F_1 falsch. Da F2F_2 und F3F_3 sich gegenseitig ausschließen (eine fordert z=1z=1, die andere z=0z=0), kann höchstens eine von beiden erfüllt werden. Also wird insgesamt höchstens 1 Formel erfüllt, niemals genau 2.

Daher gilt: FF ist erfüllbar \Leftrightarrow es existiert eine Belegung, die genau zwei der drei Formeln F1,F2,F3F_1, F_2, F_3 erfüllt.

Subproblem b (8.0/8.0P)

Gegeben: Eine 2KNF-Formel FF mit Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\}, eine Menge {1,...,l}\{1, ..., l\} von Farben (mit l>0l>0) und eine Funktion g:V{1,...,l}g: V \to \{1 ,...,l\}, die jeder Variable eine Farbe zuordnet.

Problem AA: Gibt es eine erfüllende Belegung σ\sigma, sodass alle Variablen, die von σ\sigma zu Wahr gesetzt werden, unterschiedliche Farben haben? Formal: gibt es eine erfüllende Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\} mit g(xi)g(xj)g(x_i) \neq g(x_j) für alle i<jni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: Ap2SATA \le_p \mathsf{2SAT}
Begründung:
Gegeben eine Instanz (F,g)(F, g) von Problem AA, konstruiere ich eine 2KNF-Formel FF' wie folgt:

1. Beginne mit allen Klauseln aus FF
2. Für jedes Paar von Variablen xi,xjx_i, x_j mit i<ji < j und g(xi)=g(xj)g(x_i) = g(x_j) (gleiche Farbe), füge die Klausel (¬xi¬xj)(\neg x_i \vee \neg x_j) zu FF' hinzu

Polynomialität: Die Konstruktion ist polynomiell, da:
- Wir höchstens (n2)=O(n2)\binom{n}{2} = O(n^2) neue Klauseln hinzufügen
- Jede neue Klausel hat genau 2 Literale
- FF' bleibt eine 2KNF-Formel

Korrektheit:
- Falls (F,g)(F, g) eine Lösung hat: Sei σ\sigma eine erfüllende Belegung für FF, bei der alle wahren Variablen unterschiedliche Farben haben. Dann erfüllt σ\sigma auch FF', da:
  - Alle ursprünglichen Klauseln aus FF sind erfüllt
  - Für jede hinzugefügte Klausel (¬xi¬xj)(\neg x_i \vee \neg x_j) mit g(xi)=g(xj)g(x_i) = g(x_j) gilt: höchstens eine der Variablen ist wahr (da sie gleiche Farbe haben), also ist die Klausel erfüllt

- Falls FF' erfüllbar ist: Jede erfüllende Belegung σ\sigma für FF' erfüllt auch FF (da FFF \subseteq F') und respektiert die Farbenbedingung, da die Klauseln (¬xi¬xj)(\neg x_i \vee \neg x_j) verhindern, dass zwei Variablen gleicher Farbe beide wahr sind

Da 2SAT in P liegt, liegt auch Problem AA in P.

anthropic/claude-sonnet-4

Exercise 7: Reduktion

Zeigen Sie für jedes der folgenden Probleme AA entweder, dass es in P\mathsf{P} liegt, oder, dass es NP\mathsf{NP}-hart ist.
Geben Sie hierfür jeweils eine geeignete polynomielle Reduktion an und begründen Sie deren Korrektheit.

Reduktionsfunktionen müssen präzise definiert sein und Sie müssen klar angeben, welche Probleme Sie reduzieren. Die Korrektheit der Reduktion müssen Sie aber nur skizzieren und nicht formal beweisen.

Achtung: Auch um zu zeigen, dass das Problem in P\mathsf{P} liegt, ist eine Reduktion anzugeben!

Hinweis: Um zu zeigen, dass ein Problem AA in P\mathsf{P} liegt, geben Sie eine Reduktion ApBA\le_p B für ein BPB\in\mathsf{P} an, reduzieren Sie also AA auf ein Problem BB, von dem wir wissen, dass es in P\mathsf{P} liegt, z.B. 2COL\mathsf{2COL} oder 2KNF-SAT\mathsf{2KNF\text{-}SAT}.

Um zu zeigen, dass ein Problem AA NP\mathsf{NP}-hart ist, geben Sie eine Reduktion BpAB\le_p A an, wobei BB ein bekanntes NP-hartes Problem ist, etwa 3COL\mathsf{3COL}, SAT\mathsf{SAT}, oder CLIQUE\mathsf{CLIQUE}.

Subproblem a (6.0/6.0P)

Gegeben: Drei KNF-Formeln F1,F2,F3F_1, F_2, F_3 mit Variablen aus VV.

Problem AA: Gibt es eine Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\}, die genau zwei der drei Formeln erfüllt?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: SATpA\mathsf{SAT} \le_p A

Begründung:
Gegeben eine CNF-Formel FF über Variablen VV als Eingabe für SAT, konstruiere ich drei Formeln:
- F1=FF_1 = F (die ursprüngliche Formel)
- F2=F_2 = \top (die leere CNF-Formel ohne Klauseln, immer erfüllt)  
- F3=F_3 = \bot (CNF-Formel {}\{\emptyset\} mit der leeren Klausel, nie erfüllt)

Korrektheit:
()(\Rightarrow) Falls FF erfüllbar ist, sei σ\sigma eine erfüllende Belegung für FF. Dann gilt σ(F1)=σ(F)=1\sigma(F_1) = \sigma(F) = 1, σ(F2)=1\sigma(F_2) = 1, σ(F3)=0\sigma(F_3) = 0. Also sind genau zwei Formeln erfüllt.

()(\Leftarrow) Falls eine Belegung σ\sigma genau zwei der drei Formeln erfüllt, dann muss (da F2F_2 immer wahr und F3F_3 immer falsch ist) gelten: σ(F1)=1\sigma(F_1) = 1, σ(F2)=1\sigma(F_2) = 1, σ(F3)=0\sigma(F_3) = 0. Somit erfüllt σ\sigma die Formel F1=FF_1 = F.

Da SAT NP-vollständig ist, folgt dass AA NP-hart ist.

Subproblem b (8.0/8.0P)

Gegeben: Eine 2KNF-Formel FF mit Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\}, eine Menge {1,...,l}\{1, ..., l\} von Farben (mit l>0l>0) und eine Funktion g:V{1,...,l}g: V \to \{1 ,...,l\}, die jeder Variable eine Farbe zuordnet.

Problem AA: Gibt es eine erfüllende Belegung σ\sigma, sodass alle Variablen, die von σ\sigma zu Wahr gesetzt werden, unterschiedliche Farben haben? Formal: gibt es eine erfüllende Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\} mit g(xi)g(xj)g(x_i) \neq g(x_j) für alle i<jni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: Ap2CNF-SATA \le_p \mathsf{2CNF\text{-}SAT}

Begründung:
Gegeben eine 2CNF-Formel FF über Variablen VV und Farbfunktion g:V{1,...,l}g: V \to \{1,...,l\}, konstruiere ich eine neue 2CNF-Formel FF' wie folgt:

1. Füge alle ursprünglichen Klauseln von FF zu FF' hinzu
2. Für jede Farbe c{1,...,l}c \in \{1,...,l\} und jedes Paar verschiedener Variablen xi,xjx_i, x_j mit g(xi)=g(xj)=cg(x_i) = g(x_j) = c, füge die Klausel (¬xi¬xj)(\neg x_i \vee \neg x_j) zu FF' hinzu

Korrektheit:
()(\Rightarrow) Falls σ\sigma eine erfüllende Belegung für FF ist, bei der alle auf wahr gesetzten Variablen verschiedene Farben haben:
- σ\sigma erfüllt alle ursprünglichen Klauseln von FF
- Für jedes Paar xi,xjx_i, x_j gleicher Farbe gilt: höchstens eine Variable ist wahr, also σ(¬xi¬xj)=1\sigma(\neg x_i \vee \neg x_j) = 1
- Somit erfüllt σ\sigma auch FF'

()(\Leftarrow) Falls σ\sigma die Formel FF' erfüllt:
- σ\sigma erfüllt FF (da alle ursprünglichen Klauseln enthalten sind)
- Für jedes Paar xi,xjx_i, x_j gleicher Farbe erfüllt σ\sigma die Klausel (¬xi¬xj)(\neg x_i \vee \neg x_j), d.h. höchstens eine Variable ist wahr
- Also haben alle auf wahr gesetzten Variablen verschiedene Farben

Die Konstruktion ist polynomiell, da höchstens O(n2)O(n^2) zusätzliche Klauseln hinzugefügt werden.

deepseek/deepseek-chat-v3.1

Exercise 7: Reduktion

Zeigen Sie für jedes der folgenden Probleme AA entweder, dass es in P\mathsf{P} liegt, oder, dass es NP\mathsf{NP}-hart ist.
Geben Sie hierfür jeweils eine geeignete polynomielle Reduktion an und begründen Sie deren Korrektheit.

Reduktionsfunktionen müssen präzise definiert sein und Sie müssen klar angeben, welche Probleme Sie reduzieren. Die Korrektheit der Reduktion müssen Sie aber nur skizzieren und nicht formal beweisen.

Achtung: Auch um zu zeigen, dass das Problem in P\mathsf{P} liegt, ist eine Reduktion anzugeben!

Hinweis: Um zu zeigen, dass ein Problem AA in P\mathsf{P} liegt, geben Sie eine Reduktion ApBA\le_p B für ein BPB\in\mathsf{P} an, reduzieren Sie also AA auf ein Problem BB, von dem wir wissen, dass es in P\mathsf{P} liegt, z.B. 2COL\mathsf{2COL} oder 2KNF-SAT\mathsf{2KNF\text{-}SAT}.

Um zu zeigen, dass ein Problem AA NP\mathsf{NP}-hart ist, geben Sie eine Reduktion BpAB\le_p A an, wobei BB ein bekanntes NP-hartes Problem ist, etwa 3COL\mathsf{3COL}, SAT\mathsf{SAT}, oder CLIQUE\mathsf{CLIQUE}.

Subproblem a (6.0/6.0P)

Gegeben: Drei KNF-Formeln F1,F2,F3F_1, F_2, F_3 mit Variablen aus VV.

Problem AA: Gibt es eine Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\}, die genau zwei der drei Formeln erfüllt?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: SATpA\mathsf{SAT} \le_p A
Begründung:
Gegeben eine SAT\mathsf{SAT}-Instanz FF mit Variablenmenge XX. Wir definieren eine Instanz von AA wie folgt: Sei V=X{t,u}V = X \cup \{t, u\} mit neuen Variablen tt und uu. Definiere die drei KNF-Formeln:
- F1=FF_1 = F
- F2F_2 als die KNF-Formel, die nur die Klausel (t¬t)(t \lor \neg t) enthält (immer erfüllt).
- F3F_3 als die KNF-Formel, die die Klauseln (u)(u) und (¬u)(\neg u) enthält (immer unerfüllt).

Dann gilt: FF ist erfüllbar genau dann, wenn es eine Belegung gibt, die genau zwei der drei Formeln erfüllt.
- Wenn FF erfüllbar ist, gibt es eine Belegung σ\sigma, die FF erfüllt. Erweitere σ\sigma beliebig auf tt und uu (z.B. beide 0). Dann erfüllt σ\sigma F1F_1 und F2F_2 (da F2F_2 immer wahr), aber nicht F3F_3, also genau zwei.
- Wenn FF nicht erfüllbar ist, dann für jede Belegung: F1F_1 nicht erfüllt, F2F_2 immer erfüllt, F3F_3 nie erfüllt, also nur F2F_2 erfüllt, also genau eine, nicht zwei.

Daher ist die Reduktion korrekt und polynomiell.

Subproblem b (8.0/8.0P)

Gegeben: Eine 2KNF-Formel FF mit Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\}, eine Menge {1,...,l}\{1, ..., l\} von Farben (mit l>0l>0) und eine Funktion g:V{1,...,l}g: V \to \{1 ,...,l\}, die jeder Variable eine Farbe zuordnet.

Problem AA: Gibt es eine erfüllende Belegung σ\sigma, sodass alle Variablen, die von σ\sigma zu Wahr gesetzt werden, unterschiedliche Farben haben? Formal: gibt es eine erfüllende Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\} mit g(xi)g(xj)g(x_i) \neq g(x_j) für alle i<jni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: Ap2KNF-SATA \le_p \mathsf{2KNF\text{-}SAT}
Begründung:
Gegeben eine Instanz von AA: eine 2KNF-Formel FF mit Variablenmenge VV, eine Farbmenge {1,,l}\{1, \dots, l\} und eine Funktion g:V{1,,l}g: V \to \{1, \dots, l\}. Wir konstruieren eine neue 2KNF-Formel FF' wie folgt: FF' enthält alle Klauseln von FF. Zusätzlich fügen wir für jede Farbe cc und für jedes Paar distincter Variablen x,yVx, y \in V mit g(x)=g(y)=cg(x) = g(y) = c die Klausel (¬x¬y)(\neg x \lor \neg y) hinzu. Da alle Klauseln in FF' höchstens zwei Literale haben, ist FF' eine 2KNF-Formel.

Korrektheit: Wenn FF' erfüllbar ist, gibt es eine Belegung σ\sigma, die FF' erfüllt. Da FF' FF enthält, erfüllt σ\sigma auch FF. Die hinzugefügten Klauseln (¬x¬y)(\neg x \lor \neg y) für gleiche Farben stellen sicher, dass für jede Farbe cc höchstens eine Variable mit Farbe cc auf Wahr gesetzt ist, also alle auf Wahr gesetzten Variablen unterschiedliche Farben haben. Umgekehrt, wenn es eine erfüllende Belegung σ\sigma für FF gibt, bei der alle auf Wahr gesetzten Variablen unterschiedliche Farben haben, dann erfüllt σ\sigma auch alle hinzugefügten Klauseln (¬x¬y)(\neg x \lor \neg y), da für gleiche Farben nicht beide Variablen wahr sein können. Thus, σ\sigma erfüllt FF'. Daher ist die Instanz von AA genau dann ja, wenn FF' erfüllbar ist.

Die Reduktion ist polynomiell, da die Anzahl der hinzugefügten Klauseln durch O(V2)O(|V|^2) beschränkt ist. Da 2KNF-SATP\mathsf{2KNF\text{-}SAT} \in \mathsf{P}, folgt APA \in \mathsf{P}.

deepseek/deepseek-r1-0528

Exercise 7: Reduktion

Zeigen Sie für jedes der folgenden Probleme AA entweder, dass es in P\mathsf{P} liegt, oder, dass es NP\mathsf{NP}-hart ist.
Geben Sie hierfür jeweils eine geeignete polynomielle Reduktion an und begründen Sie deren Korrektheit.

Reduktionsfunktionen müssen präzise definiert sein und Sie müssen klar angeben, welche Probleme Sie reduzieren. Die Korrektheit der Reduktion müssen Sie aber nur skizzieren und nicht formal beweisen.

Achtung: Auch um zu zeigen, dass das Problem in P\mathsf{P} liegt, ist eine Reduktion anzugeben!

Hinweis: Um zu zeigen, dass ein Problem AA in P\mathsf{P} liegt, geben Sie eine Reduktion ApBA\le_p B für ein BPB\in\mathsf{P} an, reduzieren Sie also AA auf ein Problem BB, von dem wir wissen, dass es in P\mathsf{P} liegt, z.B. 2COL\mathsf{2COL} oder 2KNF-SAT\mathsf{2KNF\text{-}SAT}.

Um zu zeigen, dass ein Problem AA NP\mathsf{NP}-hart ist, geben Sie eine Reduktion BpAB\le_p A an, wobei BB ein bekanntes NP-hartes Problem ist, etwa 3COL\mathsf{3COL}, SAT\mathsf{SAT}, oder CLIQUE\mathsf{CLIQUE}.

Subproblem a (6.0/6.0P)

Gegeben: Drei KNF-Formeln F1,F2,F3F_1, F_2, F_3 mit Variablen aus VV.

Problem AA: Gibt es eine Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\}, die genau zwei der drei Formeln erfüllt?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: 3SATpA\mathsf{3SAT} \le_p A
Begründung:
Gegeben eine Instanz von 3SAT\mathsf{3SAT}, d.h. eine 3KNF-Formel FF über einer Variablenmenge WW. Wir konstruieren eine Instanz von AA wie folgt: Die Variablenmenge sei V=WV = W. Definiere die drei KNF-Formeln:
- F1=FF_1 = F
- F2=FF_2 = F
- F3=F_3 = \bot, wobei \bot die unerfüllbare KNF-Formel ist, dargestellt durch eine einzelne leere Klausel (d.h., F3F_3 ist für alle Belegungen falsch).

Korrektheit der Reduktion:
- Wenn FF erfüllbar ist: Dann existiert eine Belegung σ:V{0,1}\sigma: V \to \{0,1\}, die FF erfüllt. Da F1=FF_1 = F und F2=FF_2 = F, erfüllt σ\sigma sowohl F1F_1 als auch F2F_2. Da F3=F_3 = \bot unerfüllbar ist, erfüllt σ\sigma F3F_3 nicht. Somit erfüllt σ\sigma genau zwei der drei Formeln (F1F_1 und F2F_2).
- Wenn FF unerfüllbar ist: Dann gibt es keine Belegung, die FF erfüllt, also erfüllt keine Belegung F1F_1 oder F2F_2. Zusätzlich ist F3=F_3 = \bot unerfüllbar, also erfüllt keine Belegung F3F_3. Daher erfüllt jede Belegung höchstens null Formeln (insbesondere nicht genau zwei).

Somit ist FF erfüllbar genau dann, wenn es eine Belegung gibt, die genau zwei der Formeln F1,F2,F3F_1, F_2, F_3 erfüllt. Die Reduktion ist polynomiell, da die Konstruktion nur das Kopieren von FF und das Erstellen der konstanten unerfüllbaren Formel F3F_3 erfordert.

Subproblem b (8.0/8.0P)

Gegeben: Eine 2KNF-Formel FF mit Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\}, eine Menge {1,...,l}\{1, ..., l\} von Farben (mit l>0l>0) und eine Funktion g:V{1,...,l}g: V \to \{1 ,...,l\}, die jeder Variable eine Farbe zuordnet.

Problem AA: Gibt es eine erfüllende Belegung σ\sigma, sodass alle Variablen, die von σ\sigma zu Wahr gesetzt werden, unterschiedliche Farben haben? Formal: gibt es eine erfüllende Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\} mit g(xi)g(xj)g(x_i) \neq g(x_j) für alle i<jni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: Ap2SATA \le_p \mathsf{2SAT}
Begründung:
Gegeben eine Instanz von AA: eine 2KNF-Formel FF über Variablen V={x1,,xn}V = \{x_1, \dots, x_n\}, eine Farbmenge {1,,l}\{1, \dots, l\} und eine Färbung g:V{1,,l}g: V \to \{1, \dots, l\}. Wir konstruieren eine 2KNF-Formel FF' wie folgt:
F=F1i<jng(xi)=g(xj)(¬xi¬xj)
F' = F \land \bigwedge_{\substack{1 \leq i < j \leq n \\ g(x_i) = g(x_j)}} (\neg x_i \lor \neg x_j)

Die zusätzlichen Klauseln (¬xi¬xj)(\neg x_i \lor \neg x_j) für jedes Paar von Variablen xi,xjx_i, x_j mit gleicher Farbe (g(xi)=g(xj)g(x_i) = g(x_j)) stellen sicher, dass höchstens eine Variable pro Farbe auf 11 gesetzt werden kann. 

- Korrektheit:  
  - Wenn es eine erfüllende Belegung σ\sigma für FF gibt, die die Farbbedingung erfüllt (d.h., alle auf 11 gesetzten Variablen haben unterschiedliche Farben), dann erfüllt σ\sigma auch FF', da FF erfüllt ist und keine zwei Variablen gleicher Farbe beide auf 11 gesetzt sind, sodass alle hinzugefügten Klauseln erfüllt sind.  
  - Wenn FF' erfüllbar ist, dann erfüllt eine erfüllende Belegung σ\sigma sowohl FF als auch die zusätzlichen Klauseln. Letztere garantieren, dass für keine Farbe zwei Variablen beide auf 11 gesetzt sind, sodass die Farbbedingung erfüllt ist.  

Die Reduktion ist polynomiell, da die Anzahl der hinzugefügten Klauseln durch (n2)=O(n2)\binom{n}{2} = O(n^2) beschränkt ist und jede Klausel in konstanter Zeit konstruiert werden kann. Da 2SATP\mathsf{2SAT} \in \mathsf{P}, folgt APA \in \mathsf{P}.

google/gemini-2.5-pro

Exercise 7: Reduktion

Zeigen Sie für jedes der folgenden Probleme AA entweder, dass es in P\mathsf{P} liegt, oder, dass es NP\mathsf{NP}-hart ist.
Geben Sie hierfür jeweils eine geeignete polynomielle Reduktion an und begründen Sie deren Korrektheit.

Reduktionsfunktionen müssen präzise definiert sein und Sie müssen klar angeben, welche Probleme Sie reduzieren. Die Korrektheit der Reduktion müssen Sie aber nur skizzieren und nicht formal beweisen.

Achtung: Auch um zu zeigen, dass das Problem in P\mathsf{P} liegt, ist eine Reduktion anzugeben!

Hinweis: Um zu zeigen, dass ein Problem AA in P\mathsf{P} liegt, geben Sie eine Reduktion ApBA\le_p B für ein BPB\in\mathsf{P} an, reduzieren Sie also AA auf ein Problem BB, von dem wir wissen, dass es in P\mathsf{P} liegt, z.B. 2COL\mathsf{2COL} oder 2KNF-SAT\mathsf{2KNF\text{-}SAT}.

Um zu zeigen, dass ein Problem AA NP\mathsf{NP}-hart ist, geben Sie eine Reduktion BpAB\le_p A an, wobei BB ein bekanntes NP-hartes Problem ist, etwa 3COL\mathsf{3COL}, SAT\mathsf{SAT}, oder CLIQUE\mathsf{CLIQUE}.

Subproblem a (6.0/6.0P)

Gegeben: Drei KNF-Formeln F1,F2,F3F_1, F_2, F_3 mit Variablen aus VV.

Problem AA: Gibt es eine Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\}, die genau zwei der drei Formeln erfüllt?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: SATpA\mathsf{SAT} \le_p A
Begründung:
Wir zeigen, dass das Problem AA NP\mathsf{NP}-hart ist, indem wir das bekannte NP\mathsf{NP}-harte Problem SAT\mathsf{SAT} polynomiell auf AA reduzieren.

Sei Φ\Phi eine beliebige KNF-Formel über einer Variablenmenge VV, die eine Instanz von SAT\mathsf{SAT} ist. Wir konstruieren daraus eine Instanz von Problem AA, also drei KNF-Formeln (F1,F2,F3)(F_1, F_2, F_3), wie folgt:
- F1:=ΦF_1 := \Phi
- F2:=(x¬x)F_2 := (x \lor \neg x), wobei xx eine beliebige Variable ist (z.B. eine aus VV oder eine neue). Dies ist eine Tautologie.
- F3:=(x¬x)F_3 := (x \land \neg x), was der KNF-Formel (x)(¬x)(x) \land (\neg x) entspricht. Dies ist ein Widerspruch.

Diese Reduktion ist in Polynomialzeit durchführbar, da die erzeugten Formeln F2F_2 und F3F_3 konstante Größe haben und F1F_1 einfach die Eingabeformel Φ\Phi ist.

Korrektheit der Reduktion:
Wir müssen zeigen, dass Φ\Phi genau dann erfüllbar ist, wenn es eine Belegung σ\sigma gibt, die genau zwei der Formeln F1,F2,F3F_1, F_2, F_3 erfüllt.

(\Rightarrow) Angenommen, Φ\Phi ist erfüllbar. Sei σ\sigma eine erfüllende Belegung für Φ\Phi.
- σ\sigma erfüllt F1F_1, da F1=ΦF_1 = \Phi.
- σ\sigma erfüllt F2F_2, da F2F_2 eine Tautologie ist und von jeder Belegung erfüllt wird.
- σ\sigma erfüllt F3F_3 nicht, da F3F_3 ein Widerspruch ist und von keiner Belegung erfüllt werden kann.
Somit erfüllt σ\sigma genau zwei Formeln, nämlich F1F_1 und F2F_2. Die Antwort für die Instanz (F1,F2,F3)(F_1, F_2, F_3) von Problem AA ist also "Ja".

(\Leftarrow) Angenommen, es gibt eine Belegung σ\sigma, die genau zwei der Formeln F1,F2,F3F_1, F_2, F_3 erfüllt. Es gibt drei Möglichkeiten:
1.  σ\sigma erfüllt F1F_1 und F2F_2, aber nicht F3F_3. Da σ\sigma die Formel F1=ΦF_1 = \Phi erfüllt, ist Φ\Phi erfüllbar.
2.  σ\sigma erfüllt F1F_1 und F3F_3, aber nicht F2F_2. Dieser Fall kann nicht eintreten, da keine Belegung die widersprüchliche Formel F3F_3 erfüllen kann.
3.  σ\sigma erfüllt F2F_2 und F3F_3, aber nicht F1F_1. Dieser Fall kann ebenfalls nicht eintreten, da F3F_3 unerfüllbar ist.

Da nur der erste Fall möglich ist, muss Φ\Phi erfüllbar sein, wenn die Instanz von AA eine "Ja"-Instanz ist.

Zusammenfassend ist Φ\Phi genau dann erfüllbar, wenn die konstruierte Instanz von AA eine "Ja"-Antwort hat. Da SAT\mathsf{SAT} NP\mathsf{NP}-hart ist, ist somit auch das Problem AA NP\mathsf{NP}-hart.

Subproblem b (8.0/8.0P)

Gegeben: Eine 2KNF-Formel FF mit Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\}, eine Menge {1,...,l}\{1, ..., l\} von Farben (mit l>0l>0) und eine Funktion g:V{1,...,l}g: V \to \{1 ,...,l\}, die jeder Variable eine Farbe zuordnet.

Problem AA: Gibt es eine erfüllende Belegung σ\sigma, sodass alle Variablen, die von σ\sigma zu Wahr gesetzt werden, unterschiedliche Farben haben? Formal: gibt es eine erfüllende Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\} mit g(xi)g(xj)g(x_i) \neq g(x_j) für alle i<jni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: Ap2KNF-SATA \le_p \mathsf{2KNF\text{-}SAT}
Begründung:
Wir zeigen, dass das Problem AA in P\mathsf{P} liegt, indem wir es polynomiell auf das Problem 2KNF-SAT\mathsf{2KNF\text{-}SAT} reduzieren, welches bekanntlich in P\mathsf{P} ist.

Sei (F,g)(F, g) eine Instanz von Problem AA, wobei FF eine 2KNF-Formel über der Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\} ist und g:V{1,...,l}g: V \to \{1, ..., l\} eine Farbfunktion. Die Bedingung des Problems ist, dass in einer erfüllenden Belegung σ\sigma von FF alle Variablen, die auf Wahr gesetzt werden, unterschiedliche Farben haben müssen. Dies ist äquivalent zu der Aussage, dass für jedes Paar von Variablen xi,xjx_i, x_j mit der gleichen Farbe (g(xi)=g(xj)g(x_i)=g(x_j)) nicht beide gleichzeitig auf Wahr gesetzt werden dürfen. Diese Bedingung lässt sich durch die logische Klausel (¬xi¬xj)(\neg x_i \lor \neg x_j) ausdrücken.

Wir konstruieren eine neue 2KNF-Formel FF' wie folgt:
FF' ist die Konjunktion von FF und einer Menge von neuen Klauseln FgF_g. Die Menge FgF_g wird wie folgt gebildet: Für jedes Paar von verschiedenen Variablen (xi,xj)(x_i, x_j) mit iji \neq j, für die g(xi)=g(xj)g(x_i) = g(x_j) gilt, fügen wir die Klausel (¬xi¬xj)(\neg x_i \lor \neg x_j) zu FgF_g hinzu.
Die resultierende Formel ist F=FCFgCF' = F \land \bigwedge_{C \in F_g} C.
Da FF eine 2KNF-Formel ist und alle Klauseln in FgF_g ebenfalls 2-Klauseln sind, ist FF' eine 2KNF-Formel.

Die Reduktion ist in Polynomialzeit durchführbar. Die Anzahl der Variablen ist nn. Es gibt (n2)\binom{n}{2} Paare von Variablen. Für jedes Paar prüfen wir, ob die Farben gleich sind und fügen gegebenenfalls eine Klausel hinzu. Die Größe von FF' ist also polynomiell in der Größe der Eingabe.

Korrektheit der Reduktion:
Wir skizzieren, warum die Instanz (F,g)(F, g) von AA eine Ja-Antwort hat genau dann, wenn die Formel FF' erfüllbar ist.

(\Rightarrow) Angenommen, es gibt eine erfüllende Belegung σ\sigma für FF, die die Farbbedingung erfüllt.
- σ\sigma erfüllt per Definition alle Klauseln in FF.
- Betrachten wir eine Klausel (¬xi¬xj)(\neg x_i \lor \neg x_j) aus FgF_g. Sie wurde hinzugefügt, weil g(xi)=g(xj)g(x_i)=g(x_j). Da σ\sigma die Farbbedingung erfüllt, kann nicht gleichzeitig σ(xi)=1\sigma(x_i)=1 und σ(xj)=1\sigma(x_j)=1 gelten. Also ist mindestens eine der Variablen auf 0 gesetzt, was die Klausel (¬xi¬xj)(\neg x_i \lor \neg x_j) wahr macht.
- Somit erfüllt σ\sigma alle Klauseln in FF', also ist FF' erfüllbar.

(\Leftarrow) Angenommen, FF' ist erfüllbar und sei σ\sigma eine erfüllende Belegung.
- Da FF' die Konjunktion von FF und FgF_g ist, muss σ\sigma sowohl FF als auch alle Klauseln in FgF_g erfüllen.
- Dass σ\sigma FF erfüllt, ist die erste Bedingung für eine Lösung von AA.
- Dass σ\sigma alle Klauseln in FgF_g erfüllt, bedeutet, dass für jedes Paar xi,xjx_i, x_j mit g(xi)=g(xj)g(x_i)=g(x_j) die Klausel (¬xi¬xj)(\neg x_i \lor \neg x_j) wahr ist. Dies impliziert, dass nicht beide, σ(xi)\sigma(x_i) und σ(xj)\sigma(x_j), 1 sein können. Dies ist genau die Farbbedingung des Problems AA.
- Also ist σ\sigma eine gültige Lösung für die Instanz (F,g)(F, g) von AA.

Da AA auf 2KNF-SAT\mathsf{2KNF\text{-}SAT} polynomiell reduzierbar ist und 2KNF-SATP\mathsf{2KNF\text{-}SAT} \in \mathsf{P}, liegt auch AA in P\mathsf{P}.

openai/gpt-5

Exercise 7: Reduktion

Zeigen Sie für jedes der folgenden Probleme AA entweder, dass es in P\mathsf{P} liegt, oder, dass es NP\mathsf{NP}-hart ist.
Geben Sie hierfür jeweils eine geeignete polynomielle Reduktion an und begründen Sie deren Korrektheit.

Reduktionsfunktionen müssen präzise definiert sein und Sie müssen klar angeben, welche Probleme Sie reduzieren. Die Korrektheit der Reduktion müssen Sie aber nur skizzieren und nicht formal beweisen.

Achtung: Auch um zu zeigen, dass das Problem in P\mathsf{P} liegt, ist eine Reduktion anzugeben!

Hinweis: Um zu zeigen, dass ein Problem AA in P\mathsf{P} liegt, geben Sie eine Reduktion ApBA\le_p B für ein BPB\in\mathsf{P} an, reduzieren Sie also AA auf ein Problem BB, von dem wir wissen, dass es in P\mathsf{P} liegt, z.B. 2COL\mathsf{2COL} oder 2KNF-SAT\mathsf{2KNF\text{-}SAT}.

Um zu zeigen, dass ein Problem AA NP\mathsf{NP}-hart ist, geben Sie eine Reduktion BpAB\le_p A an, wobei BB ein bekanntes NP-hartes Problem ist, etwa 3COL\mathsf{3COL}, SAT\mathsf{SAT}, oder CLIQUE\mathsf{CLIQUE}.

Subproblem a (6.0/6.0P)

Gegeben: Drei KNF-Formeln F1,F2,F3F_1, F_2, F_3 mit Variablen aus VV.

Problem AA: Gibt es eine Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\}, die genau zwei der drei Formeln erfüllt?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: SAT ≤p A
Begründung:
Gegeben eine KNF-Formel φ über Variablenmenge V. Definiere eine Abbildung f, die φ auf ein Triple (F1,F2,F3) abbildet:
- F1 := φ.
- Falls V ≠ ∅, wähle ein beliebiges x ∈ V und setze F2 := (x ∨ ¬x) (eine tautologische Klausel), F3 := (x) ∧ (¬x) (zwei widersprüchliche Einheitsklauseln).
- Falls V = ∅, setze F2 := ⊤ (leere Konjunktion) und F3 := ⊥ (leere Klausel).
Alle drei Formeln sind KNF-Formeln über Variablen aus V, und f ist in polynomieller Zeit berechenbar.

Korrektheitsskizze: Für jede Belegung σ gilt stets σ ⊨ F2 und σ ⊭ F3. Damit sind genau zwei der drei Formeln F1,F2,F3 unter σ erfüllt genau dann, wenn σ ⊨ F1. Also ist φ erfüllbar genau dann, wenn f(φ) eine Belegung hat, die genau zwei der drei Formeln erfüllt. Damit zeigt f die Reduktion SAT ≤p A und A ist NP-hart.

Subproblem b (8.0/8.0P)

Gegeben: Eine 2KNF-Formel FF mit Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\}, eine Menge {1,...,l}\{1, ..., l\} von Farben (mit l>0l>0) und eine Funktion g:V{1,...,l}g: V \to \{1 ,...,l\}, die jeder Variable eine Farbe zuordnet.

Problem AA: Gibt es eine erfüllende Belegung σ\sigma, sodass alle Variablen, die von σ\sigma zu Wahr gesetzt werden, unterschiedliche Farben haben? Formal: gibt es eine erfüllende Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\} mit g(xi)g(xj)g(x_i) \neq g(x_j) für alle i<jni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: A ≤p 2KNF-SAT
Begründung:
Gegeben eine Instanz (F, V, l, g). Konstruiere eine 2KNF-Formel F' über denselben Variablen durch
F' := F ∧ ⋀_{c=1}^l ⋀_{i<j, g(x_i)=g(x_j)=c} (¬x_i ∨ ¬x_j).
Diese Zusatzklauseln erzwingen, dass nicht zwei Variablen derselben Farbe zugleich wahr sein können. Die Anzahl der hinzugefügten Klauseln ist höchstens O(n^2), die Konstruktion ist polynomiell, und F' ist eine 2KNF-Formel.

Korrektheit:
- Wenn es eine erfüllende Belegung σ von F gibt, in der alle wahren Variablen paarweise verschiedene Farben haben, dann verletzt σ keine Klausel (¬x_i ∨ ¬x_j) für gleichfarbige Paare; also erfüllt σ auch F'.
- Umgekehrt garantiert jede erfüllende Belegung σ von F' die Erfüllung aller (¬x_i ∨ ¬x_j) für gleichfarbige Paare, also ist pro Farbe höchstens eine Variable wahr. Damit haben alle wahren Variablen unterschiedliche Farben und σ erfüllt F.

Also ist (F, g, l) ein Ja-Fall von A genau dann, wenn F' erfüllbar ist. Da 2KNF-SAT ∈ P, folgt A ∈ P.

openai/gpt-oss-120b

Exercise 7: Reduktion

Zeigen Sie für jedes der folgenden Probleme AA entweder, dass es in P\mathsf{P} liegt, oder, dass es NP\mathsf{NP}-hart ist.
Geben Sie hierfür jeweils eine geeignete polynomielle Reduktion an und begründen Sie deren Korrektheit.

Reduktionsfunktionen müssen präzise definiert sein und Sie müssen klar angeben, welche Probleme Sie reduzieren. Die Korrektheit der Reduktion müssen Sie aber nur skizzieren und nicht formal beweisen.

Achtung: Auch um zu zeigen, dass das Problem in P\mathsf{P} liegt, ist eine Reduktion anzugeben!

Hinweis: Um zu zeigen, dass ein Problem AA in P\mathsf{P} liegt, geben Sie eine Reduktion ApBA\le_p B für ein BPB\in\mathsf{P} an, reduzieren Sie also AA auf ein Problem BB, von dem wir wissen, dass es in P\mathsf{P} liegt, z.B. 2COL\mathsf{2COL} oder 2KNF-SAT\mathsf{2KNF\text{-}SAT}.

Um zu zeigen, dass ein Problem AA NP\mathsf{NP}-hart ist, geben Sie eine Reduktion BpAB\le_p A an, wobei BB ein bekanntes NP-hartes Problem ist, etwa 3COL\mathsf{3COL}, SAT\mathsf{SAT}, oder CLIQUE\mathsf{CLIQUE}.

Subproblem a (6.0/6.0P)

Gegeben: Drei KNF-Formeln F1,F2,F3F_1, F_2, F_3 mit Variablen aus VV.

Problem AA: Gibt es eine Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\}, die genau zwei der drei Formeln erfüllt?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: SATpA\text{SAT}\le_p A

Begründung:
Gegeben sei eine CNF‑Formel FF (Instanz von SAT) über Variablenmenge VV.
Wir konstruieren drei Formeln F1,F2,F3F_1,F_2,F_3 über derselben Variablenmenge:

* F1:=FF_1 := F.
* F2:=(x¬x)F_2 := (x \lor \lnot x) für ein beliebiges xVx\in V (eine Tautologie, also unter jeder Belegung erfüllt).
* F3:=(x)(¬x)F_3 := (x) \land (\lnot x) (ein Widerspruch; niemals erfüllt).

Die Konstruktion ist eindeutig in polynomialer Zeit möglich.

Nun gilt:

  σ:V{0,1} mit genau zwei erfu¨llten Formeln among F1,F2,F3  Longleftrightarrow  σ erfu¨llt F1
\exists\;\sigma:V\to\{0,1\}\text{ mit genau zwei erfüllten Formeln among }F_1,F_2,F_3
\iff
\sigma \text{ erfüllt }F_1


denn F2F_2 ist immer erfüllt und F3F_3 ist nie erfüllt.  
Somit gibt es eine solche Belegung genau dann, wenn FF erfüllbar ist, d.h. genau dann, wenn die SAT‑Instanz mit „Ja“ beantwortet wird.

Damit ist die Abbildung F(F1,F2,F3)F \mapsto (F_1,F_2,F_3) eine polynomialzeit‑Reduktion von SAT auf das gegebene Problem AA. Da SAT NP‑hart ist, ist AA ebenfalls NP‑hart (und liegt offensichtlich in NP, also ist AA NP‑vollständig).

Subproblem b (8.0/8.0P)

Gegeben: Eine 2KNF-Formel FF mit Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\}, eine Menge {1,...,l}\{1, ..., l\} von Farben (mit l>0l>0) und eine Funktion g:V{1,...,l}g: V \to \{1 ,...,l\}, die jeder Variable eine Farbe zuordnet.

Problem AA: Gibt es eine erfüllende Belegung σ\sigma, sodass alle Variablen, die von σ\sigma zu Wahr gesetzt werden, unterschiedliche Farben haben? Formal: gibt es eine erfüllende Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\} mit g(xi)g(xj)g(x_i) \neq g(x_j) für alle i<jni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: Ap2SATA\le_p \mathsf{2SAT}  

Begründung:  
Gegeben sei eine Instanz des Problems AA, also  
* eine 2‑KNF‑Formel FF über den Variablen V={x1,,xn}V=\{x_1,\dots ,x_n\},  
* eine Farbfunktion g:V{1,,l}g:V\to\{1,\dots ,l\}.

Wir konstruieren in polynomialer Zeit eine neue 2‑KNF‑Formel FF' wie folgt  

F  :=  F    i<jg(xi)=g(xj)(¬xi¬xj).
F' \;:=\; F\;\land\;\bigwedge_{\substack{i<j\\ g(x_i)=g(x_j)}}(\lnot x_i \,\lor\, \lnot x_j).


Der zweite Teil besteht aus allen Paar‑Klauseln, die für jedes Farb‑Kollektiv cc genau die Aussage „es können nicht beide Variablen derselben Farbe wahr sein“ ausdrücken.  
Da jede dieser Klauseln nur zwei Literale besitzt, ist FF' wieder eine 2‑KNF‑Formel.  
Die Anzahl der hinzugefügten Klauseln ist höchstens (n2)\binom{n}{2}, also polynomial in nn; die Konstruktion ist daher polynomialzeit­machbar.

Nun gilt:

Wenn es eine Belegung σ\sigma gibt, die FF erfüllt und bei der alle wahr gesetzten Variablen unterschiedliche Farben besitzen, dann erfüllt σ\sigma per Definition jede der Klauseln (¬xi¬xj)(\lnot x_i\lor\lnot x_j) für Variablen mit gleicher Farbe – weil höchstens eine von ihnen wahr ist. Also erfüllt σ\sigma auch FF'.  

Umgekehrt: Erfüllt eine Belegung σ\sigma die Formel FF', dann erfüllt sie zunächst FF (da FF ein Teil von FF' ist) und sie verletzt keine der Klauseln (¬xi¬xj)(\lnot x_i\lor\lnot x_j). Letztere Klauseln verhindern genau, dass zwei Variablen derselben Farbe gleichzeitig wahr sind. Deshalb besitzt σ\sigma die geforderte Eigenschaft, dass alle wahren Variablen unterschiedliche Farben haben.

Damit ist

  σ mit den Bedingungen von ALongleftrightarrowF ist erfu¨llbar.
\exists\;\sigma\text{ mit den Bedingungen von }A\quad\Longleftrightarrow\quad F' \text{ ist erfüllbar}.


Die Abbildung (F,g)F(F,g)\mapsto F' ist eine polynomialzeit‑Reduktion von AA auf das klassische 2SAT\mathsf{2SAT}-Entscheidungsproblem. Da 2SATP\mathsf{2SAT}\in\mathsf{P} ist, folgt, dass APA\in\mathsf{P} (und naturgemäß liegt AA in NP).

AP
\boxed{A\in\mathsf{P}}

qwen/qwen3-235b-a22b

Exercise 7: Reduktion

Zeigen Sie für jedes der folgenden Probleme AA entweder, dass es in P\mathsf{P} liegt, oder, dass es NP\mathsf{NP}-hart ist.
Geben Sie hierfür jeweils eine geeignete polynomielle Reduktion an und begründen Sie deren Korrektheit.

Reduktionsfunktionen müssen präzise definiert sein und Sie müssen klar angeben, welche Probleme Sie reduzieren. Die Korrektheit der Reduktion müssen Sie aber nur skizzieren und nicht formal beweisen.

Achtung: Auch um zu zeigen, dass das Problem in P\mathsf{P} liegt, ist eine Reduktion anzugeben!

Hinweis: Um zu zeigen, dass ein Problem AA in P\mathsf{P} liegt, geben Sie eine Reduktion ApBA\le_p B für ein BPB\in\mathsf{P} an, reduzieren Sie also AA auf ein Problem BB, von dem wir wissen, dass es in P\mathsf{P} liegt, z.B. 2COL\mathsf{2COL} oder 2KNF-SAT\mathsf{2KNF\text{-}SAT}.

Um zu zeigen, dass ein Problem AA NP\mathsf{NP}-hart ist, geben Sie eine Reduktion BpAB\le_p A an, wobei BB ein bekanntes NP-hartes Problem ist, etwa 3COL\mathsf{3COL}, SAT\mathsf{SAT}, oder CLIQUE\mathsf{CLIQUE}.

Subproblem a (6.0/6.0P)

Gegeben: Drei KNF-Formeln F1,F2,F3F_1, F_2, F_3 mit Variablen aus VV.

Problem AA: Gibt es eine Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\}, die genau zwei der drei Formeln erfüllt?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: SATpA\mathsf{SAT} \le_p A  
Begründung:  
Gegeben eine KNF-Formel FF, konstruieren wir drei Formeln F1=FF_1 = F, F2=xF_2 = x, F3=¬xF_3 = \neg x, wobei xx eine neue Variable ist.  
- Korrektheit:  
  - Wenn FF erfüllbar ist, existiert eine Belegung σ\sigma', die FF erfüllt. Setze x=1x = 1 (erfüllt F2F_2) oder x=0x = 0 (erfüllt F3F_3). In beiden Fällen wird genau eine der beiden Formeln F2F_2 oder F3F_3 erfüllt, während F1F_1 erfüllt ist. Somit gibt es eine Belegung, die genau zwei Formeln erfüllt.  
  - Wenn AA eine positive Antwort hat, gibt es eine Belegung σ\sigma, die genau zwei der drei Formeln erfüllt. Da F2F_2 und F3F_3 sich gegenseitig ausschließen (xx und ¬x\neg x), muss F1=FF_1 = F erfüllt sein. Somit ist FF erfüllbar.  
Die Reduktion ist polynomiell, da F1,F2,F3F_1, F_2, F_3 direkt aus FF konstruiert werden können.

Subproblem b (8.0/8.0P)

Gegeben: Eine 2KNF-Formel FF mit Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\}, eine Menge {1,...,l}\{1, ..., l\} von Farben (mit l>0l>0) und eine Funktion g:V{1,...,l}g: V \to \{1 ,...,l\}, die jeder Variable eine Farbe zuordnet.

Problem AA: Gibt es eine erfüllende Belegung σ\sigma, sodass alle Variablen, die von σ\sigma zu Wahr gesetzt werden, unterschiedliche Farben haben? Formal: gibt es eine erfüllende Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\} mit g(xi)g(xj)g(x_i) \neq g(x_j) für alle i<jni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: Ap2SATA \le_p \mathsf{2SAT}  
Begründung:  
Gegeben eine Instanz von AA mit 2KNF-Formel FF, Farbfunktion gg, konstruieren wir eine neue 2KNF-Formel FF', indem wir für alle Paare von Variablen xi,xjx_i, x_j mit g(xi)=g(xj)g(x_i) = g(x_j) die Klausel (¬xi¬xj)(\neg x_i \lor \neg x_j) hinzufügen.  
- Korrektheit:  
  - Jede erfüllende Belegung von FF' erfüllt automatisch FF und stellt sicher, dass keine zwei Variablen gleicher Farbe gleichzeitig wahr sind (durch die hinzugefügten Klauseln).  
  - Umgekehrt erfüllt jede Belegung, die AA löst, auch FF', da sie FF erfüllt und die Farbbegrenzung einhält.  
- Polynomielle Laufzeit:  
  Für jede Farbe cc mit kck_c Variablen entstehen (kc2)\binom{k_c}{2} Klauseln. Die Gesamtzahl der Klauseln ist in O(n2)O(n^2), was polynomiell bleibt.  
Da 2SATP\mathsf{2SAT} \in \mathsf{P}, folgt APA \in \mathsf{P}.

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

Exercise 7: Reduktion

Zeigen Sie für jedes der folgenden Probleme AA entweder, dass es in P\mathsf{P} liegt, oder, dass es NP\mathsf{NP}-hart ist.
Geben Sie hierfür jeweils eine geeignete polynomielle Reduktion an und begründen Sie deren Korrektheit.

Reduktionsfunktionen müssen präzise definiert sein und Sie müssen klar angeben, welche Probleme Sie reduzieren. Die Korrektheit der Reduktion müssen Sie aber nur skizzieren und nicht formal beweisen.

Achtung: Auch um zu zeigen, dass das Problem in P\mathsf{P} liegt, ist eine Reduktion anzugeben!

Hinweis: Um zu zeigen, dass ein Problem AA in P\mathsf{P} liegt, geben Sie eine Reduktion ApBA\le_p B für ein BPB\in\mathsf{P} an, reduzieren Sie also AA auf ein Problem BB, von dem wir wissen, dass es in P\mathsf{P} liegt, z.B. 2COL\mathsf{2COL} oder 2KNF-SAT\mathsf{2KNF\text{-}SAT}.

Um zu zeigen, dass ein Problem AA NP\mathsf{NP}-hart ist, geben Sie eine Reduktion BpAB\le_p A an, wobei BB ein bekanntes NP-hartes Problem ist, etwa 3COL\mathsf{3COL}, SAT\mathsf{SAT}, oder CLIQUE\mathsf{CLIQUE}.

Subproblem a (6.0/6.0P)

Gegeben: Drei KNF-Formeln F1,F2,F3F_1, F_2, F_3 mit Variablen aus VV.

Problem AA: Gibt es eine Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\}, die genau zwei der drei Formeln erfüllt?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: SATpA\mathsf{SAT} \le_p A
Begründung:
Definiere eine Reduktion von SAT\mathsf{SAT} auf AA: Für eine gegebene KNF-Formel FF mit Variablen aus VV konstruiere F1=FF_1 = F, F2=(x¬x)F_2 = (x \land \lnot x) (Widerspruch, immer unerfüllbar) und F3=(y¬y)F_3 = (y \lor \lnot y) (Tautologie, immer erfüllbar), wobei x,yVx, y \in V neue Variablen sind. 

Korrektheit: FF ist erfüllbar   Longleftrightarrow  \iff es gibt eine Belegung, die genau zwei der drei Formeln erfüllt. 
- Ist FF erfüllbar, so gibt es eine Belegung σ\sigma mit F1(σ)=wahrF_1(\sigma) = \text{wahr}. Da F2F_2 immer falsch und F3F_3 immer wahr ist, erfüllt σ\sigma genau F1F_1 und F3F_3 (also zwei Formeln). 
- Ist FF unerfüllbar, so gilt für alle σ\sigma entweder F1(σ)=falschF_1(\sigma) = \text{falsch}. Somit ist nur F3F_3 erfüllt (eine Formel), also kein σ\sigma erfüllt genau zwei Formeln. 

Die Reduktion ist offensichtlich polynomiell berechenbar, da nur Konstanten hinzugefügt werden.

Subproblem b (8.0/8.0P)

Gegeben: Eine 2KNF-Formel FF mit Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\}, eine Menge {1,...,l}\{1, ..., l\} von Farben (mit l>0l>0) und eine Funktion g:V{1,...,l}g: V \to \{1 ,...,l\}, die jeder Variable eine Farbe zuordnet.

Problem AA: Gibt es eine erfüllende Belegung σ\sigma, sodass alle Variablen, die von σ\sigma zu Wahr gesetzt werden, unterschiedliche Farben haben? Formal: gibt es eine erfüllende Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\} mit g(xi)g(xj)g(x_i) \neq g(x_j) für alle i<jni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: Ap2KNF-SATA \le_p \mathsf{2KNF\text{-}SAT}
Begründung:
Für eine gegebene Instanz von AA (2KNF-Formel FF, Farbenanzahl ll, Farbfunktion gg) konstruiere die 2KNF-Formel FF' durch Hinzufügen aller Klauseln (¬u¬v)(\lnot u \lor \lnot v) für Variablen uvu \neq v mit g(u)=g(v)g(u) = g(v). 

Korrektheit: Eine Belegung σ\sigma erfüllt FF' genau dann, wenn σ\sigma die Originalformel FF erfüllt und keine zwei Variablen mit gleicher Farbe zugleich wahr sind. Dies ist äquivalent zur Bedingung von Problem AA, da die Farbnebenbedingung gerade verlangt, dass alle wahr belegten Variablen unterschiedliche Farben haben. Die Reduktion ist polynomiell, da für jede Farbklasse mit kk Variablen maximal k2k^2 Klauseln hinzugefügt werden – insgesamt also O(n2)\mathcal{O}(n^2) Klauseln für nn Variablen. Da 2KNF-SATP\mathsf{2KNF\text{-}SAT} \in \mathsf{P} ist, folgt unmittelbar APA \in \mathsf{P}.

x-ai/grok-4

Exercise 7: Reduktion

Zeigen Sie für jedes der folgenden Probleme AA entweder, dass es in P\mathsf{P} liegt, oder, dass es NP\mathsf{NP}-hart ist.
Geben Sie hierfür jeweils eine geeignete polynomielle Reduktion an und begründen Sie deren Korrektheit.

Reduktionsfunktionen müssen präzise definiert sein und Sie müssen klar angeben, welche Probleme Sie reduzieren. Die Korrektheit der Reduktion müssen Sie aber nur skizzieren und nicht formal beweisen.

Achtung: Auch um zu zeigen, dass das Problem in P\mathsf{P} liegt, ist eine Reduktion anzugeben!

Hinweis: Um zu zeigen, dass ein Problem AA in P\mathsf{P} liegt, geben Sie eine Reduktion ApBA\le_p B für ein BPB\in\mathsf{P} an, reduzieren Sie also AA auf ein Problem BB, von dem wir wissen, dass es in P\mathsf{P} liegt, z.B. 2COL\mathsf{2COL} oder 2KNF-SAT\mathsf{2KNF\text{-}SAT}.

Um zu zeigen, dass ein Problem AA NP\mathsf{NP}-hart ist, geben Sie eine Reduktion BpAB\le_p A an, wobei BB ein bekanntes NP-hartes Problem ist, etwa 3COL\mathsf{3COL}, SAT\mathsf{SAT}, oder CLIQUE\mathsf{CLIQUE}.

Subproblem a (6.0/6.0P)

Gegeben: Drei KNF-Formeln F1,F2,F3F_1, F_2, F_3 mit Variablen aus VV.

Problem AA: Gibt es eine Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\}, die genau zwei der drei Formeln erfüllt?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: SATpA\mathsf{SAT} \le_p A
Begründung:
Gegeben eine KNF-Formel FF über Variablen VV, führe eine frische Variable xVx \notin V ein. Definiere F1=FF_1 = F, F2=(¬x)F_2 = (\neg x), F3=(x)F_3 = (x) über Variablen V{x}V \cup \{x\}.

Die Reduktion ist polynomialzeitig, da sie nur eine Variable hinzufügt und die Formeln kopiert bzw. einfach definiert.

Korrektheit: Eine Belegung σ\sigma erfüllt genau zwei der Formeln genau dann, wenn FF erfüllbar ist.

- Wenn FF erfüllbar ist durch σ0:V{0,1}\sigma_0 : V \to \{0,1\}, dann erweitere zu σ\sigma mit σ(x)=0\sigma(x)=0: Erfüllt F1F_1 und F2F_2, nicht F3F_3 (genau zwei). Ähnlich für σ(x)=1\sigma(x)=1: Erfüllt F1F_1 und F3F_3, nicht F2F_2.
- Umgekehrt, wenn σ\sigma genau zwei erfüllt: Erfüllen von F2F_2 und F3F_3 erfordert x=0x=0 und x=1x=1, unmöglich. Also muss es F1F_1 und genau eine von F2F_2 oder F3F_3 erfüllen, d.h. σ\sigma eingeschränkt auf VV erfüllt FF. Somit ist FF erfüllbar.

Subproblem b (8.0/8.0P)

Gegeben: Eine 2KNF-Formel FF mit Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\}, eine Menge {1,...,l}\{1, ..., l\} von Farben (mit l>0l>0) und eine Funktion g:V{1,...,l}g: V \to \{1 ,...,l\}, die jeder Variable eine Farbe zuordnet.

Problem AA: Gibt es eine erfüllende Belegung σ\sigma, sodass alle Variablen, die von σ\sigma zu Wahr gesetzt werden, unterschiedliche Farben haben? Formal: gibt es eine erfüllende Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\} mit g(xi)g(xj)g(x_i) \neq g(x_j) für alle i<jni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: Ap2KNF-SATA \le_p \mathsf{2KNF\text{-}SAT}
Begründung:
Gegeben eine Instanz von AA: 2KNF-Formel FF über Variablen V={x1,,xn}V=\{x_1,\dots,x_n\}, Farben {1,,l}\{1,\dots,l\}, Funktion g:V{1,,l}g: V \to \{1,\dots,l\}.

Gruppiere die Variablen nach Farben: Für jede Farbe cc, sei Vc={xVg(x)=c}V_c = \{x \in V \mid g(x)=c\}.

Konstruiere eine neue 2KNF-Formel FF' wie folgt: F=Fc=1lxi,xjVc,i<j(¬xi¬xj)F' = F \land \bigwedge_{c=1}^l \bigwedge_{x_i,x_j \in V_c, i<j} (\neg x_i \lor \neg x_j).

Diese Konstruktion ist polynomialzeitig, da die Anzahl hinzugefügter Klauseln c(Vc2)=O(n2)\sum_c \binom{|V_c|}{2} = O(n^2) beträgt und die Eingabegröße polynomiell darin beschränkt ist.

Korrektheit: FF' ist erfüllbar genau dann, wenn es eine Belegung σ\sigma gibt, die FF erfüllt und für keine zwei Variablen mit gleicher Farbe beide auf 1 setzt, d.h. die wahren Variablen haben paarweise unterschiedliche Farben. Dies ist äquivalent zur Bedingung in AA.

z-ai/glm-4.5

Exercise 7: Reduktion

Zeigen Sie für jedes der folgenden Probleme AA entweder, dass es in P\mathsf{P} liegt, oder, dass es NP\mathsf{NP}-hart ist.
Geben Sie hierfür jeweils eine geeignete polynomielle Reduktion an und begründen Sie deren Korrektheit.

Reduktionsfunktionen müssen präzise definiert sein und Sie müssen klar angeben, welche Probleme Sie reduzieren. Die Korrektheit der Reduktion müssen Sie aber nur skizzieren und nicht formal beweisen.

Achtung: Auch um zu zeigen, dass das Problem in P\mathsf{P} liegt, ist eine Reduktion anzugeben!

Hinweis: Um zu zeigen, dass ein Problem AA in P\mathsf{P} liegt, geben Sie eine Reduktion ApBA\le_p B für ein BPB\in\mathsf{P} an, reduzieren Sie also AA auf ein Problem BB, von dem wir wissen, dass es in P\mathsf{P} liegt, z.B. 2COL\mathsf{2COL} oder 2KNF-SAT\mathsf{2KNF\text{-}SAT}.

Um zu zeigen, dass ein Problem AA NP\mathsf{NP}-hart ist, geben Sie eine Reduktion BpAB\le_p A an, wobei BB ein bekanntes NP-hartes Problem ist, etwa 3COL\mathsf{3COL}, SAT\mathsf{SAT}, oder CLIQUE\mathsf{CLIQUE}.

Subproblem a (6.0/6.0P)

Gegeben: Drei KNF-Formeln F1,F2,F3F_1, F_2, F_3 mit Variablen aus VV.

Problem AA: Gibt es eine Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\}, die genau zwei der drei Formeln erfüllt?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: SATpA\mathsf{SAT} \le_p A
Begründung:
Given a CNF formula FF, we construct three CNF formulas F1,F2,F3F_1, F_2, F_3 as follows:
- F1=FF_1 = F
- F2=xF_2 = x (where xx is a new variable not in FF)
- F3=¬xF_3 = \neg x

If FF is satisfiable, let σ\sigma be a satisfying assignment for FF. Extend σ\sigma to σ\sigma' by setting σ(x)=0\sigma'(x) = 0. Then, σ\sigma' satisfies F1F_1 (since it satisfies FF) and F3F_3 (since it satisfies ¬x\neg x), but not F2F_2 (since it doesn't satisfy xx). So, σ\sigma' satisfies exactly two of the three formulas.

Conversely, if there exists an assignment σ\sigma that satisfies exactly two of the three formulas, then it must satisfy F1F_1 and either F2F_2 or F3F_3 (since it cannot satisfy both F2F_2 and F3F_3). In either case, it satisfies F1=FF_1 = F, so FF is satisfiable.

Therefore, FF is satisfiable if and only if there exists an assignment that satisfies exactly two of the three formulas F1,F2,F3F_1, F_2, F_3.

This reduction is polynomial-time, as we can construct F1,F2,F3F_1, F_2, F_3 from FF in polynomial time.

Therefore, AA is NP-hard.

Subproblem b (8.0/8.0P)

Gegeben: Eine 2KNF-Formel FF mit Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\}, eine Menge {1,...,l}\{1, ..., l\} von Farben (mit l>0l>0) und eine Funktion g:V{1,...,l}g: V \to \{1 ,...,l\}, die jeder Variable eine Farbe zuordnet.

Problem AA: Gibt es eine erfüllende Belegung σ\sigma, sodass alle Variablen, die von σ\sigma zu Wahr gesetzt werden, unterschiedliche Farben haben? Formal: gibt es eine erfüllende Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\} mit g(xi)g(xj)g(x_i) \neq g(x_j) für alle i<jni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: Ap2KNF-SATA \le_p \mathsf{2KNF\text{-}SAT}
Begründung:
Given an instance of problem AA (a 2CNF formula FF, a set of colors {1,...,l}\{1, ..., l\}, and a coloring function g:V{1,...,l}g: V \to \{1, ..., l\}), we construct a new 2CNF formula FF' as follows:

1. Start with F=FF' = F.
2. For each color c{1,...,l}c \in \{1, ..., l\}, let Vc={xV:g(x)=c}V_c = \{x \in V : g(x) = c\} be the set of variables with color cc.
3. For each color cc and for each pair of distinct variables x,yVcx, y \in V_c, add the clause (¬x¬y)(\neg x \vee \neg y) to FF'.

The formula FF' is a 2CNF formula, and it can be constructed in polynomial time (since there are at most O(n2)O(n^2) additional clauses, where nn is the number of variables).

Now, FF' is satisfiable if and only if there exists a satisfying assignment for FF where at most one variable from each color class is set to true. This is exactly the condition required by problem AA.

Since 2CNF-SAT is in P, we can solve problem AA in polynomial time by reducing it to 2CNF-SAT and then solving the resulting 2CNF formula.

Therefore, APA \in \mathsf{P}.