<< Inhaltsverzeichniszur Kursübersicht
<< Kapitel 9.3Kapitel 9.5 >>

9.4 Viele Beispiele aus NP

Problem 9.4.1 (3-Colorability). Gegeben ein Graph $G= (V,E)$, gibt es eine Färbung $c : V \rightarrow \{1,2,3\}$ mit

$$ \begin{align*} \forall\ \{u,v\} \in E: \ c(u) \ne c(v) \ ? \end{align*} $$
Der Peterson-Graph ist 3-färbbar.
Dieser Graph ist nicht 3-färbbar

Wir müssen nun eine Zertifikatmaschine mit polynomieller Laufzeit angeben. Um uns nicht in technischen Details zu verlieren, werden wir einfach einen Algorithmus angeben, der zwei Inputs entgegennimmt: den Graphen $G$ (im Turingmaschinenkontext also das Eingabewort $x$) und ein Zertifikat. Hier ist unser Code:

Beobachtung 9.4.2 3-Colorability ist in NP.

Beweis. Wir müssen nun eine Zertifikatmaschine mit polynomieller Laufzeit angeben. Um uns nicht in technischen Details zu verlieren, werden wir einfach einen Algorithmus angeben, der zwei Inputs entgegennimmt: den Graphen $G$ (im Turingmaschinenkontext also das Eingabewort $x$) und ein Zertifikat. Hier ist unser Code: 

def is_3_coloring(graph, c):
    (V,E) = graph
    for (u,v) in E:
    if c[u] == c[v]:
    return False
    if c[u] not in [1,2,3] or c[v] not in [1,2,3]:
        return False
    return True

Falls nun $G$ $3$-färbbar ist, wenn es also eine solche Färbung $c: V \rightarrow \{1,2,3\}$ gibt, dann wird obiger Algorithmus is_3_coloring(graph,c) auch True ausgeben. Falls er für ein $c$ True ausgibt, dann ist $c$ tatsächlich eine gültige 3-Färbung und $G$ ist $3$ -färbbar.A\(\square\)

Das obige Beispiel verdeutlicht die Essenz der Klasse NP: es ist nicht klar, wie wir einen effizienten Algorithmus für 3-Colorabilityschreiben können; aber überprüfen, ob eine gegebene Färbung eine 3-Färbung von $G$ ist, das ist einfach.

Übungsaufgabe 9.4.1 (CNF-Satisfiability). Gegeben eine Formel $F$ in konjunktiver Normalform. Gibt es eine Belegung der Variablen, so dass $F$ zu True wird?

Auch hier können wir eine einfache Prüf-Funktion schreiben, die eine Formel $F$ und eine Belegung $\alpha$ entgegennimmt, dann jede Klausel auswertet und schaut, ob immer True rauskommt. Somit gilt: auchCNF-Satisfiability ist in NP.

Problem 9.4.3 (Subset Sum). Gegeben eine Liste $p_1, \dots, p_n \in \N$ von "Preisen" und ein "Guthaben" $g \in \N$, gibt es eine Menge $I \subseteq [n]$ mit

$$ \begin{align*} \sum_{i \in I} p_i = g \ ? \end{align*} $$

Dies ist ebenfalls in NP.

Finden versus Entscheiden

Sei $G = (V,E)$ ein Graph. Eine Menge $I \subseteq V$ heißt unabhängig, wenn es keine Kante $\{u,v\} \in E$ gibt mit $u,v \in I$.

Problem 9.4.4 Gegeben ein Graph $G=(V,E)$ und eine Zahl $k$ . Finde eine unabhängige Menge in $I$ in $G$ mit $|I| \geq k$, falls es eine solche gibt.

Ist dies in NP? Schon syntaktisch nicht! Es ist ja gar kein Entscheidungsproblem. Wir können aber eine Entscheidungsvariante definieren:

Problem 9.4.5 (Independent Set) Gegeben ein Graph $G=(V,E)$ und eine Zahl $k$. Gibt es eine unabhängige Menge in $I$ in $G$ mit $|I| \geq k$?

Das Entscheidungsproblem Independent Setist offensichtlich in NP. Als Zertifikat kommt z.B. einfach die Menge $I$ in Frage. Für alle Entscheidungsprobleme, die wir oben als Beispiele aufgelistet haben, kann man ganz natürlich das zugehörige Suchproblem definieren: gegeben ein Graph, finde eine 3-Färbung (falls es sie gibt); gegeben eine CNF-Formel, finde eine erfüllende Belegung (falls es sie gibt); gegeben ein Instanz von Subset Sum, finde eine Menge $I$ mit $\sum_{i \in I} p_i = g$.

Übungsaufgabe 9.4.2 Zeigen Sie für folgende Probleme, dass wir, falls wir einen effizienten Algorithmus dafür haben, dann auch einen effizienten Algorithmus schreiben können, der das entsprechende Objekt findet, falls es denn existiert!

Dies geht nicht immer! Erinnern Sie sich an Primes. Der Agrawal–Kayal–Saxena-Algorithmus lässt uns entscheiden, ob eine gegebene Zahl $n$ prim ist; also auch, ob $n$ zusammengesetzt ist; allerdings geht daraus kein Algorithmus hervor, der einen Faktor auch findet. Wo wir gerade beim Faktorisieren sind: das Problem gegeben eine Zahl $X \in \N$, zerlege sie in ihre Primfaktoren ist ja kein Entscheidungsproblem. Können wir ein "entsprechendes" Entscheidungsproblem formulieren? Es sollte gelten: wenn wir das Entscheidungsproblem lösen können, dann auch das Suchproblem. Wie wir gesehen haben, ist Primes bzw.NonPrimesnicht das entsprechende Entscheidungsproblem, weil es uns nicht erlaubt, den Faktor auch zu finden.

Problem 9.4.6 (Small Factor) Gegeben eine Zahl $X \in \N$, binär codiert als $x \in \{0,1\}^n$, und eine Zahl $K \in \N$: gibt es einen echten Teiler $Z$ von $\N$ mit $Z \leq K$?

Übungsaufgabe 9.4.3 Zeigen Sie: wenn man Small Factor effizient lösen kann, dann kann man auch die Primzahlfaktorisierung von $X$ effizient finden. Hinweis: Effizient heißt in diesem Zusammenhang polynomiell in der Anzahl der Bits. Der Algorithmus probiere alle kleineren Zahlen aus, ob sie $X$ teilen, ist nicht effizient!

Das Entscheidungsproblem Small Factor ist offensichtlich in NP: das Zertifikat $z$ ist jener Faktor (so er denn existiert), und die Zertifikatmaschine $M$ muss nun $z$ mit $K$ multiplizieren und schauen, ob auch $X$ herauskommt. Nicht so offensichtlich jedoch ist folgendes:

Übungsaufgabe 9.4.4 Sei No Small Factor das Komplement von Small Factor, also

$$ \begin{align*} \{ x\texttt{;}k \ | \ x, k \in \{0,1\}^* \textnormal{ und $(x)_2$ hat keinen echten Teiler $Z \leq (k)_2$} \} \ , \end{align*} $$

wobei $(x)_2$ und $(k)_2$ die von $x$ und $k$ codierten natürlichen Zahlen sind.

Diese Übungsaufgabe ist quasi eine Warnung: was denn eine Zertifikatmaschine auf ihrem zweiten Band erwartet, das geht nicht immer aus der Problemstellung hervor!

<< Kapitel 9.3Kapitel 9.5 >>