Aufgabe 2)

Unlösbare Probleme und das Halteproblem

• Eine Turingmaschine ist ein mathematisches Modell für die Berechnung.
• Unlösbare Probleme: Probleme, für die keine Turingmaschine existiert, die sie für alle Eingaben lösen kann.
• Das Halteproblem: Entscheidung, ob eine gegebene Turingmaschine bei einer bestimmten Eingabe hält oder nicht.
• Von Alan Turing bewiesen, dass das Halteproblem unentscheidbar ist.
• Formal: Es gibt keine Turingmaschine H, die für jede Turingmaschine T und Eingabe w entscheidet, ob T auf w hält.
• Reduktionsbeweis: Annahme einer Entscheidungsmaschine für das Halteproblem führt zu einem Widerspruch.

a)

Beweise, dass das Halteproblem unentscheidbar ist, indem Du eine Entscheidungsmaschine H für das Halteproblem annimmst und einen Widerspruch erzeugst. Erkläre den Reduktionsbeweis detailliert.

Lösung:

Beweis des Halteproblems durch Reduktionsbeweis

Um zu zeigen, dass das Halteproblem unentscheidbar ist, nehmen wir an, dass es eine Entscheidungsmaschine H gibt, die das Halteproblem lösen kann. Das bedeutet, dass H für jede Turingmaschine T und jede Eingabe w entscheidet, ob T auf w hält. Nun zeigen wir, dass diese Annahme zu einem Widerspruch führt.

Wir konstruieren eine neue Turingmaschine D, die wie folgt arbeitet:

• D nimmt als Eingabe eine Beschreibung einer Turingmaschine T.
• D verwendet Maschine H, um zu entscheiden, ob T auf der Eingabe T hält.
• Wenn H entscheidet, dass T auf T hält, geht D in eine Endlosschleife (hält nicht).
• Wenn H entscheidet, dass T auf T nicht hält, hält D (endet).

Nun analysieren wir, was passiert, wenn wir D sich selbst als Eingabe geben, also D(D):

• Falls H entscheidet, dass D auf D hält: Nach der Definition von D bedeutet das, dass D in eine Endlosschleife geht und nicht hält. Das ist ein Widerspruch.
• Falls H entscheidet, dass D auf D nicht hält: Nach der Definition von D bedeutet das, dass D hält. Auch das ist ein Widerspruch.

In beiden Fällen führt die Annahme, dass H das Halteproblem entscheidet, zu einem Widerspruch. Daher kann es keine solche Entscheidungsmaschine H geben und das Halteproblem ist unentscheidbar.

Formale Darstellung des Reduktionsbeweises

Für formale Zwecke kann der Beweis in folgenden Schritten zusammengefasst werden:

• Annahme: Es existiert eine Turingmaschine H, die für jede Turingmaschine T und Eingabe w entscheidet, ob T auf w hält.
• Konstruktion: Konstruiere eine Turingmaschine D, die wie folgt funktioniert:

function D(T) input: Beschreibung der Turingmaschine T begin     if H(T, T) then         loop forever     else         halt end end function

• Selbstanwendung: Betrachte D(D) und analysiere die Konsequenzen.
• Widerspruch: In beiden möglichen Fällen (H entscheidet, dass D auf D hält oder nicht hält) entsteht ein Widerspruch.
• Schlussfolgerung: H kann nicht existieren, und das Halteproblem ist unentscheidbar.

Dieser Beweis zeigt eindrucksvoll, dass bestimmte Probleme, selbst in der theoretischen Informatik, nicht algorithmisch lösbar sind, und unterstreicht die Grenzen des maschinellen Berechnens.

b)

Beschreibe, wie der Beweis von Alan Turing über die Unentscheidbarkeit des Halteproblems das Konzept von unlösbaren Problemen beeinflusst hat. Gehe dabei auf mindestens zwei weitere Beispiele unlösbarer Probleme ein.

Lösung:

Einfluss von Turings Beweis der Unentscheidbarkeit des Halteproblems auf das Konzept unlösbarer Probleme

Alan Turings Beweis der Unentscheidbarkeit des Halteproblems war ein Meilenstein in der theoretischen Informatik und hat tiefgreifende Auswirkungen auf unser Verständnis von Berechenbarkeit und unlösbaren Problemen. Der Beweis zeigt, dass es bestimmte Probleme gibt, die nicht algorithmisch lösbar sind, unabhängig davon, wie viel Rechenzeit und Speicherplatz zur Verfügung stehen. Dies führte zu einem ganzen Bereich der Informatik, der sich mit der Klassifizierung von Problemen nach ihrer Berechenbarkeit und der Untersuchung der Grenzen dessen, was Maschinen berechnen können, befasst.

Zwei weitere Beispiele unlösbarer Probleme

1. Das Problem der Erfüllbarkeit unentscheidbarer logischer Formeln

Das Entscheidungsproblem der prädikatenlogischen Formeln ist ein weiteres klassisches Beispiel für ein unlösbares Problem. Entscheidungsproblem bezeichnet die Frage, ob eine gegebene prädikatenlogische Formel (eine Formel der Logik erster Stufe) erfüllbar ist, d. h., ob es eine Interpretation gibt, unter der die Formel wahr wird.

Alan Turing und Alonzo Church haben unabhängig voneinander bewiesen, dass dieses Problem unentscheidbar ist. Der Beweis, der ebenfalls auf die Methode des Reduktionsbeweises zurückgreift, zeigt, dass keine Turingmaschine existiert, die allgemeingültig für jede prädikatenlogische Formel entscheiden kann, ob sie erfüllbar ist oder nicht.

2. Das Wortproblem für allgemeine Gruppen

Ein weiteres Beispiel unlösbarer Probleme ist das Wortproblem für allgemeine Gruppen. Das Wortproblem fragt, ob für eine gegebene Gruppe (definiert durch eine Menge von Erzeugern und Relationen) und ein gegebenes Wort (eine Folge von Erzeugern), das Wort das neutrale Element (Identität) der Gruppe darstellt.

Der Mathematiker Emil Post zeigte, dass das Wortproblem für allgemeine Gruppen unentscheidbar ist. Das bedeutet, dass es keine allgemeine Methode gibt, um für jede beliebige Gruppe und jedes beliebige Wort zu entscheiden, ob das Wort in dieser Gruppe das neutrale Element entspricht. Der Beweis nutzt wieder die Technik der Reduktion, indem unlösbare Probleme auf das Wortproblem zurückgeführt werden.

Zusammenfassung

Turings Beweis der Unentscheidbarkeit des Halteproblems hat das Feld der theoretischen Informatik zutiefst beeinflusst. Es führte zu einem besseren Verständnis dafür, dass es viele wesentliche Probleme gibt, die jenseits der Reichweite algorithmischer Lösungen liegen. Dies hat zu umfangreichen Forschungen über die Natur dieser Probleme und ihre Klassifizierung geführt, um die Grenzen der Berechenbarkeit zu definieren. Die Beispiele des Entscheidungsproblems für prädikatenlogische Formeln und des Wortproblems für allgemeine Gruppen veranschaulichen, dass das Konzept von unlösbaren Problemen in verschiedenen Bereichen der Mathematik und Informatik von Bedeutung ist.

c)

Angenommen, eine hypothetische Maschine H' könnte das Halteproblem lösen. Erkläre, warum eine solche Maschine H' nicht zur Lösung des Entscheidbarkeitsproblems für allgemeine Turingmaschinen genutzt werden kann. Verwende dafür formale Argumente.

Lösung:

Warum eine hypothetische Maschine H' das Entscheidbarkeitsproblem nicht lösen kann

Angenommen, es gibt eine hypothetische Maschine H', die das Halteproblem für jede Turingmaschine T auf einer beliebigen Eingabe w lösen kann. Das bedeutet, dass H' entscheidet, ob T auf der Eingabe w anhält oder nicht. Wir werden mittels formaler Argumente zeigen, warum eine solche Maschine H' nicht zur Lösung des Entscheidbarkeitsproblems für allgemeine Turingmaschinen genutzt werden kann.

Definitionen und Annahmen

• \textbf{Halteproblem:} Das Problem, zu entscheiden, ob eine gegebene Turingmaschine T bei einer bestimmten Eingabe w anhält oder nicht.
• \textbf{Entscheidbarkeitsproblem:} Generell das Problem, festzustellen, ob ein Problem algorithmisch lösbar ist, das heißt, ob es eine Turingmaschine gibt, die für alle Eingaben das Problem in endlicher Zeit löst.

Argumentation

Wir nehmen an, dass H' eine Turingmaschine ist, die das Halteproblem löst, das heißt:

• H'(T, w) = true wenn T bei Eingabe w anhält.
• H'(T, w) = false wenn T bei Eingabe w nicht anhält.

Aufgrund dieser Annahmen möchten wir ermitteln, ob H' zur Lösung des allgemeinen Entscheidbarkeitsproblems verwendet werden kann. Dazu analysieren wir einige formale Argumente:

• Selbstanwendung und Widerspruch:Wenn H' ohne Einschränkungen existiert, könnte man versuchen, die Berechnung von H' selbst auf die Eingabe-Daten seiner eigenen Struktur anzuwenden. Dies führt zu Konstruktionen, ähnlich wie dem Reduktionsbeweis des Halteproblems, wo Selbstanwendung in einen Widerspruch mündet.\textbf{Formal:} Angenommen, es existiert ein Entscheidungsverfahren, das für jede Turingmaschine \textbf{T'} und jede Eingabe \textbf{w'} in endlicher Zeit entscheidet, ob \textbf{T'} bei Eingabe \textbf{w'} anhält.Man konstruiere eine Turingmaschine \textbf{D'} genau wie im ursprünglichen Halteproblem-Beweis:

  function D'(T) input: Beschreibung der Turingmaschine T begin     if H'(T, T) then         loop forever     else         halt end end function

  Nun analysiere den Fall, wenn D' auf D' angewandt wird (also D'(D')):
  • Wenn H' (D', D') = true (D' hält bei D'), geht D' in eine Endlosschleife – Widerspruch.
  • Wenn H' (D', D') = false (D' hält nicht bei D'), dann hält D' – Widerspruch.
  In beiden Fällen ergibt sich ein logischer Widerspruch, was zeigt, dass H' nicht existieren kann, ohne die Berechenbarkeitslogik zu brechen.
• Reduktion und widersprüchliche Entscheidbarkeit:Für jede Maschine, die H' implementiert, kann man Reduktionen konstruieren, die die Entscheidbarkeit anderer unlösbarer Probleme implizieren würden. Da jedoch bekannt ist, dass solche Probleme unlösbar sind (durch Nicht-Existenz einer entscheidungsfähigen Turingmaschine), wird auch die Lösung mittels H' unlogisch.

In Summe zeigen diese Argumente, dass selbst eine hypothetische Entscheidungsmaschine H' nicht in der Lage wäre, das allgemeine Entscheidbarkeitsproblem für Turingmaschinen zu lösen, ohne Widersprüche in der Theorie der Turingmaschinen-Entscheidbarkeit zu erzeugen.

Aufgabe 3)

Betrachte die Problematik der NP-Vollständigkeit, die für die Informatik von zentraler Bedeutung ist. Zu den bekanntesten NP-vollständigen Problemen gehören K-SAT, das Hamiltonkreisproblem, das Handlungsreisendenproblem, das Knotenüberdeckungsproblem und das Unabhängige Mengenproblem. Ein Problem ist NP-vollständig, wenn es in der Klasse NP liegt und jedes Problem in NP polynomiell auf dieses Problem reduziert werden kann. Das Verstehen und Anwenden von Reduktionen ist hierbei ein wesentlicher Bestandteil.

a)

Beweise, dass das Knotenüberdeckungsproblem (Vertex Cover) NP-vollständig ist. Gehe dabei auf die folgenden Punkte ein:

• Zeige, dass Vertex Cover in NP liegt.
• Wende die Reduktion von einem bekannten NP-vollständigen Problem (z.B. 3-SAT) auf Vertex Cover an und beweise die Korrektheit der Reduktion.

Lösung:

Beweis, dass das Knotenüberdeckungsproblem (Vertex Cover) NP-vollständig istUm zu beweisen, dass das Knotenüberdeckungsproblem (Vertex Cover) NP-vollständig ist, müssen zwei wesentliche Bedingungen erfüllt sein:

• Zeigen, dass Vertex Cover in NP liegt.
• Eine polynomielle Reduktion von einem bekannten NP-vollständigen Problem auf Vertex Cover konstruieren und die Korrektheit dieser Reduktion beweisen.
1. Vertex Cover liegt in NP
• Ein Problem liegt in NP, wenn eine Lösung in polynomieller Zeit verifiziert werden kann. Im Fall des Knotenüberdeckungsproblems gilt dies wie folgt:
• Gegeben ein Graph G = (V, E) und eine Zahl k zeigt Vertex Cover, ob es eine Teilmenge von Knoten V' gibt, wobei |V'| ≤ k und jede Kante in E mindestens einen Endpunkt in V' hat.
• Zur Verifikation einer gegebenen Lösung in polynomieller Zeit: Prüfe, ob die Anzahl der Knoten in V' kleiner oder gleich k ist und ob jede Kante in E mindestens einen Endpunkt in V' hat.
Da dieses Verfahren in polynomieller Zeit abgeschlossen werden kann, liegt das Knotenüberdeckungsproblem eindeutig in NP.2. Reduktion von 3-SAT auf Vertex Cover
• Zum Beweis der NP-Vollständigkeit wenden wir eine polynomielle Reduktion vom 3-SAT-Problem (welches NP-vollständig ist) auf Vertex Cover an.
• Schritte der Reduktion:
  1. Gegeben eine 3-CNF-Formel F mit den Klauseln C1, C2, ..., Cm und den Variablen x1, x2, ..., xn.
  2. Konstruiere einen Graph G = (V, E): Für jede Klausel Ci von F (1 ≤ i ≤ m) füge drei Knoten (v1, v2, v3) hinzu, die jeweils durch Kanten ein Dreieck bilden (also {v1, v2}, {v2, v3}, {v3, v1}).
  3. Für jede Variable xj füge zwei Knoten (xj und ¬xj) hinzu und verbinde sie durch eine Kante ({xj, ¬xj}).
  4. Verbinde dann jeden Knoten, der eine Literal in einer Klausel repräsentiert, mit dem entsprechenden Knoten der entsprechenden Variable. Z.B. verbinde einen Knoten von Ci, der xi entspricht, mit dem Knoten xj.
  5. Bestimme k als m + n (jede Klausel erfordert mindestens einen Knoten, jede Variable mindestens einen Knoten).
  6. Behaupte, dass F genau dann erfüllbar ist, wenn G ein Vertex Cover der Größe k hat.
  7. Korrektheit der Reduktion: Wenn F erfüllbar ist, dann gibt es eine wahrheitsgemäße Zuweisung der Variablen, die jede Klausel erfüllt. Wähle für jede Klausel mindestens einen Knoten im Vertex Cover und für jede Variable einen der beiden Knoten (je nachdem, ob sie wahr oder falsch ist). Dadurch wird G so zerlegt, dass jede Kante mindestens einmal abgedeckt ist und die Größe des Covers gleich k ist. Umgekehrt, wenn G ein Vertex Cover der Größe k hat, bedeutet das, dass für jede Klausel mindestens ein Knoten im Cover liegt und jede Variable mindestens einen der beiden Knoten hat, was einer erfüllbaren Wahrheitstabelle entspricht.
Da gezeigt wurde, dass Vertex Cover in NP liegt und eine polynomielle Reduktion von 3-SAT auf Vertex Cover konstruiert wurde, ist das Knotenüberdeckungsproblem NP-vollständig.

b)

Beschreibe das Handlungsreisendenproblem (Traveling Salesman Problem, TSP) und erkläre, warum es NP-vollständig ist. Verwende dazu folgende Schritte:

• Definiere das Problem formal.
• Diskutiere, warum TSP in NP liegt.
• Zeige durch eine Reduktion von einem anderen bekannten NP-vollständigen Problem, dass TSP ebenfalls NP-vollständig ist.

Lösung:

Beschreibung des Handlungsreisendenproblems (Traveling Salesman Problem, TSP) und dessen NP-VollständigkeitUm das Handlungsreisendenproblem (TSP) zu beschreiben und zu erklären, warum es NP-vollständig ist, müssen wir die folgenden Schritte durchgehen:

• Das Problem formell definieren.
• Diskutieren, warum TSP in NP liegt.
• Eine Reduktion von einem anderen bekannten NP-vollständigen Problem auf TSP zeigen.
1. Formelle Definition des Handlungsreisendenproblems (TSP)
• Gegeben sind: Ein vollständiger gewichteter Graph G = (V, E), wobei V die Menge der Knoten und E die Menge der Kanten ist. Jedes Paar von Knoten ist durch genau eine Kante verbunden, und jede Kante hat ein Gewicht (Distanz).
• Frage: Gibt es einen zyklischen Pfad, der jeden Knoten genau einmal besucht und dessen Gesamtkantenlänge kleiner oder gleich einer gegebenen Schranke B ist?
2. Warum liegt TSP in NP?
• Ein Problem liegt in NP, wenn eine Lösung in polynomieller Zeit verifiziert werden kann.
• Bei TSP kann eine Lösung durch folgende Schritte verifiziert werden:
• Gegeben eine Reihenfolge der Knoten (eine Rundreise), überprüfe, ob jede Knotenfolge genau einmal besucht wird und die Rundreise geschlossen ist.
• Berechne die Gesamtlänge der Rundreise und überprüfe, ob sie kleiner oder gleich B ist.
• Da diese Überprüfungen in polynomieller Zeit durchgeführt werden können, liegt TSP in NP.
3. Reduktion von Hamiltonian Cycle Problem (HCP) auf TSP
• Um zu zeigen, dass TSP NP-vollständig ist, müssen wir eine Reduktion von einem bekannten NP-vollständigen Problem, wie dem Hamiltonian Cycle Problem (HCP), auf TSP konstruieren.
• Schritte der Reduktion:
  1. Gegeben ein Graph G = (V, E) des HCP. Wir möchten wissen, ob G einen Hamiltonkreis hat, also einen zyklischen Pfad, der jeden Knoten genau einmal besucht.
  2. Konstruiere den vollständigen Graph G' für das entsprechende TSP wie folgt:
  3. Jeder Knoten in G entspricht einem Knoten in G'.
  4. Setze das Gewicht der Kanten in E' auf 1, wenn die entsprechende Kante in E ist. Setze das Gewicht der Kanten in E', die nicht in E sind, auf eine sehr große Zahl, z.B. 2, um sicherzustellen, dass diese Kanten nicht Teil der optimalen Lösung sind.
  5. Setze die Schranke B auf die Anzahl der Knoten in V.
  6. Behaupte, dass G einen Hamiltonkreis hat, wenn und nur wenn G' eine Rundreise der Länge |V| oder kleiner hat.
  7. Korrektheit der Reduktion:
  8. Wenn G einen Hamiltonkreis hat, kann diese Reihenfolge in G' als Rundreise der Länge |V| verwendet werden, da jede Kante in G' die in G vorhanden ist, das Gewicht 1 hat.
  9. Umgekehrt, wenn es in G' eine Rundreise der Länge |V| oder kleiner gibt, muss diese Rundreise nur Kanten aus E verwenden, die das Gewicht 1 haben, da die anderen Kanten ein Gewicht von mindestens 2 haben und die Gesamtzahl dann größer als |V| wäre. Daher repräsentiert die Rundreise einen Hamiltonkreis in G.
Da gezeigt wurde, dass TSP in NP liegt und dass HCP polynomiell auf TSP reduziert werden kann, ist das Handlungsreisendenproblem (TSP) ebenfalls NP-vollständig.

c)

Beschreibe kurz das Unabhängige Mengenproblem (Independent Set) und beweise seine NP-Vollständigkeit. Dabei solltest du folgende Punkte behandeln:

• Definiere, was ein unabhängiges Set in einem Graphen ist.
• Erkläre, warum das Unabhängige Mengenproblem in der Klasse NP liegt.
• Führe einen Reduktionsbeweis zur NP-Vollständigkeit unter Verwendung eines bekannten NP-vollständigen Problems (z.B. Vertex Cover).

Lösung:

Beweis der NP-Vollständigkeit des Unabhängigen Mengenproblems (Independent Set Problem)Um das Unabhängige Mengenproblem zu beschreiben und seine NP-Vollständigkeit zu beweisen, gehen wir die folgenden Schritte durch:

• Definiere, was ein unabhängiges Set in einem Graphen ist.
• Erkläre, warum das Unabhängige Mengenproblem in der Klasse NP liegt.
• Führe einen Reduktionsbeweis zur NP-Vollständigkeit unter Verwendung eines bekannten NP-vollständigen Problems (z.B. Vertex Cover).
1. Definition eines unabhängigen Sets
• Ein unabhängiges Set in einem Graphen G = (V, E) ist eine Teilmenge von Knoten U ⊆ V, sodass keine zwei Knoten in U durch eine Kante in E verbunden sind.
• Das Unabhängige Mengenproblem fragt, ob es in einem gegebenen Graphen G ein unabhängiges Set der Größe k gibt, d.h. ob es eine Teilmenge U von V gibt, wobei |U| ≥ k ist und U unabhängiges Set ist.
2. Warum liegt das Unabhängige Mengenproblem in der Klasse NP?
• Ein Problem liegt in NP, wenn eine Lösung in polynomieller Zeit verifiziert werden kann.
• Beim Unabhängigen Mengenproblem kann man eine Lösung durch folgende Schritte verifizieren:
• Gegeben eine Teilmenge U von V, überprüfe, ob |U| ≥ k ist.
• Überprüfe, ob keine zwei Knoten in U durch eine Kante verbunden sind, d.h. überprüfe für alle u, v ∈ U, dass (u, v) ∉ E.
• Da diese Überprüfungen in polynomieller Zeit durchgeführt werden können, liegt das Unabhängige Mengenproblem in NP.
3. Reduktionsbeweis zur NP-Vollständigkeit vom Vertex Cover Problem zum Unabhängigen Mengenproblem
• Wir verwenden eine polynomielle Reduktion vom bekannten NP-vollständigen Problem Vertex Cover zum Unabhängigen Mengenproblem:
• Schritte der Reduktion:
  1. Gegeben einen Graphen G = (V, E) und eine Zahl k für das Vertex Cover Problem.
  2. Erzeuge den gleichen Graphen G' = (V, E) für das Unabhängige Mengenproblem, aber wähle eine neue Zahl k' = |V| - k.
  3. Behaupte, dass G ein Vertex Cover der Größe k hat, wenn und nur wenn G' ein unabhängiges Set der Größe k' hat.
  4. Korrektheit der Reduktion:
     • Wenn G ein Vertex Cover der Größe k hat, dann existiert eine Teilmenge C von V mit |C| = k, sodass jede Kante in E mindestens einen Endpunkt in C hat.
     • Die Komplementmenge von C, also V \ C, ist ein unabhängiges Set in G, da keine Kante in E beide Endpunkte in V \ C haben kann.
     • Da |V \ C| = |V| - k = k', hat G' ein unabhängiges Set der Größe k'.
     • Umgekehrt, wenn G' ein unabhängiges Set der Größe k' hat, dann existiert eine Teilmenge U von V mit |U| = k' und keine zwei Knoten in U sind durch eine Kante in E verbunden.
     • Die Komplementmenge von U, also V \ U, ist ein Vertex Cover in G, da jede Kante in E mindestens einen Endpunkt in V \ U haben muss.
     • Da |V \ U| = |V| - k' = k, hat G ein Vertex Cover der Größe k.
Da gezeigt wurde, dass das Unabhängige Mengenproblem in NP liegt und eine polynomielle Reduktion vom Vertex Cover besteht, ist das Unabhängige Mengenproblem NP-vollständig.

Aufgabe 4)

Betrachte die Entscheidungsprobleme SAT und 3-SAT. Es sei bekannt, dass 3-SAT NP-vollständig ist. Zur Erinnerung: SAT (Satisfiability) ist das Problem, zu entscheiden, ob eine gegebene boolesche Formel erfüllbar ist. 3-SAT ist eine Einschränkung von SAT, bei der jede Klausel höchstens drei Literale enthält. Angenommen, Du hast einen Algorithmus, der 3-SAT in polynomialer Zeit lösen kann.

b)

Teil 2Zeige, dass durch die in Teil 1 beschriebene Transformation eine Instanz \textit{x} von SAT genau dann erfüllbar ist, wenn die transformierte Instanz \textit{f(x)} von 3-SAT erfüllbar ist. Verwende dabei formale Argumente und, wenn notwendig, mathematische Notationen, um die Korrektheit der Reduktion darzulegen.

Lösung:

• Kontext der Aufgabe: Es ist bekannt, dass 3-SAT NP-vollständig ist. SAT (Satisfiability) ist das Problem, zu entscheiden, ob eine gegebene boolesche Formel erfüllbar ist. 3-SAT ist eine Einschränkung von SAT, bei der jede Klausel höchstens drei Literale enthält. Angenommen, Du hast einen Algorithmus, der 3-SAT in polynomialer Zeit lösen kann.
Teil 2
• Ziel: Zeige, dass durch die in Teil 1 beschriebene Transformation eine Instanz \(x\) von SAT genau dann erfüllbar ist, wenn die transformierte Instanz \(f(x)\) von 3-SAT erfüllbar ist. Verwende dabei formale Argumente und, wenn notwendig, mathematische Notationen, um die Korrektheit der Reduktion darzulegen.
Formaler Nachweis der Korrektheit:Um die Korrektheit der Transformation nachzuweisen, müssen wir zeigen, dass eine SAT-Instanz \(x\) genau dann erfüllbar ist, wenn die daraus resultierende 3-SAT-Instanz \(f(x)\) erfüllbar ist.
• Richtung 1: SAT zu 3-SATAngenommen, die ursprüngliche SAT-Formel \(x\) ist erfüllbar. Das heißt, es gibt eine Belegung der Variablen, sodass jede Klausel in \(x\) wahr ist. Wir müssen zeigen, dass die transformierte Formel \(f(x)\) ebenfalls erfüllbar ist.Betrachten wir eine Klausel in \(x\) der Form \((x_1 \lor x_2 \lor x_3 \lor \ldots \lor x_k)\) mit \(k > 3\).Durch die in Teil 1 beschriebene Transformation wird diese Klausel in mehrere Klauseln umgewandelt:
  • \((x_1 \lor x_2 \lor y_1)\)
  • \((eg y_1 \lor x_3 \lor y_2)\)
  • \((eg y_2 \lor x_4 \lor y_3)\)
  • ... (für alle Zwischenschritte) ...
  • \((eg y_{k-4} \lor x_{k-2} \lor x_{k-1} \lor x_k)\)
  Da die ursprüngliche Klausel \((x_1 \lor x_2 \lor x_3 \lor \ldots \lor x_k)\) durch eine Belegung der Variablen erfüllbar ist, muss mindestens eines der Literale in der Klausel wahr sein. Schreiben wir die Belegung der neuen Variablen \(y_1, y_2, \ldots, y_{k-3}\) entsprechend:
  • Falls \((x_1 \lor x_2 \lor x_3 \lor \ldots \lor x_k)\) bereits durch ein Literal der ersten Klausel \((x_1 \lor x_2 \lor y_1)\) wahr wird, setzen wir \(y_1\) auf wahr und alle nachfolgenden \(y_j\) ebenfalls auf wahr.
  • Falls nicht, setzen wir \(y_1, y_2, \ldots, y_{k-3}\) so, dass jede Zwischenklausel erfüllt ist.
  Somit ist die transformierte Formel \(f(x)\) erfüllbar.
• Richtung 2: 3-SAT zu SATAngenommen, die transformierte 3-SAT-Formel \(f(x)\) ist erfüllbar. Das bedeutet, es gibt eine Belegung der Variablen (einschließlich der neuen Variablen \(y_1, y_2, \ldots, y_{k-3}\)), sodass jede Klausel in \(f(x)\) wahr ist. Wir müssen zeigen, dass die ursprüngliche SAT-Formel \(x\) ebenfalls erfüllbar ist.Da die Klauseln in \(f(x)\) aus der ursprünglichen Klausel \((x_1 \lor x_2 \lor x_3 \lor \ldots \lor x_k)\) durch Einfügen von \(y_i\)-Variablen gebildet werden, muss die Erfüllung von \(f(x)\) sicherstellen, dass in der ursprünglichen Klausel mindestens ein Literal wahr sein muss. Wir können daher die Werte der neuen Variablen ignorieren und uns nur auf die ursprünglichen Literale konzentrieren:
  • Falls eine neue Variable \(y_i\) wahr ist, setzen wir die entsprechenden \(x_j\)-Werte gemäß der ursprünglichen Klausel so, dass die Erfüllung gewährleistet ist.
  • Da jede Klausel der ursprünglichen Formel als eine Sequenz von 3-Literal-Klauseln in der 3-SAT-Formel dargestellt wird, garantiert die Erfüllung der 3-SAT-Formel auch die Erfüllung der ursprünglichen SAT-Formel.
  Somit ist die ursprüngliche Formel \(x\) erfüllbar, wenn \(f(x)\) erfüllbar ist.
Zusammenfassung:Durch die obige Argumentation haben wir gezeigt, dass eine SAT-Instanz \(x\) genau dann erfüllbar ist, wenn auch die transformierte 3-SAT-Instanz \(f(x)\) erfüllbar ist. Dies belegt formell die Korrektheit der in Teil 1 beschriebenen Transformation.