NP-Vollständigkeit 1 Motivation 2 Polynomialzeitreduktion

Proseminar Theoretische Informatik
19.01.2016
NP-Vollständigkeit
Patrick Cichon
1
Wolfgang Mulzer
Motivation
Die Menge der NP-vollständigen Probleme umfasst genau die schwersten Probleme in NP, bzw.
etwas genauer: sie ist die Teilmenge der Probleme in NP, die so komplex sind, dass man mit
ihnen alle anderen Probleme in NP simulieren kann.
NP-vollständige Problemen sind für die theoretische Informatik interessant, weil sie zum Beweisen von Gleichheit bzw. Ungleichheit von P und NP genutzt werden können:
Beobachtung 1. Sollte es einen Algorithmus geben, mit dem irgendein NP-vollständiges Problem in Polynomialzeit entschieden werden kann, so würde dies bedeuten, dass alle Probleme in
NP auch in P liegen.
Beobachtung 2. Sollte es jedoch gelingen zu beweisen, dass mindestens ein NP-vollständiges
Problem nicht in Polynomialzeit berechenbar ist, so wäre damit bewiesen, dass P und NP ungleich sind.
2
Polynomialzeitreduktion
Wir wissen bereits, dass mit Reduktion und Wissen über die Entscheidbarkeit eines Problems
Schlussfolgerungen über die Entscheidbarkeit des anderen an der Reduktion beteiligten Problems gezogen werden können. Gilt beispielsweise A ≤ B, so wissen wir, dass Entscheidbarkeit
von B auch Entscheidbarkeit von A impliziert, da es eine Umwandlungsfunktion für Eingaben
für A gibt um sie zu Eingaben für B umzuwandeln.
Für NP-Vollständigkeit ist es jedoch nicht ausreichend zu wissen ob es so eine Funktion gibt.
Es ist auch wichtig ob diese Funktion eﬃzient berechnet werden kann.
Definition 3. Eine Funktion f : Σ∗ −→ Σ∗ ist eine in Polynomialzeit berechenbare Funktion
wenn es eine Polynomialzeit Turingmaschine M gibt, die für die Eingabe w mit genau f (w) auf
ihrem Band hält.
Definition 4. Eine Sprache A ist in Polynomialzeit redizuierbar auf die Sprache B, geschrieben
als A ≤P B, wenn es eine in Polynomialzeit berechenbare Funktion f : Σ∗ −→ Σ∗ gibt, für die
gilt:
∀w ∈ Σ∗ : w ∈ A ⇐⇒ f (w) ∈ B
Die Funktion f wird Polynomialzeitreduktion genannt.
Sollte es einen eﬃzienten Algorithmus geben um zu prüfen ob f (w) in B liegt, so gäbe es auch
einen eﬃzienten Algorithmus um zu prüfen ob w in A liegt, nämlich indem erst f (w) berechnet
wird und dann f (w) ∈ B getestet wird.
1
Beispiel
3SAT ist das Problem nach der Frage, ob eine boolesche Formel in cnf (konjunktiver Normalform), bei der jede Klausel aus genau drei Literalen besteht, erfüllbar ist, das heißt, ob es für
die Formel eine Belegung der Variablen mit true oder f alse gibt, bei der die Formel insgesamt
gültig ist.
CLIQUE ist das Problem nach der Frage, ob es bei einem ungerichteten Graphen eine Teilmenge
aus k Knoten gibt, die untereinander vollständig paarweise durch Kanten verbunden sind.
Satz 5.
3SAT ≤P CLIQU E
Beweis. Gesucht wird nach einer Polynomialzeitfunktion f : Σ∗ −→ Σ∗ , sodass
w ∈ 3SAT ⇐⇒ f (w) ∈ CLIQU E
Die booleschen Formel w, die Eingabe für 3SAT ist, hat die Form
w = (a1 ∨ b1 ∨ c1 ) ∧ (a2 ∨ b2 ∨ c2 ) ∧ . . . ∧ (ak ∨ bk ∨ ck )
Aus w wird ein ungerichteter Graph mit drei Knoten pro Klausel generiert. Kanten werden
paarweise zwischen allen Knoten α und β eingefügt, es sei denn mindestens eine der folgenden
Bedigungen ist erfüllt:
α und β sind in der selben Klausel.
(1)
α≡β
(2)
Nun muss gezeigt werden, dass der Graph in Polynomialzeit erzeugt werden kann und dass es
im Graphen genau dann eine k-Clique gibt, wenn w erfüllbar ist.
Beweisrichtung f (w) ∈ CLIQUE =⇒ w ∈ 3SAT Wenn es im Graphen eine solche
Clique gibt, so wissen wir über die beteiligten Knoten, dass die entsprechenden Literale aus
unterschiedilchen Klauseln kommen und dass sie nicht gegensätzlich sind Es muss sich also um
eine mögliche Belegung der Variablen handeln, wenn man genau die Literale der Clique wahr
setzt, bei der in jeder Klausel mindestens eine Variable wahr ist. Somit wäre w erfüllbar.
Beweisrichtung w ∈ 3SAT =⇒ f (w) ∈ CLIQUE Wenn es eine erfüllende Belegung für
w gibt, so muss in jeder der k Klauseln mindestens ein Literal auf true gesetzt sein. Wählt
man aus jeder Klausel ein Literale aus, das auf true gesetzt ist, so bilden die entsprechenden
Knoten des generierten Graphen f (w) eine k-Clique, denn die Literale können einender nicht
widersprechen und stammen aus unterschiedlichen Klauseln.
Zeitaufwand zur Berechnung von f (w):
• Es gibt genau so viele Knoten in f (w) wie Literale in w, der Zeitaufwand der Berechnung
dieser liegt also in O(n).
• Die Anzahl an möglichen Kanten in einem ungerichteten Graphen mit m Knoten ist kleiner
oder gleich m · (m − 1) und wie eben gezeigt ist m = n, also liegt der Zeitaufwand zur
Berechnung dieser in O(n2 )
2
3
NP-Vollständigkeit
Definition 6. Eine Sprache B ist NP-vollständig, wenn
1. B in NP liegt und
2. jedes A in NP Polynomialzeit reduzierbar auf B ist.
Um zu zeigen, dass ein Problem B in NP liegt, würde es ausreichen zunächst zu zeigen, dass
B in NP liegt und dass ein Beliebiges NP-vollstaendiges Problem A auf B in Polynomialzeit
reduzierbar ist, da deshalb jedes Problem in NP auf B in Polynomialzeit reduzierbar wäre indem
erst die Polynomialzeitreduktion auf A und dann auf B angewandt wird.
Satz 7. Gilt für ein B aus NP und ein beliebiges NP-vollständiges A, dass A ≤P B, so ist B
NP-vollständig.
Um diese Vorgehensweise zum Beweisen von NP-Vollständigkeit nutzen zu können ist es jedoch
nötig bereits mindestens ein NP-Vollständiges Problem zu kennen. Man muss aber für ein Problem die NP-Vollständigkeit beweisen ohne sich auf die NP-Vollständigkeit anderer Probleme
zu stützen um überhaupt beweisen zu können, dass es Problem NP-vollständig ist.
4
SAT
SAT - satisfiability bzw. Erfüllbarkeit - ist eine verallgemeinerung von 3SAT und beschäftig sich
mit der Frage, ob eine beliebige boolesche Formel erfüllbar ist.
Satz 8. SAT ist NP-vollständig.
Um zu beweisen, dass SAT NP-vollständig ist, muss zunächst bewiesen werden, dass es in NP
liegt. Dabei wird in betracht gezogen, dass eine nichtdeterministische Turingmaschine die gültige
Belegung erraten kann und dann in Polynomialzeit die Gültigkeit der Formel prüfen kann. Auf
diesen Teil des Beweises wird hier nicht weiter eingegangen.
Beweisidee Um zu beweisen, dass jedes Problem A in NP auf SAT reduzierbar ist, konstruieren wir die Polynomialzeitreduktion jeder beliebigen Sprache in NP auf SAT. Dazu wird die
nichtdeterministische Turingmaschine N , welche A entscheidet, mit dem Eingabewort w durch
ein boolesche Formel simuliert.
Beweis. Für jede Sprache in NP gibt es eine nichtdeterministische TM N , die sie für ein festes
k in O(nk ) Schritten entscheidet, wobei n die Größe der Eingabe ist. Die einzelnen Berechnungsschritte eines Berechnungsstranges von N seien in einer Tabelle mit nk + 1 Zeilen und nk + 3
Spalten dargestellt. Jede Zeile stellt dabei einen Berechnungsschritt von N dar und in jeder
Zelle steht ein Zeichen aus dem Bandalphabet Γ von N , der aktuelle Zustand von N (wobei
die Position des Zustandes in der Zeile mit der Position des Kopfes übereinstimmt) oder ein
besonderes Zeichen # zum Markieren der ersten und letzten Spalte der Tabelle.
Die Menge C sei die Vereinigung des Bandalphabets, der Zustandsmenge und #.
3
In der ersten Zeile der Tabelle steht de Startkonfiguration von N mit Startzustand q0 und den
Zeichen von w:
#
#
..
.
q0
w1
...
wn
␣
...
␣
#
#
#
..
.
Startkonfiguration
#
Die Tabelle und somit auch ein Berechnungsstrang von N gelten als akzeptierend, wenn in
mindestens einer Zeile / Konfiguration ein Endzustand erreicht wurde.
Die boolesche Formel ϕ, die diese TM simuliert, hat folgende Form:
ϕcell ∧ ϕstart ∧ ϕaccept ∧ ϕmove
(3)
Die Zelle in Zeile i und Spalte j sei cell(i, j).
xi,j,c sei eine Variable der booleschen Formel und genau dann wahr, wenn in cell(i, j) das Zeichen
c ∈ C steht.
ϕcell = In jeder Zelle der Tabelle steht genau ein Element aus C.
ϕcell =
∧
1≤i≤nk +1
1≤j≤nk +3



)
(
 ∧
 ∨




(xi,j,c ∨ xi,j,d )
∧
x
i,j,c



c∈C
(4)
c,d∈C
c̸=d
in Worten: In jeder Zelle ((steht mindestens ein Zeichen) und (steht nicht mehr als ein Zeichen)).
ϕstart = In der ersten Zeile der Tabelle befinden sich außen die #-Symbole und daziwschen das
Eingabewort w und q0 über dem ersten Zeichen von w.
ϕstart = x1,1,# ∧ x1,2,q0 ∧ x1,3,w1 ∧ . . . ∧ x1,n+2,wn ∧ x1,n+3,␣ ∧ . . . ∧ x1,nk +2,␣ ∧ x1,nk +3,#
(5)
ϕaccept = in einer Zelle befindet sich ein Endzustand von N .
ϕaccept =
∨
xi,j,qaccept
(6)
1≤i≤nk +1
1≤j≤nk +3
ϕmove soll garantieren, dass jede Zeile durch eine gültige Operation von N aus der vorherigen
Zeile folgen kann. Dafür wird gesorgt, indem jedes 2 × 3 Fenster der Tabelle mit der Übergangsfunktion δ von N entstehen kann.
(beispielhafte gültige Fenster als Tafelbild)
Behauptung: Ist die erste Zeile der Tabelle gültig, und entsprechen alle 2 × 3 Fenster einem
gültigen Fenster, so entspricht jede Zeile einer Konfiguration, die durch N auf die vorherige
folgen kann.
In der tabelarischen Darstellung eines Berechnungsstranges von N können sich in jedem Berechnugnsschritt nur Felder im unmittelbaren Umfeld des Zustandssymboles verändern.
4
Da sich jede Zelle, die sich weder neben dem Zustandssymbol befindet noch ein # enthält, im
mittleren oberen Feld nur solcher Fenster befinden kann, bei denen sich in der oberen Reihe keine
Zustandssymbole befinden, muss in jedem gültigen passenden Fenster das Symbol unvern̈dert
im unteren mittleren Feld auftauchen. Dadurch ist garantiert, dass alle 2 × 3 Fenster ohne
Zustandssymbole in der oberen Zeile legal sind.
Für Fenster, bei denen das obere mittlere Feld ein Zustandssymbol enthält ist garantiert, dass
die unteren drei Felder logisch aus den oberen folgen.
Sei das (i, j) Fenster das Fenster, dessen oberes mittlere Feld in Zeile i und Spalte j liegt. ϕmove
soll für all diese Fenster überprüfen, ob es zulässig ist.
ϕmove =
∧
(F enster(i, j) ist legal)
(7)
1≤i≤nk
2≤j≤nk +2
wobei wir (F enster(i, j) ist legal) durch Folgendes ersetzen:
∨
xi,j−1,a1 ∧ xi,j,a2 ∧ xi,j+1,a3 ∧ xi+1,j−1,a4 ∧ xi+1,j,a5 ∧ xi+1,j+1,a6
(8)
zulässiges Fenster mit Feldern
a1 ,...,a6
Die generierte boolesche Formel ϕ ist genau dann erfüllbar, wenn die nichtdeterministische
Turingmaschine bei Eingabe w einen akzeptierenden Berechnungsstrang hat. Es ist allerdings
entscheidend, dass ϕ in Polynomialzeit in Abhängigkeit von |w| aus N und w berechnet werden
kann.
Wir wissen, dass die Anzahl an Variablen in ϕ in O(n2k ) liegt, denn es gibt (nk + 3) ∗ (nk + 1)
viele Felder und die Anzahl an möglichen Werten pro Feld ist |C| = |Q| + |Γ| + 1. Diese Anzahl
ist nicht von der Länge von w, sondern nur von der TM, abhängig.
Außerdem müssen wir die Komplexität der Berechnungen von ϕcell , ϕstart , ϕaccept und ϕmove
analysieren.
Die Länge der Teilformeln für jede Zelle in ϕcell ist lediglich von |C| abhängig, liegt also in O(1).
Somit liegt der Zeitaufwand zur Berechnung von ϕcell in O(n2k )
ϕstart besteht aus genau nk + 3 Variablen, liegt also in O(nk ).
ϕaccept ist die Konjuktion von einer Variable pro Zelle, liegt also in O(n2k ).
ϕmove hat für jede Zelle der Tabelle eine fest von N abhängige Länge, liegt also in O(n2k ).
Der Zeitaufwand zur Berechnung von ϕ liegt also in O(n2k ) und ist somit polynomiell von der
Größe der Eingabe abhängig.
NP-Vollständigkeit anderer Probleme A kann nun einfacher bewiesen werden, indem man Zugehörigkeit zu NP und A ≤P SAT zeigt.
5
Quellen
[1] Michael Sipser. Introduction to the Theory of Computation, Thomson Course Technology,
2. Auflage, 2006. Abschnitte 7.4 – 7.5
5

Download Report