Computational complexity - Exam

Aufgabe 1)

Gegeben sei die Klasse P, die alle Entscheidungsprobleme umfasst, die von einer deterministischen Turingmaschine in polynomialer Zeit gelöst werden können.

• Ein Problem gehört zur Klasse P, wenn es eine Turingmaschine gibt, die das Problem in Laufzeit O(n^k) für ein konstantes k löst.
• Polynomielle Zeitkomplexität: T(n) = O(n^k) wobei T(n) die Laufzeit und n die Eingabegröße ist.
• Wichtige Eigenschaft: Alle Algorithmen, die ein Problem der Klasse P lösen, sind effizient bzw. praktisch lösbar.

a)

Beweise, dass das Erkennungsproblem für reguläre Sprachen zur Klasse P gehört. Definiere zuerst das Problem und erläutere, warum eine deterministische Turingmaschine, die dieses Problem in polynomialer Zeit löst, existiert.

• Beschreibe die Schritte, die erforderlich sind, um das Erkennungsproblem für reguläre Sprachen mit einer deterministischen Turingmaschine zu lösen.

Lösung:

Das Erkennungsproblem für reguläre Sprachen ist wie folgt definiert:

• Gegeben eine reguläre Sprache L und ein Wort w, entscheide, ob w in L enthalten ist.

Reguläre Sprachen können durch endliche Automaten dargestellt werden. Das bedeutet, dass für jede reguläre Sprache ein endlicher Automat (Deterministischer Endlicher Automat, kurz DEA) existiert, der genau die Wörter akzeptiert, die in der Sprache liegen.

Um das Erkennungsproblem für reguläre Sprachen mit einer deterministischen Turingmaschine in polynomialer Zeit zu lösen, gehen wir wie folgt vor:

• Darstellung des DEA: Die reguläre Sprache L wird durch einen deterministischen endlichen Automaten (DEA) A dargestellt.
• Eingabe: Das gegebene Wort w und die Beschreibung des DEA A (z.B. Zustandsmenge, Eingabealphabet, Übergangsfunktion, Startzustand, Endzustände).
• Überprüfung: Beginne mit dem Startzustand des DEA.
• Schritte: Für jedes Symbol des Wortes w:
• Finde den nächsten Zustand basierend auf der aktuellen Übergangsfunktion des DEA.
• Wechsle in diesen Zustand.
• Akzeptanzentscheidung: Wenn das Ende des Wortes w erreicht ist, überprüfe, ob der aktuelle Zustand ein Endzustand ist:
• Falls ja, akzeptiere w.
• Falls nein, lehne w ab.

Begründung: Ein DEA arbeitet in linearer Zeit bzgl. der Eingabelänge. Das heißt, wenn n die Länge des Wortes w ist, dann benötigt der DEA für jeden Buchstaben von w eine konstante Zeitoperation, um den nächsten Zustand zu bestimmen. Da der DEA die Zustandsübergänge in konstanter Zeit durchführt und die Länge des Wortes w n ist, ist die Gesamtlaufzeit O(n), was polynomiell ist.

Daher gehört das Erkennungsproblem für reguläre Sprachen zur Klasse P, da es von einer deterministischen Turingmaschine in polynomialer Zeit gelöst werden kann.

c)

Betrachte das Problem, ob eine gegebene Zahl eine Primzahl ist. Zeige, dass dieses Problem in der Klasse P liegt, indem Du den Algorithmus von Agrawal, Kayal und Saxena (AKS-Primzahltest) beschreibst.

• Fasse den AKS-Algorithmus kurz zusammen und beweise, dass seine Laufzeit polynomiell ist.
• Berechne die Laufzeit des AKS-Algorithmus und zeige, dass er für jede Eingabegröße in polynomialer Zeit arbeitet.

Lösung:

Um zu zeigen, dass das Problem, ob eine gegebene Zahl eine Primzahl ist, in der Klasse P liegt, verwenden wir den AKS-Primzahltest. Dieser Algorithmus wurde von Agrawal, Kayal und Saxena entwickelt und hat eine polynomiale Laufzeit.

• Problem: Gegeben sei eine Zahl n. Bestimme, ob n eine Primzahl ist.

Wir werden den AKS-Primzahltest zusammenfassen und zeigen, dass seine Laufzeit polynomiell ist:

AKS-Algorithmus

Der AKS-Algorithmus basiert auf der Erkenntnis, dass eine Zahl n dann und nur dann eine Primzahl ist, wenn ein bestimmtes Polynom in Modulo-Arithmetik eine bestimmte Eigenschaft erfüllt. Für eine Zahl n funktioniert der Algorithmus folgendermaßen:

1. Falls n eine Potenz einer natürlichen Zahl ist (d.h., n = a^b für a > 1 und b > 1), dann ist n keine Primzahl.
2. Finde das kleinste r so, dass o_r(n) > (\log n)^2, wobei o_r(n) die Ordnung von n modulo r ist.
3. Wenn 1 < \text{ggT}(a, n) < n für ein a ≤ r, dann ist n keine Primzahl.
4. Falls n ≤ r, dann ist n eine Primzahl.
5. Für a von 1 bis \lfloor \sqrt{\phi(r)} \log n \rfloor prüfen, ob (X+a)^n ≡ X^n + a (\mod X^r - 1, n). Wenn nicht, ist n keine Primzahl.
6. Wenn keiner der obigen Tests n als zusammengesetzt identifiziert, dann ist n eine Primzahl.

Zeitkomplexität des AKS-Algorithmus

Die Zeitkomplexität des AKS-Algorithmus ergibt sich hauptsächlich aus den folgenden Schritten:

• Schritt 1: Das Testen aller Potenzen hat eine Komplexität von \text{O}(\log^2 n).
• Schritt 2: Das Finden von r hat eine Komplexität von \text{O}(\log^5 n).
• Schritt 3: Das Berechnen der größten gemeinsamen Teiler hat eine Komplexität von \text{O}(\log^3 n).
• Schritt 4: Einfache Fallprüfung mit Komplexität \text{O}(\log n).
• Schritt 5: Das Testen der Polynomgleichung hat eine Komplexität von \text{O}(r \log^2 n), was im schlechtesten Fall \text{O}(\log^7 n) ist.

Gesamtlaufzeit: Damit ergibt sich eine Gesamtlaufzeit des AKS-Algorithmus von \text{O}(\log^{7.5} n), wobei \text{n} die Eingabegröße in Bits darstellt. Diese Laufzeit ist polynomiell.

Daher liegt das Problem, ob eine gegebene Zahl eine Primzahl ist, in der Klasse P, da der AKS-Primzahltest dieses Problem in polynomialer Zeit löst.

Aufgabe 2)

Das Problem der NP-VollständigkeitNP-vollständige Probleme sind diejenigen Entscheidungsprobleme, die sowohl in NP liegen als auch NP-schwer sind.

• Ein Problem A ist in NP, wenn eine Lösung in polynomieller Zeit verifiziert werden kann.
• Ein Problem A ist NP-schwer, wenn jedes Problem in NP auf A in polynomieller Zeit reduzierbar ist.
• Falls ein NP-vollständiges Problem in polynomieller Zeit lösbar ist, sind alle Probleme in NP polynomiell lösbar.
• Das berühmte Beispiel ist das SAT-Problem.

a)

(a) Angenommen, es gibt einen Algorithmus, der das SAT-Problem in polynomieller Zeit löst. Was sind die Implikationen für die Klasse NP und die Klasse P? Erkläre ausführlich!

Lösung:

Das Problem der NP-VollständigkeitNP-vollständige Probleme sind diejenigen Entscheidungsprobleme, die sowohl in NP liegen als auch NP-schwer sind.

• Ein Problem A ist in NP, wenn eine Lösung in polynomieller Zeit verifiziert werden kann.
• Ein Problem A ist NP-schwer, wenn jedes Problem in NP auf A in polynomieller Zeit reduzierbar ist.
• Falls ein NP-vollständiges Problem in polynomieller Zeit lösbar ist, sind alle Probleme in NP polynomiell lösbar.
• Das berühmte Beispiel ist das SAT-Problem.

(a) Angenommen, es gibt einen Algorithmus, der das SAT-Problem in polynomieller Zeit löst. Was sind die Implikationen für die Klasse NP und die Klasse P? Erkläre ausführlich!Angenommen, es existiert ein Algorithmus, der das SAT-Problem in polynomieller Zeit löst. Dies hat folgende Implikationen für die Klassen NP und P:

• SAT ist NP-vollständig: Das SAT-Problem ist ein beispielhaftes NP-vollständiges Problem. Das bedeutet, dass jedes Problem in NP in polynomieller Zeit auf das SAT-Problem reduziert werden kann.
• Implikation für alle NP-Probleme: Wenn das SAT-Problem in polynomieller Zeit lösbar ist, bedeutet dies, dass jedes Problem in NP (jedes Probleme, dessen Lösung in polynomieller Zeit verifiziert werden kann) ebenfalls in polynomieller Zeit gelöst werden kann. Das liegt daran, dass wir bekanntlich jedes NP-Problem auf das SAT-Problem in polynomieller Zeit reduzieren können.
• Konsequenz für die Klasse P: Da NP-Probleme in polynomieller Zeit lösbar sind, gehören sie auch zur Klasse P. Somit ist NP eine Teilmenge von P.
• P = NP: Das Vorhandensein eines polynomiellen Algorithmus für das SAT-Problem zeigt, dass es keinen Unterschied zwischen den Klassen P und NP gibt. Dies impliziert, dass P gleich NP ist, also P = NP.
• Auswirkung auf Algorithmen und Komplexitätstheorie: Ein solcher Algorithmus hätte immense Auswirkungen auf viele Bereiche der Informatik und Mathematik, insbesondere auf Algorithmen, Kryptographie und Optimierungsprobleme. Viele Probleme, die für ihre Schwierigkeit bekannt sind, könnten plötzlich effizient gelöst werden.

Zusammenfassend bedeutet das Vorhandensein eines polynomiellen Algorithmus für das SAT-Problem, dass die Klassen P und NP identisch sind, also P = NP, und zahlreiche als schwierig geltende Probleme plötzlich lösbar wären.

b)

(b) Beweise, dass das 3-SAT-Problem NP-vollständig ist. Gehe dabei auf die Reduktion vom allgemeinen SAT-Problem auf das 3-SAT-Problem ein und stelle sicher, dass Deine Argumentation vollständig ist.

Lösung:

Das Problem der NP-VollständigkeitNP-vollständige Probleme sind diejenigen Entscheidungsprobleme, die sowohl in NP liegen als auch NP-schwer sind.

• Ein Problem A ist in NP, wenn eine Lösung in polynomieller Zeit verifiziert werden kann.
• Ein Problem A ist NP-schwer, wenn jedes Problem in NP auf A in polynomieller Zeit reduzierbar ist.
• Falls ein NP-vollständiges Problem in polynomieller Zeit lösbar ist, sind alle Probleme in NP polynomiell lösbar.
• Das berühmte Beispiel ist das SAT-Problem.

Solve the following subexercise:(b) Beweise, dass das 3-SAT-Problem NP-vollständig ist. Gehe dabei auf die Reduktion vom allgemeinen SAT-Problem auf das 3-SAT-Problem ein und stelle sicher, dass Deine Argumentation vollständig ist.Um zu beweisen, dass das 3-SAT-Problem NP-vollständig ist, müssen wir zwei Dinge zeigen:

• 3-SAT liegt in NP, und
• jedes Problem in NP ist polynomiell auf 3-SAT reduzierbar.

1. 3-SAT liegt in NP:Ein Problem liegt in NP, wenn eine Lösung in polynomieller Zeit verifiziert werden kann. Für das 3-SAT-Problem kann eine mögliche Lösung durch Einsetzen der Werte der Variablen in die Klauseln des 3-SAT-Formels überprüft werden. Dies kann in polynomialer Zeit geschehen, da die Anzahl der Klauseln und die Anzahl der Variablen polynomiell ist. Daher liegt 3-SAT in NP.2. Reduktion vom SAT-Problem auf das 3-SAT-Problem:Um zu beweisen, dass 3-SAT NP-vollständig ist, müssen wir zeigen, dass jede boolesche Formel in konjunktiver Normalform (CNF), die ein SAT-Problem darstellt, in polynomieller Zeit auf eine 3-SAT-Formel reduziert werden kann. Der allgemeine Ablauf ist wie folgt:

• Jede CNF-Formel: Eine CNF-Formel besteht aus Klauseln, von denen jede eine Disjunktion von Literalen ist. Klauseln können beliebig viele Literale enthalten.
• Umwandlung zu 3-Literale-Klauseln: Das Ziel der Reduktion ist es, jede Klausel mit mehr als 3 Literalen auf Klauseln mit genau 3 Literalen umzuformen. Betrachte eine Klausel mit mehr als 3 Literalen, z.B. (x1 ∨ x2 ∨ x3 ∨ ... ∨ xk). Wir können sie wie folgt umwandeln:
• Lasse neue Variablen y1, y2, ..., y(k-3) einführen. Die Klausel (x1 ∨ x2 ∨ x3 ∨ ... ∨ xk) wird durch die folgenden Klauseln ersetzt:
• (x1 ∨ x2 ∨ y1)
• (¬y1 ∨ x3 ∨ y2)
• (¬y2 ∨ x4 ∨ y3)
• ...
• (¬y(k-3) ∨ x(k-1) ∨ xk)
• Jede dieser neuen Klauseln enthält genau 3 Literale.
• Die neue Formel mit den zusätzlichen Variablen repräsentiert dieselbe logische Bedingung wie die ursprüngliche Formel. Dies bedeutet, wenn die ursprüngliche Formel erfüllbar war, ist auch die neue Formel erfüllbar und umgekehrt.

Da die Reduktion in polynomialer Zeit durchgeführt werden kann, haben wir hiermit eine polynomielle Reduktion vom allgemeinen SAT-Problem zum 3-SAT-Problem gezeigt.Da das 3-SAT-Problem sowohl in NP liegt als auch NP-schwer ist, folgt daraus, dass das 3-SAT-Problem NP-vollständig ist.

c)

(c) Das Knotenüberdeckungsproblem (Vertex Cover) ist ein weiteres bekanntes NP-vollständiges Problem. Gegeben sei ein ungerichteter Graph G = (V, E) und eine Zahl k. Beschreibe einen polynomiellen Verifikationsalgorithmus für das Knotenüberdeckungsproblem und erkläre, warum dieser Algorithmus zeigt, dass Vertex Cover in NP liegt.

Lösung:

Das Problem der NP-VollständigkeitNP-vollständige Probleme sind diejenigen Entscheidungsprobleme, die sowohl in NP liegen als auch NP-schwer sind.

• Ein Problem A ist in NP, wenn eine Lösung in polynomieller Zeit verifiziert werden kann.
• Ein Problem A ist NP-schwer, wenn jedes Problem in NP auf A in polynomieller Zeit reduzierbar ist.
• Falls ein NP-vollständiges Problem in polynomieller Zeit lösbar ist, sind alle Probleme in NP polynomiell lösbar.
• Das berühmte Beispiel ist das SAT-Problem.

Solve the following subexercise:(c) Das Knotenüberdeckungsproblem (Vertex Cover) ist ein weiteres bekanntes NP-vollständiges Problem. Gegeben sei ein ungerichteter Graph G = (V, E) und eine Zahl k. Beschreibe einen polynomiellen Verifikationsalgorithmus für das Knotenüberdeckungsproblem und erkläre, warum dieser Algorithmus zeigt, dass Vertex Cover in NP liegt.Das Knotenüberdeckungsproblem oder Vertex Cover Problem ist wie folgt definiert: Gegeben sei ein ungerichteter Graph G = (V, E) und eine Zahl k. Die Aufgabe ist zu entscheiden, ob es eine Menge von höchstens k Knoten gibt, die jede Kante im Graphen überdeckt (d.h., jedes Ende einer Kante ist einer dieser Knoten). Ein polynomieller Verifikationsalgorithmus überprüft, ob eine gegebene Lösung tatsächlich eine gültige Knotenüberdeckung ist und dass sie höchstens k Knoten enthält.Polynomieller Verifikationsalgorithmus:

• Eingabe: Ein ungerichteter Graph G = (V, E), eine Menge C von Knoten (|C| ≤ k), und eine Zahl k.
• Verifikation:

1. Prüfen, ob die Menge C höchstens k Knoten enthält. Dies kann in O(1) Zeit geschehen durch einfaches Zählen der Knoten in C und Überprüfen, ob |C| ≤ k.
2. Für jede Kante (u, v) in E, prüfe ob entweder u oder v oder beide in C enthalten sind.Dies bedeutet, wir müssen jede Kante durchgehen und überprüfen, ob mindestens einer ihrer Endknoten in C liegt. Dies kann in O(|E|) Zeit geschehen, da es einen konstanten Aufwand erfordert, um für jede Kante deren Endknoten in der Menge C zu überprüfen, und wir alle Kanten durchgehen müssen.

Wenn beide Prüfungen erfolgreich bestanden werden, dann ist die Menge C eine gültige Knotenüberdeckung von G mit höchstens k Knoten.Warum zeigt dieser Algorithmus, dass Vertex Cover in NP liegt?

• Ein Problem liegt in der Klasse NP, wenn eine vorgeschlagene Lösung in polynomieller Zeit verifiziert werden kann.
• Der oben beschriebene Verifikationsalgorithmus prüft in polynomialer Zeit, ob eine vorgeschlagene Menge von Knoten tatsächlich eine Knotenüberdeckung des Graphen ist und weniger oder gleich k Knoten enthält.
• Insbesondere, die Zeitkomplexität unseres Verifikationsalgorithmus ist O(|E|), was polynomial zur Größe des Eingabegraphen ist (die Anzahl der Kanten ist höchstens quadratisch zur Anzahl der Knoten).

Daher erfüllt der polynomielle Verifikationsalgorithmus die Definition von NP und zeigt somit, dass das Knotenüberdeckungsproblem in NP liegt.

Aufgabe 3)

Polynomzeit-ReduktionenPolynomzeit-Reduktionen, auch bekannt als polynomielle Reduktionen, sind Transformationen eines Problems in ein anderes, wobei die Umwandlung durch einen Algorithmus erfolgt, der in polynomieller Zeit läuft.

• Nützlich zur Klassifizierung von Problemen basierend auf ihrer Schwierigkeit.
• Formell: Ein Problem A ist polynomzeit-reduzierbar auf ein Problem B (A ≤P B), wenn es eine Funktion f gibt, die A auf B in polynomieller Zeit transformiert.
• Mathematisch ausgedrückt: A ≤P B ⇔ ∃ f: {0,1}* → {0,1}* und f ist in P, so dass für alle x gilt: x ∈ A ⇔ f(x) ∈ B
• Wichtig für die Theorie der NP-Vollständigkeit: Ein Problem ist NP-vollständig, wenn es in NP liegt und jedes andere Problem in NP in polynomieller Zeit auf es reduzierbar ist.

a)

Sei A das Erfüllbarkeitsproblem für SAT-Formeln und B das 3-SAT-Problem. Zeige, dass A ≤P B ist, indem Du eine polynomielle Zeit-Funktion f angibst, die eine beliebige SAT-Formel in eine 3-SAT-Formel umwandelt. Beschreibe den Algorithmus zur Umwandlung und erkläre, warum er in polynomieller Zeit arbeitet.

Lösung:

Polynomzeit-ReduktionenPolynomzeit-Reduktionen, auch bekannt als polynomielle Reduktionen, sind Transformationen eines Problems in ein anderes, wobei die Umwandlung durch einen Algorithmus erfolgt, der in polynomieller Zeit läuft.

• Nützlich zur Klassifizierung von Problemen basierend auf ihrer Schwierigkeit.
• Formell: Ein Problem A ist polynomzeit-reduzierbar auf ein Problem B (A ≤P B), wenn es eine Funktion f gibt, die A auf B in polynomieller Zeit transformiert.
• Mathematisch ausgedrückt: A ≤P B ⇔ ∃ f: {0,1}* → {0,1}* und f ist in P, so dass für alle x gilt: x ∈ A ⇔ f(x) ∈ B
• Wichtig für die Theorie der NP-Vollständigkeit: Ein Problem ist NP-vollständig, wenn es in NP liegt und jedes andere Problem in NP in polynomieller Zeit auf es reduzierbar ist.

Lösung der Unteraufgabe:Sei A das Erfüllbarkeitsproblem für SAT-Formeln und B das 3-SAT-Problem. Um zu zeigen, dass A ≤P B ist, definieren wir eine polynomielle Zeit-Funktion f, die eine beliebige SAT-Formel (in konjunktiver Normalform) in eine 3-SAT-Formel umwandelt. Der Algorithmus zur Umwandlung funktioniert wie folgt:

1. Gegeben sei eine SAT-Formel in konjunktiver Normalform (CNF). Das bedeutet, die Formel besteht aus einer Menge von Klauseln, und jede Klausel ist eine Menge von Literalen.
2. Für jede Klausel C, die mehr als 3 Literale enthält, führen wir eine Umwandlung durch. Angenommen, C hat die Form (l1 ∨ l2 ∨ ... ∨ lk) mit k > 3.
3. Wir zerlegen die Klausel C in mehrere Klauseln, so dass jede Klausel höchstens 3 Literale enthält:
   • Ersetze C durch die Klausel (l1 ∨ l2 ∨ y1),
   • füge die Klausel (¬y1 ∨ l3 ∨ y2) hinzu,
   • füge die Klausel (¬y2 ∨ l4 ∨ y3) hinzu,
   • ...
   • füge die Klausel (¬yk-4 ∨ lk-2 ∨ yk-3) hinzu,
   • füge die Klausel (¬yk-3 ∨ lk-1 ∨ lk) hinzu.
   Hierbei sind y1, y2, ..., yk-3 neue Variablen, die nur in diesen Klauseln vorkommen.
4. Durch diese Transformation haben wir jede Klausel mit mehr als 3 Literalen in mehrere Klauseln mit genau 3 Literalen zerlegt.
5. Wiederhole diesen Prozess für alle Klauseln der ursprünglichen Formel.

Dieser Algorithmus arbeitet in polynomieller Zeit, da:

• Jede Klausel, die mehr als 3 Literale enthält, in einer linearen Anzahl zusätzlicher Klauseln zerlegt wird.
• Die Anzahl der neuen Klauseln ist proportional zur Anzahl der Literale in der ursprünglichen Klausel.
• Die Gesamtzahl der Klauseln bleibt also innerhalb eines polynomiellen Faktors der ursprünglichen Anzahl von Klauseln und Literalen.

Aufgrund dieser Überlegungen ist die Laufzeit des Algorithmus durch ein Polynom in der Größe der Eingabeformel beschränkt.Daher ist die Reduktion von SAT auf 3-SAT (A ≤P B) in polynomieller Zeit möglich.

b)

Angenommen, du hast eine Funktion f, die ein Problem C in polynomieller Zeit auf das 3-SAT-Problem reduziert. Wie kannst Du diese Funktion verwenden, um zu zeigen, dass C ebenfalls NP-vollständig ist, vorausgesetzt, dass C in NP liegt?

Lösung:

Polynomzeit-ReduktionenPolynomzeit-Reduktionen, auch bekannt als polynomielle Reduktionen, sind Transformationen eines Problems in ein anderes, wobei die Umwandlung durch einen Algorithmus erfolgt, der in polynomieller Zeit läuft.

• Nützlich zur Klassifizierung von Problemen basierend auf ihrer Schwierigkeit.
• Formell: Ein Problem A ist polynomzeit-reduzierbar auf ein Problem B (A ≤P B), wenn es eine Funktion f gibt, die A auf B in polynomieller Zeit transformiert.
• Mathematisch ausgedrückt: A ≤P B ⇔ ∃ f: {0,1}* → {0,1}* und f ist in P, so dass für alle x gilt: x ∈ A ⇔ f(x) ∈ B
• Wichtig für die Theorie der NP-Vollständigkeit: Ein Problem ist NP-vollständig, wenn es in NP liegt und jedes andere Problem in NP in polynomieller Zeit auf es reduzierbar ist.

Lösung der Unteraufgabe:Angenommen, Du hast eine Funktion f, die ein Problem C in polynomieller Zeit auf das 3-SAT-Problem reduziert. Um zu zeigen, dass C ebenfalls NP-vollständig ist, vorausgesetzt, dass C in NP liegt, folgen wir diesen Schritten:

1. Zeige, dass C in NP liegt:Nach Voraussetzung liegt C in NP. Das bedeutet, dass es einen nichtdeterministischen Algorithmus gibt, der in polynomieller Zeit überprüft, ob eine gegebene Lösung zu C gehört.
2. Zeige, dass ein NP-vollständiges Problem auf C reduziert werden kann:Da 3-SAT ein bekanntes NP-vollständiges Problem ist, müssen wir zeigen, dass ein Problem, das bekanntermaßen NP-vollständig ist, auf C reduzierbar ist. Da wir bereits eine Funktion f haben, die C auf 3-SAT in polynomieller Zeit reduziert, verwenden wir diese Funktion, um zu zeigen, dass wir eine Reduktion in die umgekehrte Richtung konstruieren können.
   • Sei 3-SAT ein NP-vollständiges Problem.
   • Sei f die polynomielle Zeit-Funktion, die C auf 3-SAT reduziert, d.h., für alle x gilt: x ∈ C ⇔ f(x) ∈ 3-SAT.
   • Um zu zeigen, dass C NP-vollständig ist, müssen wir nur nachweisen, dass jedes Problem in NP auf C in polynomieller Zeit reduzierbar ist.
     • Da 3-SAT NP-vollständig ist, kann jedes Problem in NP in polynomieller Zeit auf 3-SAT reduziert werden.
     • Sei g die polynomielle Zeit-Reduktion von einem beliebigen NP-Problem D auf 3-SAT, d.h., für alle y gilt: y ∈ D ⇔ g(y) ∈ 3-SAT.
     • Um D auf C zu reduzieren, betrachte die zusammengesetzte Funktion h = f⁻¹ ∘ g (wenn f bijektiv ist) oder eine geeignete Modifikation:
     • h(y) = f⁻¹(g(y)) ergibt eine Lösung in C.
     • Da sowohl f als auch g polynomiell sind, ist auch h polynomiell.

Da wir gezeigt haben, dass C sowohl in NP liegt als auch dass jedes Problem in NP in polynomieller Zeit auf C reduzierbar ist, folgt daraus, dass C NP-vollständig ist.

c)

Zeige, dass das Clique-Problem NP-vollständig ist, indem Du ein anderes NP-vollständiges Problem wählst und eine polynomielle Reduktion auf das Clique-Problem angibst. Beschreibe alle relevanten Schritte der Reduktion und beweise, dass der Reduktionsalgorithmus in polynomieller Zeit läuft.

Lösung:

Polynomzeit-ReduktionenPolynomzeit-Reduktionen, auch bekannt als polynomielle Reduktionen, sind Transformationen eines Problems in ein anderes, wobei die Umwandlung durch einen Algorithmus erfolgt, der in polynomieller Zeit läuft.

• Nützlich zur Klassifizierung von Problemen basierend auf ihrer Schwierigkeit.
• Formell: Ein Problem A ist polynomzeit-reduzierbar auf ein Problem B (A ≤P B), wenn es eine Funktion f gibt, die A auf B in polynomieller Zeit transformiert.
• Mathematisch ausgedrückt: A ≤P B ⇔ ∃ f: {0,1}* → {0,1}* und f ist in P, so dass für alle x gilt: x ∈ A ⇔ f(x) ∈ B
• Wichtig für die Theorie der NP-Vollständigkeit: Ein Problem ist NP-vollständig, wenn es in NP liegt und jedes andere Problem in NP in polynomieller Zeit auf es reduzierbar ist.

Lösung der Unteraufgabe:Um zu zeigen, dass das Clique-Problem NP-vollständig ist, wählen wir ein bekanntes NP-vollständiges Problem und geben eine polynomielle Reduktion auf das Clique-Problem an. Ein geeignetes Problem ist das 3-SAT-Problem.3-SAT-Problem: Eine boolesche Formel in konjunktiver Normalform (CNF) ist eine 3-SAT-Formel, wenn jede Klausel höchstens 3 Literale enthält. Das 3-SAT-Problem ist zu entscheiden, ob eine gegebene 3-SAT-Formel erfüllbar ist.Hier sind die relevanten Schritte zur Reduktion von 3-SAT auf das Clique-Problem:

1. Eingabe: Eine 3-SAT-Formel \(\text{F}\), bestehend aus einer Menge von Klauseln \(\text{C}_1, \text{C}_2, \text{C}_3, \text{...}, \text{C}_m\) mit jeweils höchstens 3 Literalen.
2. Graphenkonstruktion: Baue einen Graphen \(G\) wie folgt:
   • Für jedes Literal in jeder Klausel füge einen Knoten in \(G\) hinzu. Bezeichne den Knoten, der einem Literal \(l\) in Klausel \(C_i\) entspricht, als \(v_{i,l}\).
   • Verbinde zwei Knoten \(v_{i,l}\) und \(v_{j,l'}\) in \(G\) mit einer Kante, falls sie aus verschiedenen Klauseln stammen \((i ≠ j)\) und die Literale sich nicht gegenseitig ausschließen \((l ≠ eg l')\).
3. Zielclique: Setze die Zielgröße \(k\) der Clique auf die Anzahl der Klauseln in \(F\) (also \(k = m\)).
4. Reduktionskorrektheit: Zeige, dass eine erfüllbare Belegung für die 3-SAT-Formel \(\text{F}\) vorhanden ist, genau dann, wenn der Graph \(G\) eine Clique der Größe \(m\) enthält:
   • Angenommen, \(\text{F}\) ist erfüllbar. Wähle aus jeder Klausel ein Literal, das wahr ist. Die Knoten, die diesen Literalen entsprechen, sind paarweise verbunden (aufgrund der Konstruktion) und bilden somit eine Clique der Größe \(m\).
   • Angenommen, \(G\) hat eine Clique der Größe \(m\). Da die Knoten aus verschiedenen Klauseln stammen und sich nicht gegenseitig ausschließen, gibt es eine erfüllbare Belegung, die die entsprechenden Literale wahr macht.

Laufzeitanalyse: Der Reduktionsalgorithmus läuft in polynomieller Zeit, da die Konstruktion des Graphen \(G\) und das Hinzufügen der Kanten in polynomieller Zeit erfolgen können. Insbesondere ist die Größe des Graphen polynomiell in der Größe der 3-SAT-Formel.

• Das Erstellen der Knoten benötigt \(O(mn)\), wobei \(m\) die Anzahl der Klauseln und \(n\) die maximale Anzahl von Literalen pro Klausel ist (hier maximal 3).
• Das Hinzufügen der Kanten benötigt \(O((mn)^2)\), da man für jedes Paar von Knoten prüft, ob sie verbunden werden können.

Da beide Schritte polynomiell sind, ist der gesamte Algorithmus polynomiell. Daher ist das Clique-Problem NP-vollständig, da es in NP liegt und ein bekanntes NP-vollständiges Problem (in diesem Fall 3-SAT) in polynomieller Zeit darauf reduziert werden kann.

Aufgabe 4)

Log-Raum-ReduktionenLog-Raum-Reduktionen sind Reduktionen zwischen Problemen, die mit logarithmischem Platz (Log-Space) berechnet werden können.

• Verwendet eine log-space transducer, die den Eingabestrang liest und den Ausgabestrang schreibt, während nur O(log n) Speicherplatz verwendet wird.
• Formal: Ein Problem A log-raum-reduziert auf Problem B (A ≤log B), wenn es eine log-space Turingmaschine gibt, die eine Eingabe x in eine Eingabe y für B umwandelt, so dass x in A ist genau dann, wenn y in B ist.
• Viel genutzt in der Komplexitätstheorie zur Charakterisierung von Komplexitätsklassen wie L, NL, P.
• Ermöglicht die Untersuchung der Schwierigkeit von Problemen unter Speicherbeschränkungen.
• Beispiel: Überprüfung der Erreichbarkeit in gerichteten Graphen ist NL-vollständig unter log-raum-Reduktion.

a)

Angenommen, Du hast zwei Probleme A und B, und Du weißt, dass A auf B mittels Log-Raum-Reduktionen reduziert werden kann (A ≤log B). Beschreibe im Detail, wie eine log-space Turingmaschine arbeitet, um diese Reduktion durchzuführen. Gehe dabei auf die Begrenzung des Speicherplatzes und den Ablauf der Verarbeitung ein. Begründe, warum diese Maschine O(log n) Speicherplatz benötigt und wie sie sicherstellt, dass x in A ist, wenn y in B ist.

Lösung:

Beschreibung einer log-space Turingmaschine für die Reduktion von A auf BAngenommen, Du hast zwei Probleme A und B, und Du weißt, dass A auf B mittels Log-Raum-Reduktionen reduziert werden kann. Die Verarbeitungsschritte und Speicherplatzbegrenzungen einer log-space Turingmaschine lassen sich wie folgt detailliert beschreiben:

• Definierte Speicherbeschränkungen: Eine log-space Turingmaschine darf nur O(log n) Speicherplatz verwenden, wobei n die Länge der Eingabe ist. Das bedeutet, dass der verfügbare Speicherplatz nur logarithmisch zur Eingabelänge wächst.
• Struktur der log-space Turingmaschine: Der Speicherplatz wird hauptsächlich für den Zähler und Zeiger verwendet, um Positionen in der Eingabe und Ausgabe zu verwalten. Diese Variablen benötigen nur O(log n) Bits, um Indizes bis zur maximalen Länge der Eingabe zu speichern.
• Arbeitsweise der log-space Turingmaschine:

• Die Maschine liest die Eingabe x und schreibt die entsprechende Ausgabe y.
• Der Speicherplatz wird verwendet, um den aktuellen Zustand und die Position in der Eingabe zu notieren.
• Jede Position der Eingabe wird einzeln eingelesen, und basierend auf dem aktuellen Zustand und der Position wird die jeweilige Position der Ausgabe geschrieben.
• Die Maschine wandelt x in y um, ohne die gesamte Eingabe oder Ausgabe gleichzeitig im Speicher zu halten.
• Stattdessen hält die Maschine nur die aktuellen Zustände, Positionen und notwendige Zwischenberechnungen im Speicher.

• Warum O(log n) Speicherplatz ausreichend ist:
  • Die log-space Turingmaschine benötigt den Speicher hauptsächlich für die Verwaltung und Indizierung der Eingabe und Ausgabe.
  • Da der Speicherbedarf nur logarithmisch zur Eingabelänge wächst, reicht dieser Speicherplatz aus, um Positionen und Zustände effizient zu verwalten.
  • Häufig werden Pointer verwendet, um bestimmte Abschnitte der Eingabe wiederholt zu lesen oder zu bearbeiten, ohne sie ständig im Speicher zu behalten.
• Sicherung der Relation x in A <=> y in B:
  • Die log-space Turingmaschine transformiert x in y so, dass die Beziehung zwischen den beiden Problemen erhalten bleibt.
  • Falls x in A ist, stellt die Maschine sicher, dass die berechnete Ausgabe y in B ist, indem sie die Transformation gemäß der Reduktionsregeln durchführt.
  • Umgekehrt bedeutet es auch, dass wenn y in B ist, die ursprüngliche Eingabe x in A liegt.
  • Diese ersten Schritte stellen sicher, dass die Reduktion korrekt und vollständig ist, indem sie die definierte Transformation korrekt und innerhalb der Speicherplatzbeschränkungen ausführen.

b)

Erkläre, warum die Überprüfung der Erreichbarkeit in gerichteten Graphen NL-vollständig unter Log-Raum-Reduktionen ist. Skizziere dabei einen log-space Algorithmus zur Reduktion eines anderen Problems in NL auf das Erreichbarkeitsproblem. Erläutere dabei auch die Eigenschaften, die ein Problem erfüllen muss, um als NL-vollständig zu gelten.

Lösung:

Erklärung der NL-Vollständigkeit des Erreichbarkeitsproblems in gerichteten GraphenDas Erreichbarkeitsproblem in gerichteten Graphen, auch als Graph Reachability Problem bekannt, ist ein entscheidendes Problem in der Komplexitätstheorie und zeigt die NL-Vollständigkeit unter Log-Raum-Reduktionen aus folgenden Gründen:

• Definition von NL: Die Klasse NL (Nondeterministic Logarithmic-Space) umfasst alle Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine unter Verwendung von O(log n) Speicherplatz gelöst werden können.
• NL-Vollständigkeit: Ein Problem ist NL-vollständig, wenn es in NL liegt und jedes andere Problem in NL auf es unter Verwendung einer log-space Reduktion reduziert werden kann.
• Erreichbarkeitsproblem: Das Erreichbarkeitsproblem prüft, ob es in einem gerichteten Graphen einen Pfad von einem Startknoten zu einem Zielknoten gibt.

Eigenschaften eines NL-vollständigen Problems:

• Es muss in NL liegen: Das bedeutet, dass es von einer nichtdeterministischen Turingmaschine mit O(log n) Speicherplatz entschieden werden kann.
• Jedes Problem in NL muss log-raum-reduzierbar auf dieses Problem sein.

Das Graph Reachability Problem erfüllt beide Eigenschaften:

• Es ist in NL, weil wir mit einer nichtdeterministischen Turingmaschine mit O(log n) Speicherplatz überprüfen können, ob ein Pfad zwischen zwei Knoten existiert.
• Es lässt sich zeigen, dass jedes Problem in NL log-raum-reduzierbar auf das Erreichbarkeitsproblem ist, indem man einen log-space Algorithmus zur Reduktion verwendet.

Log-Space Algorithmus zur Reduktion eines Problems in NL auf das Erreichbarkeitsproblem

• Angenommen, wir haben ein Problem P, das in NL liegt. Für dieses Problem existiert also eine nichtdeterministische Turingmaschine, die P in logarithmischer Raumkomplexität lösen kann.
• Wir müssen nun zeigen, wie wir dieses Problem P auf das Erreichbarkeitsproblem in gerichteten Graphen reduzieren können.
• Der Schlüssel liegt darin, den Berechnungsprozess der Turingmaschine für P in einen gerichteten Graphen zu kodieren. Jeder Zustand der Turingmaschine kann als Knoten im Graphen betrachtet werden.
• Ein Übergang von einem Zustand zum nächsten in der Turingmaschine entspricht einer gerichteten Kante im Graphen.
• Der Startzustand der Turingmaschine wird zum Startknoten, und ein akzeptierender Endzustand wird zum Zielknoten im Graphen.
• Wir erstellen also einen gerichteten Graphen, der die Berechnung der Turingmaschine simuliert. Das bedeutet, dass es im Graphen einen Pfad vom Startknoten zum Zielknoten gibt, genau dann, wenn der Eingabewert x zur Sprache von P gehört.
• Dieser Graph kann innerhalb von O(log n) Speicherplatz erzeugt und verwaltet werden, da die Turingmaschine nur O(log n) Speicherplatz benötigt.
• Damit haben wir gezeigt, dass jedes Problem in NL log-raum-reduzierbar auf das Erreichbarkeitsproblem in gerichteten Graphen ist.