Transcript
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 effizient 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 effizienten Algorithmus geben um zu prüfen ob f (w) in B liegt, so gäbe es auch einen effizienten 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 unver¨ ndert 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
