cards-deck: 100-199_university::111-120_theoretic_cs::112_complexity_theory

$NP$ -Vollständigkeit

Overview

[!Bsp]

Wir hätten gerne ein Problem $NP ∖ P$ –> als ein solches, was womöglich sehr schwer ist und diese Klasse repräsentieren kann / wird.

Würden wir dieses finden können, so könnten wir zeigen, dass $P \neq = NP$ –> Aber das können wir ja nicht, wie in 112.23_Probleme_p_np gesehen haben!

Da wir das scheinbar nicht zeigen können, wäre es dennoch von Vorteil wenn man zeigen kann, dass es bestimmte Probleme gibt, die hoffentlich die “schwersten” sind.

–> Es gibt Probleme in NP, sodass man alle Probleme $\in NP$ auf sie reduzieren kann.

(Das heißt auch), wenn man das Problem lösen könnte, dann würde man alle Problemem $\in NP$ reduzieren können.

Würde man dazu noch einen Algorithmus finden, dann würde folgen $P = NP$

Wir wollen jetzt eine Menge von NP-Problemen, die alle untereinander auf sich abbildbar / reduzierbar sind –> Das heißt, sie sind alle gleich schwer, und man kann das eine in ein anderes konvertieren “reduzieren”.

[!Tip] Äquivalenz durch Reduktion

Wir wollen jetzt zeigen, dass man diese Probleme immer auf ein anderes reduzieren kann. Also etwa SAT auf 3-SAT, aber auch das Clique-Problem etc. –> Somit haben wir eine Kette von Reduktionien, sodass wir von dem einen zum anderen kommen kann und somit nach und nach alle dieser Probleme gleich “reduzieren” können

Wir beginnen dabei mit den Grundlagen, um diese Reduktionen umsetzen zu können.

boolesche Formeln

[!Definition] Boole’sche Formel

Eine Boolesche Formel besteht aus boole’schen Variablen $\in {T r u e, F a l se}$ , die durch drei Operatoren $\land, \lor, \neg$ verknüpft werden können.

Wie definieren wir dann diese boole’sche Formel formal? #card

Formal beschrieben also:

Sei $V$ ein Satz von Variablen.

Ein Literal ist entweder Variable $x_{i} \in V$ oder eine negierte Variable $\neg x_{i}$ - oder auch $\overline{x}$ - Hierbei sind alle Literale auch Formeln –> halt eine minimale Struktur

Wenn $A, B$ Formeln sind, dann sind auch:

$A \land B$ - Konjunktion

$A \lor B$ - Disjunktion

Sei $ϕ : V \to {T r u e, F a l se}$ eine Belegung der Variablen. Dann wird $ϕ$ in der offensichtlichen Weise auf Formeln erweitert.

Ein Beispiel wäre etwa: $x_{1} \lor \neg x_{2} \land x_{3} \lor (x_{5} \land x_{6} \land \neg x_{8})$ ^1720643849153

Erfüllbare Formeln

[!Req] Erfüllbare Formeln

Wann nennen wir eine Formel erfüllbar? Was muss gelten. Wie kann man die Erfüllbarkeit anders darstellen? #card

Es gilt: Eine Boole’sche Formel ist erfüllbar, wenn es eine Belegung der Variablen gibt, sodass die ganze Formel wahr wird.

$x_{1} \land x_{2} \land \neg x_{3}$ ist etwa erfüllbar durch passendes Einsetzen

Nebenbedingung: Jede Formel $F$ defineirt also eine Funktion $s_{f} : {0, 1}^{∣ V ∣} \to {0, 1}$

Das nennen wir dann auch eine boole’sche Funktion –> diese Erfüllbarkeit kann dann als ein Entscheidungsproblem beschrieben werden: $L := {F ∣ \exists Belegung u \in {0, 1}^{∣ V ∣} von V, sodass F (u) = 1}$ ^1720643849163

Konjunktive Normalform - CNF

Wir wollen ferner eine Struktur, eine spezifische Darstellung einer Formel, definieren, welche nur aus Konjunktionen von Oder-Termen, also $(x_{1}, \lor \dots) \land (x_{n} \lor \dots)$ besteht und somit Lösungen für diese finden –> was aber schwer sein wird /ist!.

[!Definition]

Wir wollen eine Klausel als Konjunktive Normalform beschreiben, wenn folgend gilt:

Wie konstruieren / definieren wir die konjunktive Normalform? #card

Sie weist die Form $C_{1} \land C_{2} \land \dots \land_{k}$ Wobei hier $C_{j}$ jeweils eine Klausel ist.

Ein Beispiel wäre etwa: $(x_{1} \lor \neg x_{2}) \land (\neg x_{3} \lor x_{4} \lor x_{6}) \land (\neg x_{1} \lor \neg x_{2})$ ^1720643849167

Folgerung | Darstellbarkeit in CNF

[!Satz]

Wir können jetzt sagen, dass Jede Boole’sche Funktion durch eine CNF-Formel - mit exponentieller Länge - ausgedrückt werden.

Wie können wir das beweisen und als Funktion darstellen, die genau das für eine beliebige Funktion darstellen kann? #card

Sei $f : {0, 1}^{l} \to {0, 1}$ eine beliebige Funktion - nicht notwendigerweise eine boole’sche Formel!

Dann gibt es jetzt eine Boole’sche Formel $ϕ \in CNF$ mit $l$ Variablen und der Länge $\leq l \cdot 2^{l}$ , sodass für alle $u \in {0, 1}^{l}$ folgend gilt: $ϕ (u) = f (u)$ (Also wir geben eine Belegung u ein und sie muss gleich zu der Ursprungsfunktion sein!)

Wir bezeichnen die Länge einer Formel als die Zahl der $\land, \lor$ Zeichen in der formel!

^1720643849170

Beweis zur Umformung:

Wir wollen einen Beweis führen, der uns diese obige Äquivalenz belegen kann.

Idee: Wir betrachten also über ${0, 1}^{l}$ $2^{l}$ viele Belegungen $v$ .

Wir finden für jedes $v$ eine Klausel $c_{v} (u)$ , die nur dann false ist, wenn alle $u = v$
Wir setzen $ϕ (u)$ auf die Konjunktion der $c_{v} (u)$ aller Nullstellen von $f (u)$

Beweis:

Betrachten wir also ein Wort $v \in {0, 1}^{l}$ . Wir konstruieren dann jetzt eine Klausel $c_{v}$ mit $l$ Variablen $u_{1}, \dots, u_{l}$ , sodass folgendes gilt: $c_{v} (u) = {10 falls u \neq = v falls u = v$ Das können wir umsetzen denn für $v = (v_{1}, \dots, v_{l})$ wählen wir dann die Klausel $c_{v} (u) = (a_{1} \lor a_{2} \lor \dots \lor a_{l}), a_{i} = {u_{i} \neg u_{i} falls v_{i} = 0 falls v_{i} = 1$ –> Also wir konstruieren es genauso, dass $\neg c_{v} (u) = ⋀_{i} \neg a_{i}$ Also ist dann $c_{v} (u) = 0$ ist, wenn $u = v$ .

Sei dann jetzt $K := {v \in {0, 1}^{l} ∣ f (v) = 0}$

Dann können wir jetzt eine Formel folgend definieren: $ϕ (u) = v \in K ⋀ c_{v} (u)$ Also ist dann $ϕ \in CNF$

Es gilt dann jetzt folgend auch: $ϕ (u) = 0 ⟺ f (u) = 0$ (was die gewollte Struktur ist!)

wenn $f (u) = 0$ , dann gibt es eine Klausel $c_{v = u} (u)$ in $ϕ$ für $u$ , die 0 ist, denn dann tritt $u = v$ ein ( was ja bei $c_{v} (u) = 0$ ) ist nach Definition
Wenn $ϕ (u) = 0$ , dann ist mindestens eine der Klauseln in $ϕ$ gleich 0. Also $u = v$ für ein v mit $f (v) = 0$

Damit ist die Länge $ϕ \leq l \cdot 2^{l}$ , denn jedes $c_{v}$ hat die Länge $l$ und ferner $∣ K ∣\leq 2^{l}$ !

SAT | Erfüllbarkeitsproblem $\in NP$

Wir möchten jetzt das bekannte SAT-Problem beschreiben - weil wir es auch weiter für den Baum von Karp’s 21 Probleme benötigen!

[!Definition]

betrachten wir eine Boole’sche Formel $F$ in konjunktiver Normalform.

Das SAT-Problem beschreibt jetzt folgendes Entscheidungsproblem: $S A T := {F ∣ F \in CNF \land \exists Belegung \in {0, 1}^{∣ V ∣} sodass F (u) = 1}$ also wir wollen einfach eine gültige Belegung für eine vorliegende Formel in $CNF$ -Form bestimmen.

Wir wissen, dass $S A T \in NP$ ist

Was heißt es, wenn es in NP ist? Wie können wir die Eigenschaft beweisen? #card

Dass es $\in NP$ ist, können wir ja zeigen, indem wir nachweisen, dass es in polynomieller Zeit Zertifizierbar ist, man also für einen Vorschlag prüfen kann, ob er richtig ist oder nicht.

Eine NTM kann einfach alle möglichen $2^{M}$ Belegungen der Variablen ausprobieren! –> Eine Belegung ist ein Zertifikat in $P$ ; wir beschreiben es folgend:

Jede Klausel kann linear schnell zertifiziert werden - sobald eine Variable true ist!

Über alle Klammern in der CNF kann auch linear schnell verifiziert werden –> sobald einmal false auftritt brechen wir ab ( es sind ja Konjunktionen, also müssen alle wahr sein!)

Diese Verifikation ist linear in der Länge der Formel $F$ . –> Wir haben ja schon gesehen, dass die Formel selbst exponentiell lang werden kann, wenn man sie aus einer anderen heraus konstruiert ^1720643849173

k-Sat

Als Variante von SAT möchten wir noch $k - S a t$ einführen:

[!Satz] Definition

Wie definieren wir k-sat? #card

Das $k$ -Sat Problem ist das SAT-Problem, aber so eingeschränkt, dass jede Klausel höchstens $k$ Literale ( also einzelne Variablen) haben darf –> also es gibt maximal $k$ viele disjunktiv verknüpfte Variablen!

Wichtig ist hier vor Allem $3 - S A T$ ! ^1720643849176

Bemerkung | DNF als Alternative

Neben der konjunktien Normalform gibt es auch die disjunktive Normalform, die in der Struktur beinahe gleich ist, nur eine Klausel aus $Ko nj u k t i o n e n$ besteht (also $(x_{1} \land x_{2} \dots)$ ) und die einzelnen Klauseln über Disjunktionen $\lor$ verknüpft sind.

Man kann das gleiche Problem $S A T$ auch mit $F A L$ darstellen: $F A L = F ∣ F \in D NF \land \exists Belegung u \in {0, 1}^{∣ V ∣} : F (u) = 0$

[!Attention] DNF-SAT ist $\in P$

DNF-SAT, also Prüfen, wann eine DNF $= 1$ ist, ist $\in P$ , und sogar in linearer Zeit lösbar.

Dafür schauen wir uns einfach eine Klausel an und setzen die Variablen so, dass sie 1 ergeben –> damit haben wir dann eine Lösung auf der ganzen Disjunktion $1 \lor () \lor () \dots$ gefunden und somit ist das Ergebnis auch $= 1$ !

Polynomialzeit-Reduktion

Wir kennen bereits Reduktionen aus der Berechenbarkeitstheorie, die Problemklassen Charakterisieren und so etwa ein Problem auf ein anderes Problem reduzieren lässt.

Wie auch da möchten wir nun die Komplexitätstheorie Probleme aufeinander reduzieren, um deren Schwierigkeit auf eine Vergleichsebene bringen zu können. Wenn sich also Problem $A$ auf $B$ reduzieren lässt, ist $A$ höchstens so schwer, wie $B$ !

Diese Abbildung / Konstruktion muss hierbei berechenbar sein! –> Also hier in polynomieller Zeit berechenbar sein!

Wir wollen das ferner in einem Ablauf beschreiben und anwenden können!

[!Definition] Polynomzeit-Reduktion

Wir nennen eine Funktion $f : Σ_{*} \to Σ^{*}$ eine in polynomieller Zeit berechenbare Funktion, falls es eine TM $M$ mit $L (M) \in P$ gibt, welche auf Eingabe $w$ mit dem Inhalt $f (w)$ auf dem Band hält.

Was heißt das für die Betrachtung von Zwei Sprachen, wobei wir eine auf die andere reduzieren wollen? #card

Seien jetzt also $L_{1} \subset Σ_{1}^{*}, L_{2} \subset Σ_{2}^{*}$ zwei Sprachen. Wir nennen jetzt $L_{1}$ auf $L_{2}$ polynomiell reduzierbar - in polynomieller Zeit abbildungsreduzierbar - falls es eine in polynomieller Zeit berechenbare Funktion $f : Σ_{1}^{*} - Σ_{2}^{*}$ gibt, sodass folgendes gilt: $> w \in L_{1} ⟺ f (w) \in L_{2} >$

Die Funktion $f$ heißt dann die Polynomialzeit-Reduzierung von $L_{1}$ auf $L_{2}$ . Das schreiben wir folgend mit : $> L_{1} ⪯_{p} L_{2} oder einfach L_{1} ⪯ L_{2} >$

[!Attention] Grundsätzlich ist polynomielle Reduzierbarkeit analog zur Abbildungsreduzierbarkeit, mit der zusätzlichen Anforderung, dass die Abbildung in polynomieller Zeit berechenbar ist! ^1720643849179

Ablauf

[!Tip] Ablauf für eine Polynomialzeit-Reduktion:

Folgende Schritte benötigt es, um eine Polynomialzeit-Reduktion durchzuführen:

Welche vier Schritte brauchen wir hierbei? #card

Erfinde die Abbildungsfunktion $f$

Zeige, dass $f \in P$

Zeige jetzt $W \in L_{1} ⟹ f (w) \in L_{2}$ und auch $W \in / L_{1} ⟹ f (w) \in / L_{2}$

oder wir zeigen die folgenden beiden Aussagen: $w_{1} \in / L_{1} ⟹ f (w) \in / L_{2}$ oder auch $f (w) \in L_{2} ⟹ w \in L_{1}$ ^1720643849183

Das wollen wir unter Anwendung eines Beispiels direkt einsetzen:

Umsetzung | $3 S A T ⪯_{p} C L I Q U E$

Wir wollen zeigen, dass wir obig genannte Probleem reduzieren können. Das heißt, wir können 3-SAT auf das Cliquen-Problem umwandeln / übersetzen.

[!Satz]

Es gilt also $3 S A T ⪯_{p} C L I Q U E$

Wie beweisen wird das? #card

Beweis:

Als Idee möchten wir das 3-SAT Problem so umwandeln, dass man es in einer Instanz der Graphentheorie umwandeln / darstellen kann.

Betrachten wir etwa eine CNF-Formel $Φ$ mit $k$ Klauseln und 3-Literalen pro Klausen (3-SAT), Etwa folgend: $Φ = (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 $n = 3 k$ Literale

Den Beweis wollen wir folgend aufbauen / umsetzen:

Wir konstruieren zunächste eine Polynomialzeit-Abbildung $f$ , welche den String $⟨ G, k ⟩$ konstruiert, sodass dann $G = (V, E)$ ein ungerichterer Graph ist.

Danach zeigen wir jetzt, dass $Φ$ genau dann erfüllbar ist, wenn $G$ eine Clique der Größe $k$ hat –> also $ϕ \in 3 S A T ⟺ G \in k - C L I Q U E$

(der letzte Teil ist meist etwa tricky, je nach Frage / Problem, was gelöst werden muss) ^1720643849186

Wir wollen jetzt einen Graphen konstruieren:

[!Korollar] Fortführung Beweis

Wir konstruieren jetzt den Graphen folgend:

jedem der $n = 3 k$ Literale in $Φ$ wird ein Knoten in $G$ zugeordnet

jede der $k$ 3-Klauseln in $Φ$ wird zu einer Gruppe - genauer einem Tripel von $t_{1}, \dots t_{k}$ - von Knoten

Wir verbinden dann alle (kostet uns $n^{2}$ ) Paare $(v_{i}, v_{j})$ von Knoten in $G$ außer den folgenden

Wenn $v_{i}$ und $v_{j}$ im gleichen Tripel sind (also wir bauen $k$ bipartite Gruppen auf!)

Wenn $v_{i} = x_{l}$ und $v_{j} = \overline{x_{l}}$ (also wir wollen Komplete zueinander nicht verbinden)

Damit können wir etwa folgenden Term zum Graphen machen: $Φ = (x_{1} \lor x_{2} \lor x_{3}) \land (\overline{x_{2}} \lor x_{3} \lor x_{5}) \land (\overline{x_{1}} \lor x_{2} \lor x_{4})$

Jetzt gilt es zu zeigen, dass eine Lösung in beiden Fällen äquivalent ist - und somit auch NP -

Wir zeigen zuerst $Φ$ erfüllbar $⟹$ es gibt eine $k$ -Clique.

Sei jetzt also $Φ$ erfüllbar.

Dann muss in jedem der Tripel $t_{k}$ mindestens ein Literal wahr sein. Wir markieren diesen Literal - falls es mehrere gibt, nehmen wir ein beliebiges einzelnes aus dem Tripel - und betrachten die Menge der markierten Literale.

Diese Menge ist eine $k$ -CLique, denn

sie hat $k$ -Knoten und

sie enthält keine widersprüchlichen Literale –> also alle Knoten sind verbunden ( wie wir in der Konstruktion dargestellt haben!)

Jetzt zeigen wir noch: Es gibt eine k-Clique $⟹$ $Φ$ ist erfüllbar.

Sei dann $C$ eine $k$ -Clique auf $G$ . Dann folgt dafür:

enthält $C$ genau einen Knoten aus allen Tripeln $t_{k}$ , weil der Graph $k - p a r t i t$ ist!

Die Knoten in $C$ entsprechen gleichzeitig erfüllbaren Literalen, nach Konstruktion - wenn sie nicht gleichzeitig erfüllbar wären, dann hätten sie auch keine gemeinsame Kante!

Wenn all diese Literale auf true gesetzt werden, dann ist $Φ$ erfüllt!

Jetzt können wir auch noch zeigen, dass:

$S A T ⪯_{p} 3 S A T$

[!Satz]

Wir wollen also zeigen, dass $S A T ⪯_{p} 3 S A T$ , wir also SAT auf 3SAT reduzieren können!

Wie könnten wir das beweisen/konstruieren? #card

Sei eine $Φ$ in CNF gegeben, dann konstruieren wir in polynomieller Zeit eine neue Formel $Ψ$ , die eine Instanz von $3 S A T$ ist, sodass dann folgt: $Φ erf \overset{u}{¨} llbar ⟺ Ψ erf \overset{u}{¨} llbar$

Das wollen wir in den Schritten machen:

Konstruktion der Abbildung:

Für jede Klausel der form $c = l_{1} \lor \dots \lor l_{k}, k > 3$ bauen wir eine neue Klausel folgend auf:

Wir führen $k - 3$ neue Variablen $y_{1}, \dots, y_{k - 3}$ ein und konstruieren dann das Äquivalent $Ψ_{c} := (l_{1} \lor l_{2} \lor y_{1}) \land (\overline{y_{1}} \lor l_{3} \lor y_{2}) \land \dots \land (\overline{y_{k - 4}} \lor l_{k - 2} \lor y_{k - 3} \land (\overline{y_{k - 3}} \lor l_{k - 1} \lor l_{k})$

(Also wir haben den einen langen Term so zusammengestellt, dass wir immer maximal 2 der Originalen Literale genommen haben und den Rest mit $y$ aufgefüllt haben. Wichtig ist, dass wir $y$ und in der nächsten Klausel $\overline{y}$ verwenden, weil wir somit darauf achten, dass durch ein Setzen von $y$ nicht aus Versehen zwei Klauseln aktiviert werden)

(Es gibt weniger als $n$ solche Klauseln in $Φ$ , und dise Konstruktion macht aus einer Klausel dann $k - 3 < n$ neue Klauseln –> Wir erzeugen also $< n^{2}$ neue Variablen / Klauseln. Die Konstruktion funktioniert in polynomieller Zeit, und mit der Konjunktion bauen wir dann $Ψ$ zusammen)

Wir wollen ferner beweisen, dass es eine Polynomial-Zeit Reduktion ist:

$Ψ$ ist nach Konstruktion eine gültige $3 S A T$ -Instanz - also CNF

Wie oben bemerkt ist die Konstruktion von polynomieller Zeit gewesen!

ist $Φ$ erfüllbar $⟹$ ist $Ψ$ erfüllbar: Sei jetzt $Φ$ erfüllbar, also es gibt eine Belegung der Variablen, die alle Klauseln wahr macht! –> Insbesondere auch eine Klausel $c = l_{1} \lor \dots l_{k}$ mit $k > 3$ Es muss also mindestens ein Literal in $c$ wahr sein! Wit haben $Ψ_{c}$ so konstruiert, dass $Ψ_{c} := (l_{1} \lor l_{2} \lor y_{1}) \land (\overline{y_{1}} \lor l_{3} \lor y_{2}) \land \dots \land (\overline{y_{k - 4}} \lor l_{k - 2} \lor y_{k - 3} \land (\overline{y_{k - 3}} \lor l_{k - 1} \lor l_{k})$ Setzen wir dann dabei $y_{1}, \dots y_{i - 2}$ auf True und ferner $y_{i - 1}, \dots, y_{k - 3}$ auf false –> so erhält jede Klausel mindestens eine wahre Variable, somit ist auch $Ψ$ erfüllbar.

Jetzt noch: $Ψ$ ist erfüllbar $⟹$ $Φ$ ist erfüllbar: Wir betrachten die Konstruktion von $Ψ_{c}$ . In jeder seiner Klauseln ist also mindestens ein Literal wahr. Da $Ψ_{c}$ aus $k - 2$ Klauseln besteht, aber nur $k - 3$ y-Variablen enthält muss mindestens einer der $l_{1}$ Literale true sein ( Also aus der aufgeteilten Klausel $C$ von $Φ$ hat in derr Konstruktion für $Ψ_{c}$ garantiert ein Term ein Wahr und ist aber kein $y$ -Term, den wir ja absichtlich konstruieren, um das zu beeinflussen) –> Somit war diese Variable dafür verantwortlich, dass diese ausgedehnte Klausel erfüllbar ist –> dann muss auch die “condensed version” erfüllbar sein!

^1720643849191

Was wir damit jetzt gezeigt haben:

[!Feedback]

Wir wissen jetzt, dass $S A T ⪯_{p} 3 S A T$

Es gilt aber auch $3 S A T ⪯_{p} S A T$ –> Wie macht man das etwa?

Selbiges, wie obig, gilt auch für $k - S a t$ !

2-SAT funktioniert so nicht und ist tatsächlich auch $\in P$ !

Reduktionen sind Transitiv

[!Satz]

Es gilt: Sei $A ⪯_{p} B$ und $B ⪯_{p} C$ , dann ist auch $A ⪯_{p} C$

Wie beweist man das? Viel wichtiger, was ist bei einer Reduktion, wo das Ziel in P ist? #card

Der Beweis oben ist offensichtlich, weil wir einfach die Information weitergeben können.

Sei jetzt $A ⪯_{p} B$ und $B \in P$ , dann ist hier auch $A \in P$ !

Das beweisen wir folgend:

Sei $M$ die Polynomialzeit TM, die $B$ entscheidet!.

Sei jetzt $f$ die Abbildung welche $A$ auf $B$ reduzieren wird.

Wir konstruieren die TM $N$ , welche $A$ in polynomieller Laufzeit entscheidet folgend:

Auf eine Eingabe $w$ folgt:

Berechne $f (w)$ –> polynomielle Zeit

Starte $M$ auf Input $f (w)$ Gebe aus, was immer $M$ nach polynomieller Zeit ausgibt

Da $f$ eine Reduktion von $A \to B$ ist, haben wir auch $w \in A ⟹ f (w) \in B$ gezeigt, und somit akzeptiert $N$ jeden Input aus A!

Die Laufzeit ist polynomiell, da beide Teilschritte polynomiell sind ^1720643849194

Leicht | Schwer in Komplexität:

Key-Takeaways hieraus sind:

Leicht ist leicht zu zeigen,
aber schwer ist schwer zu zeigen xd

[!Tip]

Mit einer Reduktion kann man jetzt also zeigen, dass bestimmte Probleme “leicht” sind ( $\in P$ ). Um zu zeigen, dass ein Problem $L_{1}$ leicht ist, können wir folgend vorgehen:

Wie würden wir das zeigen? Wie zeigen wir, dass ein Problem schwer ist? #card

Wir zeigen, dass $L_{1} \in P$ , indem wir ein anderes Problem $L_{2}$ , wo wir wissen, dass es $\in P$ ist nehmen und damit reduzieren, also $L_{1} ⪯_{p} L_{2}$ –> Ähnlich, wie bei Reduktionen bei TMs!

Wie zeigen wir, dass etwas schwer ist?

am besten wäre es, wenn wir sagen könnten, dass etwas schwer ist, wennn es nicht in polynomieller Zeit lösbar ist ==> es folgt also $L \in NP ∖ P$ . (Aber das wissen wir nicht, da unklar ist, ob $P \neq = NP$ )

Alternative Lösung :

Wir finden jetzt ein schwerstes Problem $\in NP$ und nehmen das für die Reduktion.

(tatsächlich gibt es einige dieser Art!) ^1720643849197

NP Vollständigkeit

Wir wollen jetzt ebenjenige schwersten Probleme definieren, die wir zuvor angesprochen haben:

[!Definition] NP Vollständigkeit

Wir nennen eine Sprache $L \subset {0, 1}^{*}$ NP-Schwer oder auch $NP - H a r t$ , falls gilt:

Was muss gelten? Wann nennen wir eine Sprache np-vollständig? Wie beschreiben wir die Menge der Np-vollständigen Sprachen? #card

$\forall L^{'} \in NP$ gilt, dass $L^{'} ⪯_{p} L$ –> Also wir können viele verschiedene Probleme $\in NP$ auf dieses Problem reduzieren!

Eine Sprache heißt dann weiter NP-Vollständig, wenn gilt:

$B \in NP$ und weiter

$B$ ist NP-hard

–> Die Menge dieser NP-vollständigen Probleme nennen wir dann NPC - non-deterministically polynomial time complete ^1720643849200

[!Satz]

Es gilt: Falls es eine Sprache $B$ gibt, sodass $B \in NPC$ und $B \in P$ , dann gilt $P = NP$

Warum folgt das? #card

Naja aus der Definition von np-vollständig: Wenn $B \in NPC \land B \in P$ , dann heißt es, dass wir alle Sprachen $L^{'} \in NP$ auf $B$ reduzieren können –> sie sind dann also auch $\in P$ lösbar!

(Das wäre schon cool!) ^1720643849203

Somit folgen auch noch zwei Korollare:

[!Korollar]

Falls $P \neq = NP$ , was gilt dann?

Falls $B \in NPC \land B ⪯_{p} C, C \in NP$ , was folgt dann?

was folgt für beide Aussagen? #card

Falls $P \neq = NP$ , dann gilt $P \cap NPC = \emptyset$

Falls $B \in NPC \land B ⪯_{p} C, C \in NP$ , dann ist auch $C \in NPC$ ! ^1720643849206

NPC Problem finden

Da wir jetzt wissen, dass es solche Probleme geben kann, die NP-vollständig sind und somit jede Sprache sich darauf reduzieren lässt, müssen wir eine solche nur noch finden

Das zu zeigen scheint aber sehr komplex, weil man ja quasi für jede Sprache $\in NP$ eine Aussage treffen müsste!

[!Tip] Meet Cook and Levin

Durch ihren Beweis, haben sie eine Struktur gefunden, wie man jede Sprache $L$ entsprechend in einem SAT-Problem übersetzen kann!

Satz von Cook & Levin

[!Proposition]

Es gilt jetzt $S A T \in NPC$ , also $L ⪯_{p} S A T, \forall L \in P, \in NP$

Was folgt aus dieser Aussage über $NP, P$ ? Ferner, was ist die Idee, um das zu beweisen> #card

Da wir mit $S A T$ jede Sprache darstellen können, folgt dafür erstmal $NP = P$

(Was jetzt noch keien neue Errungenschaft ist, weil wir das schon wussten, die Trennung ist ja eher interessant!)

Beweisidee:

Wir wollen einen Beweis führen, der die $L$ verifizierende $T M_{L}$ passend in ein SAT-Problem übersetzen kann ( Das ist die L verifizierende TM $M$ ! Das heißt also, wir erhalten die Möglichkeit die TM durch Variablen “ersetzen” bzw. darstellen zu können und dann können wir schauen, wie wir eine Lösung des SAT-Problemes finden.

Ferner gibt es für jedes Wort $w \in L$ ein Zertifikat $c$ der Länge $∣ c ∣ \leq p (∣ w ∣)$ , sodass $M$ die eingabe $⟨ w, c ⟩$ akzeptiert und für $w \in / L$ verwirft.

Wir müssen also genau diese Verifikation (eine TM) als boolesche Formel beschreiben können.

Wir wollen jetzt also folgendes zeigen:

[!Idea] Beweis-Idee für Satz von Cook & Levin

Was wir zeigen wollen: Wenn $L \in NP$ , dann gilt $L ⪯_{p} S A T$

Daraus folgen drei Folgerungen für SAT und L, welche? #card

Dann folgt jetzt:

$L \in NP$ -> es gibt also eine nicht-det. Polynomialzeit beschrankte TM $M$ , die L erkennt. Es gibt somit also ein Polyynom $p$ , welches die Zahl der Rechenschritte von $M$ beschränkt!

SAT: ist das Erfüllbarkeitsproblem der Aussagenlogik. Sei $F$ eine boolesche Formel, ist sie erfüllbar? Also gibt es eine Belegung ihrer Variablen, sodass die ganze Formel wahr ist?

$L ⪯_{p} S A T$ : wir müssen eine Konstruktion - also eine Abbildung - finden, sodass $w \in L ⟺ F erf \overset{u}{¨} llbar$ !

Aber das einzige, was wir über $L$ wissen ist, dass $L \in NP$ ist. –> Wir müssen also die TM $M$ konkret durch CNF Formeln simulieren

Dafür ist die Notation einer nicht-deterministischen TM nochmal relevant:

112.13_turing_maschinen_nondeterministisch

Hilfssatz | “Genau-Eine”-Formel

[!Definition]

Als Konzept für die weitere Konstruktion des Beweises

Konstruktion der Formel:

In der Formel wenden wir die “Genau-eins”-Formel an, die also genau 1 ist, wenn nur ein Punkt 1 ist!

Wir können damit immer tracken, welchen Zustand wir gerade haben ( erster Term), der andere Term ist der “Tracker”, wo wir quasi die Position auf dem Band tracken! $R := t = 1 ⋀ p (n) [\in O (∣ Q ∣^{2}) G (z u s t_{t, z_{1}} \dots, z u s t_{t, z_{∣ Q ∣}}), \land \in O ((2 p (n))^{2}) G (p o s_{t, - p (n)} \dots p o s_{t, p (n)}) \land (i = - p (n) ⋀ p (n) \in O (∣ Γ ∣^{2}) G (ban d_{t, i, a_{1}}, \dots, ban d_{t, i, a_{l}}))]$ (Hierbei ist jetzt der erste und letzte Term konstant, nur der mittlere Skaliert –> weil er die Menge des Bandes beschreibt und damit trackt, wo wir uns auf diesem befinden)

wir definieren dann weiter $A$

–> Das ist der Start Der TM und wir haben somit gezeigt, dass sie richtig “starten” / anfangen kann!

Wir wollen jetzt die Übergänge betrachten undauch hier zeigen, dass die CNF, die wir bilden, wahr sein wird!

(erster Term von $U_{1}$ ): für alle Zeitpunkte, liegt unsere TM in einem Zustand $t$ und sie hat den Lesekopf an Stelle $I_{t}$ auf dem Lesekopf und auf dem Band steht der Term $a_{t}$ an der Stelle $i_{t}$ (dann in der großen Klammer folgt): Wir haben einen Übergang zu einem neuen Zustand –> und schreiben ein neues Symbol. das kann in verschiedenen KOnfigurationen ( also einem aktuellen Zustand, der Position des Bandes und vielleicht die Eingabe) auftreten und wir verbindn alle Möglichkeiten durch ein Oder! Dieser Term sieht vielleicht nicht aus, wie etwas in CNF, aber wir wissen, dass man DNF in eine CNF umwandeln kann –> Da wir wissen, wie viele Elemente sich in der DNC befinden, können wir ferner auch konstant umwandeln –> es sind drei Literale pro Klausel und dann wird da nur eine Potenz, die konstant ist, erzeugt!

Beispiele von NP-Problemen

Vertex Cover $\in NPC$

Wir wollen das zeigen, indem wir eine Reduktion von $C L I Q U E ⪯_{p} V ERTEX CO V ER$ aufbauen.

Exemplarisch wollen wir ein Beispiel nennen, wie man von einer Lösung einer Clique zu einem Vertex Cover kommt.

Die Idee ist dabei, wie bei 112.92_ueb12, dass man von dem gegeben Graphen alle Kanten invertiert / vertauscht, also das Komplement bildet.

Anschließend sind alle Knoten, die zuvor in der Clique nicht enthalten waren, dann der minimale vertex cover!

Bildlich also:

Was wir jetzt zeigen müssen, um entsprechend die Reduktion beweisen zu können:

Es gilt zu zeigen: $⟨ G, k ⟩ \in C L I Q U E ⟺ f (⟨ G, k ⟩) = ⟨ G^{'}, k^{'} ⟩ \in V ERTEX CO V ER$

[!Tip] RELEVANT:

Es ist wichitg, dass hier in beiden Seiten argumentiert bzw bewiesen wird, weil es eine Äquivalenz ist, die jeweils gelten muss.

Sei dann jetzt $⟨ G, k ⟩ \in C L I Q U E$ :

Dann hat $G$ eine Clique der Größe $k$ , sodass $\exists V_{1} s u s b e t e q V : ∣ V_{1} = k$ und ferner auch $\forall u, v \in V_{1} : {u, v} \in E$
Im Komplementgraphen - den wir durch das Invertieren der Kanten bilden, $G;$ genannt,gilt dann ferner auch $\forall u, v \in V_{1} : {u, v} \in / E$
Alle Kanten in $G^{'}$ haben also mindestens einen Endknoten in $V ∖ V_{1}$

Ferner möchten wir die anderweitige Betrachtung umsetzen, also Sei $⟨ G^{'}, k^{'} ⟩ \in V ERTEX CO V ER$

Dann hat $G^{'}$ einen Vertex Cover der Größe $k^{'} = ∣ V ∣ - k$ , also $\exists V_{1} b \subseteq V : ∣ V_{1} ∣= k^{'}$ und ferner muss gelten: $\forall {u, v} \in E^{'} : u \in V_{1} \lor v \in V_{1}$
Es gibt also keine Kante in $G^{'}$ sodass beide Endknoten der Kantne in $V ∖ V_{1}$ liegen, also beschrieben mit: $\forall u, v \in (V ∖ V_{1}) : {u, v} \in / E^{'}$
Für den Graphen $G$ gilt dann per Konstruktion von $G^{'} : \forall u, v \in (V ∖ V_{1}) : {u, v} \in E$
Also ist $V ∖ V_{1}$ eine Clique in $G$ der Größe $∣ V ∣ - ∣ V_{1} ∣= ∣ V ∣ - k^{'} = ∣ V ∣ - (∣ V ∣ - k) = k$
und somit haben wir dann zeigen können, dass es auch eine entsprechende Clique kommt

Integer Linear Programming

beschreibt das Lösen eines linearen Ungleichungssystems mit einer bestimmten Form:

Betrachten wir ein Beispiel, dann können wir es in drei Ungleichungen darstellen:

$1 x_{T} + 2 X_{s} 3 X_{T} + 1 X_{S} X_{T}, X_{S} \leq 600 \leq 900 \geq 0$

wir können diese auch entsprechend umformen:

$1 X_{T} + 2 X_{S} \leq 600 2 X_{S} \leq 600 - X_{T} X_{S} \geq 300 - \frac{1}{2} x X_{T}$

Dass das Ganze schon NP-schwer ist, erkennen wir relativ schnell, dass es sehr viel schwieriger wird, wenn man mehr Bedingungen eine Lösung finden möchte und somit skalieren muss.

Ferner können wir auch schon aussagen, dass das $0 - 1$ -Integer-Programming $\in NP$ ist.

#nachtragen

Betrachten wir ein Beispiel dafür:

$u_{1} \lor \neg u_{2} \lor \neg u_{3} ⟹ u_{1} + (1 - u_{2}) + (1 - u_{3}) \geq 1 ⟺ - u_{1} - 1 + u_{2} - 1 + u_{3} \leq - 1 ⟺ - u_{1} + u_{2} + u_{3} \leq 1 100 ∣ \cdot - 1$ Hierbei ist beschreibt die erste Form die Normalform der Ungleichung stehen - die wir oft verwenden, weil viele Algorithmen der linearen Programmierung darauf aufbauen / diese voraussetzen. Dass wir sie auch so umformen können, dass $A \cdot x \leq b$ ist, haben wir anschließend zeigen können –> es ist also möglich!

Subset SUM

wurde auch schon in 112.92_ueb12 betrachtet und bearbeitet.

Wir haben hier schon gezeigt, dass es $\in NP$ ist und eine Reduktion umgesetzt.

Wir wollen jetzt noch umsetzen / zeigen, dass es auch NP-hart / vollständig ist.

Dafür möchten wir $3 - S A T ⪯_{p} S U BSET S U M$ reduzieren:

[!Idea] Idee zur Konstruktion

Wir wollen versuchen die informationen aus der aussagenlogischen Formmel im Dezimalsystem als $m + n$ stellige Zahl dodieren –> also in den Klauseln Informationen zu den Ziffern “verstecken / einbringen”.

Im folgenden nennen wir die ersten m Stellen oft den “vorderen Ziffernblock” und die letzten $n$ Stellen den hinteren Ziffernblock.

Wir wollen das an einem Beispiel zeigen / erklären:

betrachten wir folgendes 3-Sat Problem: $Φ = (x_{1} \lor \neg x_{3} \lor x_{5}) \land (\neg x_{1} \lor x_{5} \lor x_{4}) \land (\neg x_{2} \lor \neg x_{2} \lor \neg x_{5})$ Wir können unter folgender Konstruktion nun die Zahl $b$ definieren / erzeugen:

$b = m 444 n 11 \dots 11$

Und im Beispiel erzeugen wir folgende Zahlen: $v_{1} v_{2} v_{3} v_{4} v_{5} v_{1}^{'} v_{2}^{'} v_{3}^{'} v_{4}^{'} v_{5}^{'} c_{1} c_{2} c_{3} d_{1} d_{2} d_{3} = 100 = 000 = 000 = 010 = 110 = 010 = 002 = 100 = 000 = 001 = 100 = 010 = 001 = 200 = 020 - 002 1000001000001000001000001100000100000100000100001000000000000000000000000000000$ und jetzt wollen wir eine Teilmenge dieser Werte so kombinieren, dass wir damit die Zahl $b$ rekonstruieren / darstellen können:

In unserem Beispiel können wir die 3-SAT Aussage folgend belegen: mit $v_{1}, v_{4}, v_{2}^{'}, v_{3}^{'}$ und damit erhalten wir: $21311111$ und wir müssen es noch auf $444$ erweitern - also den ersten Block!

Dafür können wir jetzt die übrigen Werte $c_{2}, c_{3}, d_{1}, d_{2}$ nehmen, um dann entsprechend zu resultieren!

ein weiteres Beispiel:

$Φ = (x_{1} \lor x_{1} \lor x_{1}) \land (\neg x_{1} \lor \neg x_{1} \lor \neg x_{1})$ und wir können $b = 441$ setzen und die Werte, die wir erzeugen können, sind: $v_{1} c_{1} c_{2} v_{1}^{'} d_{1} d_{2} 301 = 100 = 010 = 031 - 200 = 020$ und wir sehen hier, dass es niemals erfüllt werden kann, weil wir etwa durch nehmen von $v_{1} \land v_{1}^{'}$

scattered-lenity