Abbildungen - Reduktionen in der Berechenbarkeitstheorie:

specific part of [[theo2_SprachenEntscheidbarkeit]] broad part of [[112.00_anchor_overview]]

Ziele von Reduktionen:

Angenommen wir wollen ein Problem $P_{1}$ lösen. Was wäre ein Ansatz dieses zu Lösen im Kontext von Reduktion? #card Wir können es für die Reduktion in ein kleineres Problem $P_{2}$ reduzieren. also $P_{1} \subseteq P_{2}$

Wir möchten damit erzielen, dass wir Aussagen über die Berechenbarkeit einer Sprache auf eine andere übertragen können: welche zwei Eigenschaften können wir daraus ableiten? Wichtig! #card

Falls $P_{2}$ leicht ist, erhalten wir eine leichte Lösung für $P_{1}$
Falls $P_{1}$ schwer ist, dann ist vermutlich auch $P_{2}$ schwer.

Definition von Reduktionen:

Sei eine Sprache $L_{1} \subset Σ_{1}^{*}$ und eine weitere Sprache $L_{2} \subset Σ_{2}^{*}$ Wir beschreiben, dass die Sprache $L_{1}$ auf die Sprache $L_{2}$ Abbildungs-reduzierbar ist, wenn gilt: :: Es gibt eine Turing-berechenbare Funktion $f : Σ_{1}^{*} ⟶ Σ_{2}^{*}$ , so dass für eine beliebiges Wort $w \in Σ_{1}^{*}$ gilt: $w \in L_{1} ⟺ f (w) \in L_{2}$

Sofern gilt $w \in L_{1} ⟺ f (w) \in L_{2}$ , was beschreiben wir dann mit f? #card Wir bezeichnen dann die Funktion $f$ als eine Reduktion von $L_{1}$ auf $L_{2}$ Wir notieren sie folgend mit: $L_{1} ⪯_{m} L_{2}$ wobei m als Indikator für mapping reduction steht.

Jede Reduktion muss quasi in beide Richtungen $\Leftarrow \land \Rightarrow$ stimmen, sonst ist es keine valide Reduktion! Wir verlieren ja sonst eventuell Informationen, wie es bei [[netsec_HashFunctions|Hash Functions]] etwa der Fall ist

grafisches Beispiel durch Clique / Vertex Covers

Haben wir zuvor auch schon in Algo betrachtet [[111.99_algo_ProblemComplexity#Example ==Independent set –> clique==|Cliques]] Betrachten wir das Problem von k-Cliques: Sei dafür $G = (V, E)$ ein ungerichteter Graph und $k \in N$ . Eine Teilmenge $V^{'} s u b se t V$ heißt dann Clique, falls :: $V^{'}$ im Graph vollständig miteinander / untereinander verbunden ist. Es müssen also alle Punkte der Clique miteinander direkt verbunden sein. ![[Pasted image 20230523130329.png]] Wir wollen jetzt entscheiden, ob es eine Clique der Größe K im Graph gibt, oder nicht.

Wir können dieses Problem reduzieren, indem wir uns das Vertex Cover anschauen und später verwenden, um darauf auf die Clique-Konstruktion zu schließen.

Vertex Cover:

Sei ein ungerichteter Graph $G = (V, E), k \in N$ gegeben. Weiter nennen wir jetzt die Teilmenge $V^{'} \subset V$ ein Vertex Cover, wenn wir mit dieser Selection von Knoten jede Kante des Graphes mit mindestens einem Endpunkt in $V^{'}$ betrachten können. Folgende Darstellung gibt das Prinzip nochmal wieder. ![[Pasted image 20230523143833.png]] Auch dafür existiert ein Problem:

Gibt es ein Vertex Cover mit $k$ vielen Knoten in unserem Graph ?

Reduktion von Clique auf Vertex Cover:

Unter vorheriger Betrachtung können wir womöglich das Clique-Problem auf ein Vertex Cover-Problem reduzieren.

Dafür sei $G$ der gegebene Graph und $k \in N$ Wir können jetzt einen neuen Graphen definieren, welcher genau das Complement des gegebenen Graphen bildet. Wir notieren ihn mit $G^{\sim}$ und weiter wählen wir nun auch ein $k^{\sim}$ sodass gilt: $G$ hat eine k-clique $⟺ G^{\sim}$ hat einen $k^{\sim}$ -Vertex-Cover.

Wir definieren $G^{\sim}$ dabei als das Komplement von G:

es hat die gleiche Menge Knoten
es hat all die Kanten zwischen Knoten, die G nicht hat.

Folgerung der Reduktion:

Wir behaupten unter dieser Betrachtung:

Die Reduktion ist berechenbar

Und beweisen es mit: Die Reduktion $f$ transformiert den Graphen $G$ in den Graphen $G^{\sim}$ . Wir können offentsichtlich eine TM konstruieren, die die Eingabe von G und k so verarbeitet, dass sie mit der Ausgabe $G^{\sim}, k^{\sim}$ resultiert. –> wie ist nicht relevant, wir wissen, dass es möglich ist xd

Weiterhin behaupten wir auch: G hat eine Clique der Größe $k ⟺ G^{\sim}$ hat einen Vertex Cover der Größe $n - k$ wobei $n = ∣ V ∣$ –> also wir definieren ein Vertex-Cover mit $k^{\sim}$ Knoten.

Da es ein sehr spezifisches Anwendungsbeispiel ist,besteht unter Umständen das Problem, dass es keine Sprache beschreibt. Wenn wir jedoch bedenken, dass unser Beispiel auf n viele Eingaben übertragen und somit angewandt werden kann, können wir das Problem schon auch aus der_Sicht_ einer Sprache betrachten, denn am Ende ist das Paradigma der Übersetzung / Reuktion das selbige. Bildlich betrachtet: ![[Pasted image 20230523144719.png]] Auch diese Aussage kann man beweisen, werde ich in diesem Satz aber weglassen, weil dieser Beweise nicht allzu wichtig ist und eher zu [[111.00_anchor]] gehört.

Wir können schlussendlich folgern:

Wir wollen eine TM bauen, die das $k$ -Clique Problem lösen kann.
Wir starten mit einer Instanz $(G, k)$ des Problemes einer $k$ -Clique.
Wir transformieren diese Instanz auf eine neue, die die Charakteristika eines $k - V er t e x - C o v ers$ -Problem aufweist. Diese Transformation $f$ können wir durch eine weitere TM berechnen.
Wir können jetzt eine TM des $k$ -Vertext-Covers-Problem auf $f (G, k) = (G^{\sim}, n - k)$ anwenden.
Deren Ja/Nein-Antworten stimmen dann auch für das ursprüngliche $k$ -Clique Problem überein, wie wir es zuvor gezeigt und bewiesen haben!

Gründe für Reduktionen $L_{1} ⪯ L_{2}$ :

Folglich können wir mit dieser Betrachtung und Reduktion wichtige Schlüsse über Sprachen treffen: Falls $L_{1} ⪯ L_{2}$ dann gilt: welche zwei Aussagen können wir mit einer Reduktion beschreiben? #card

Falls $L_{2}$ (semi) entscheidbar ist, dann ist auch $L_{1}$ entscheidbar
Falls $L_{1}$ nicht (semi-)entscheidbar ist, dann ist auch $L_{2}$ nicht (semi-entscheidbar)
Falls $L_{2}$ (semi) entscheidbar ist, dann ist auch $L_{1}$ entscheidbar warum können wir darauf schließen? #card

Denn wir können ja das erste Problem auf das zweite abbilden / reduzieren Und wenn wir das erste darauf reduzieren können, gleichzeitig das einfachere Problem der Zielraum ist, dann wird auch unser erster Raum leicht sein, denn wir können ihn ja auf den leichteren Raum reduzieren
Falls $L_{1}$ nicht (semi-)entscheidbar ist, dann ist auch $L_{2}$ nicht (semi-entscheidbar) warum ist diese Aussage möglich? #card

Wenn wir nun $L_{1}$ nicht entscheiden können, aber es dennoch mit einer Funktion auf $L_{2}$ reduzieren können, dann muss $L_{2}$ auch nicht entscheidbar sein, weil es ja weiterhin schwer ist!

Beweis der Aussage 1:

Falls $L_{2}$ (semi) entscheidbar ist, dann ist auch $L_{1}$ entscheidbar Sei $L_{2}$ (semi-)entscheidbar, also es gibt eine TM $M_{2}$ , die die Sprache (semi-)entscheidet. unter dieser prämisse, wie können wir jetzt darauf schließen, dass auch $L_{1}$ entscheidbar ist ? #card Dann bauen wir jetzt auch eine TM $M_{1}$ die $L_{1}$ (semi-)entscheidet. Bei der Eingabe von $w$ wendet $M_{1}$ zunächst die TM $F$ an, welche die Reduktion von $L_{1}$ auf $L_{2}$ umsetzt. Weiter können wir die Ausgabe von $F$ auf $M_{2}$ anwenden. Nach unserer Definition sollte $M_{2}$ dann das richtige Ergebnis liefern. ==> wir wissen also, dass beide entscheidbar sind!. ![[Pasted image 20230523131413.png]]

Beweis der Aussage 2:

Falls $L_{1}$ nicht (semi-)entscheidbar ist, dann ist auch $L_{2}$ nicht (semi-entscheidbar) Angenommen $L_{2}$ ist (semi-)entscheidbar wie würden wir mit diesem Zustand weiter darauf schließen, dass $L_{1}$ auch nicht entscheidbar ist? Wir starten nun mit der Instanz von $L_{1}$ und bauen die TM $M_{1}$ auf. Weiterhin wissen wir jetzt, dass $M_{1}$ auch (semi)-entscheidbar. Dann entscheidet $M_{1}$ $L_{1}$ aber auch $L_{2}$ , was ein Widerspruch bildet!

Andere Richtungen der Reduktionen gelten nicht:

Sei gegeben: $L_{1} ⪯ L_{2}$ wobei $L_{2}$ nicht entscheidbar ist. Können wir etwas für $L_{1}$ folgern? #card Nein, denn wir wissen dann nur, dass das erste Problem nicht gelöst werden kann, indem wir es auf Problem 2 reduzieren –> denn dann ist es auch nicht mehr entscheidbar. Wir wissen auch nicht, ob es einen anderen Weg gibt, mit dem man das Problem dann vielleicht doch lösen kann

Als weiteres Beispiel können wir noch betrachten:

Sei gegeben:

Sei $L_{1} ⪯ L_{2}$ und $L_{1}$ entscheidbar. Was folgt jetzt für $L_{2}$ ? #card Nichts , denn um die Reduktion zum Lösen von Problem 2 zu benutzen, müssten wir die Umkehrabbildung bauen –> um so eventeull eine Reduktion von Problem 2 auf Problem 1 erhalten zu können. Es besteht aber auch die Möglichkeit, dass es Instanzen von Problem 2 gibt, die nie durch eine Reduktion getroffen werden könnten, also wir würden den Zustand und die Menge der Instanzen gar nicht abdecken. Bildlich heißt das: ![[Pasted image 20230523145805.png]]

Mit dieser Betrachtung können wir uns jetzt viel wichtigere Probleme anschauen. So auch das [[theo2_Halteproblem|Halteproblem]] was uns aussagt, dass man manche Probleme niemals richtig lösen kann!

scattered-lenity