Polynomzeit-Reduktion:

specific part of [[theo2_VergleichModelleBerechenbarkeit]] [[theo_Komplexitätsklassen]] broad part of [[112.00_anchor_overview]]

Wie auch in der Berechenbarkeitstheorie wollen wir Probleme aufeinander reduzieren, um die Schwierigkeit dieser eventuell vergleichen zu können. Wie auch da muss die Reduktion selbst aber ein einfacher Prozess sein, weil es sonst viel zu schwierig werden könne. Dabei sollte diese in polynomieller Zeit berechenbar sein.

Definition :

Seien $L_{1} \subset Σ_{1}^{*}, L_{2} \subset Σ_{2}^{*}$ zwei Sprachen.

Wir sagen jetzt, dass $L_{1}$ auf $L_{2}$ polynomiell reduzierbar ist, also geschrieben $L_{1} ⪯ L_{2}$ . Wir sprechen davon, wenn wir eine TM $M$ finden können, die in polynomieller Zeit eine Abbildung von $f : Σ_{1}^{*} ⟶ Σ_{2}^{*}$ berechnet, so dass dann gilt: $w \in L_{1} ⟺ f (w) \in L_{2}$

Wir haben es bereits mit folgender Betrachtung gesehen: Clique $⪯_{p}$ Vertex Cover [[theo2_ReduktionenBerechenbarkeitstheorie#grafisches Beispiel durch Clique / Vertex Covers]]

Wir können jetzt auch 3-SAT $p rece q$ Clique polynomiell reduzieren: #nachtragen

3-SAT $⪯$ Clique:

Betrachten wir folgendes 3-SAT Problem notiert / beschrieben mit folgender Formel: $Θ = (a_{1} \lor b_{1} \lor c_{1}) \land (a_{2} \lor b_{2} \lor c_{2}) \land \dots \land (a_{k} \lor b_{k} \lor c_{k})$ , also ein Term mit $k$ Klauseln und höchstens $n = 3 \cdot k$ Literalen / Variablen. WIr können dieses Problem auf einen Graphen transformieren und dann damit auch das k-Clique Problem lösen: Betrachten wir dabei einen Graphen, der für jede Klausel folgend aufgesetzt wird: ![[Pasted image 20230624181654.png]] Dabei entspricht jede Dreiergruppe von Literalen genau einer Dreiergruppe von Knoten. Wir möchten Kanten jetzt passend aufbauen :

nicht innerhalb der Gruppen verknüpfen
nicht zwischen entgegengesetzten Literalen also nicht $x_{1}, \neg x_{1}$
sonst können sie für alle existieren Wir müssen jetzt für jede Knotengruppe mindestens einen wahren Literal haben, damit das Problem gelöst wird.

satz

Diese Konstruktion stellt eine Polynomzeit-Reduktion zwischen 3-SAT und $k$ -Clique dar. Denn Beweis: die ursprüngliche Formel mit der Länge n ist gegeben. unser Graph hat $n$ Knoten und $\leq n^{2}$ Kanten Eine Konstruktion einer Kante benötigt prinzipiell nur das Wissen über die beiden Endknoten und die Klausel, in der dann beide sind. Mit diesem Wissen können wir dann mit einer ungefähren Laufzeit von $n^{2}$ resultieren

SAT $⪯$ 3-SAT :

Sei eine Formel $θ$ in CNF gegeben also ein SAT Problem. Wir möchten diese Formel jetzt so umschreiben, dass eine Instanz von 3-SAT daraus wird. Sei eine Klausel aus $θ$ mit Länge $> 3$ gegeben, und sagen wir weiter $c = l_{1} \lor \dots \lor l_{k}$ . Wir möçhten jetzt neue Variablen einführen: $y_{1}, \dots y_{k - 3}$ Diese werden wir anschließend so anwenden, dass wir die Ursprungsformel anpassen können: $\gamma_{C}:= (l_{1}\lor l_{2}\y_{1}) \land ( )$

scattered-lenity

Polynomzeit-Reduktion:

Definition :

3-SAT ⪯ Clique:

SAT ⪯ 3-SAT :

3-SAT $⪯$ Clique:

SAT $⪯$ 3-SAT :