Michael Budahn - Theoretische Informatik 1

NP-vollständige Probleme

Michael Budahn - Theoretische Informatik 2

Motivation

Michael Budahn - Theoretische Informatik 3

Motivation● viele praxisrelevante Probleme sind NP-

vollständig und eine Lösung würde auf vielen Gebieten helfen

● wenn man weiss das es unmöglich ist effizente Algorithmen zu finden braucht man keine zu suchen

Michael Budahn - Theoretische Informatik 4

Definition● Ein Problem C ist NP-vollständig wenn :

(1) von einer Nicht-Deterministischen Turingmaschine in polynomieller Zeit erkannt wirdird

(2) sich alle Probleme in NP auf C reduzieren lassen

Michael Budahn - Theoretische Informatik 5

Definition● Problem A ist auf ein Problem B reduzierbar

genau dann wenn:– es einen deterministischen Algorithmus mit

polynomieller Laufzeit gibt der aus einem Problem ein Problem macht, sodass b genau dann wahr ist wenn a auch wahr ista∈A b∈B

Michael Budahn - Theoretische Informatik 6

Folgen aus der Definition● wenn man ein Algorithmus findet der ein NP-

vollständiges Problem löst kann man sämtliche Probleme aus NP in polynomieller Zeit lösen P = NP

● um zu zeigen das ein Problem np-vollständig ist muss man nur zeigen das ein anderes NP-vollständiges Problem darauf reduzierbar ist

⇒

Michael Budahn - Theoretische Informatik 7

Einige np-vollständige Probleme● SAT (Boolean satisfiability problem)

– ist ein Boolscher Ausdruck durch eine Variablenbelegung erfüllbar?

● n-Puzzle– ist eine bestimmte Position lösbar?

● knapsack– kann man Gegenstände von einem Wert größer als

w in seinen Rucksack packen ohne das Gewicht g zu überschreiten?

a∧b∨¬a∧c∧¬b∨¬c

Michael Budahn - Theoretische Informatik 8

Einige np-vollständige Probleme● Subset sum

– Gegeben eine Menge an Ganzzahlen gibt es eine Teilmenge die Aufsummiert null ergibt?

● Cliquen-Problem– Gibt es in einem Graphen einen Clique mit mehr als

k-Knoten?– Eine Clique sind paarweise adjazente Knoten

● Independent Set– Gibt es in einem Graphen eine Menge

unabhängigen Knoten größer k?

Michael Budahn - Theoretische Informatik 9

Einige np-vollständige Probleme● Subgraph isomorphism

– gegeben zwei Graphen G und H ist G ein Untergraph von H?

● Graph coloring– kann man die Knoten eines Graphen mit n Farben

so einfärben so das adjazente Knoten nicht die gleiche Farbe haben?

Einige np-vollständige Probleme● Hamiltonian Cycle

– gibt es in einem Graphen einen Hamiltonischen Kreis?

● Traveling salesman– Gegeben Städte und Kosten um zwischen ihnen zu

reisen. Kann man alle Städte bereisen ohne dabei ein bestimmtes Kostenlimit zu überschreiten?

Hamiltonian Cycle● Wie können wir zeigen das das Hamiltonian

Cylce Problem np-vollständig ist?(1) wir zeigen das man eine Lösung für das Problem

in polynomieller Zeit verifizieren kann(2) wir zeigen das ein anderes np-vollständiges

Problem auf den Hamiltonian Cycle reduzierbar ist

Reduktion von Hamiltonian Cycle auf Traveling Salesman

AB

C

D E

HamiltonischerKreis ?

polynomiellerAlgorithmus

AA

B

B

C

C

D

D

E

E

1 11 1 1 1

11 1 11 1 11 1 1

AB

C

D E

Gibt es einen Kreis mit Gewicht 0 ?

AA

B

B

C

C

D

D

E

E

0 00 0 0 0

00 0 00 0 00 0 0

11

1 1

Reduktion● Mittlerweile gibt es mehr als 3000 Probleme für

die NP-Vollständigkeit bewiesen wurde● Wie wurde das erste NP-Vollständige Problem

gefunden?

Satz von Cook● Stephan A. Cook bewies 1971 in dem nach ihm

benannten Satz von Cook die NP-Vollständigkeit des Boolschen Erfüllbarkeitsproblems (SAT)

Satz von Cook● Zu jedem Problem in NP gibt es eine

nichtdeterministische Turingmaschine M' die es in polynomieller Laufzeit löst

● Zu M' konstruieren wir M sodass :– M hat 1 Band– M betritt kein Feld links der Eingabe– anstatt stehenzubleiben verharrt M in der

Konfiguration– M hat immernoch polynomielle Laufzeit T n=cnk

Satz von Cook● Wenn wir die Zellen des Bandes mit 1

beginnend durchnummerieren brauchen wir uns nur mit den Zellen von 1 bis T+1 beschäftigen. Für alle anderen brauchen wir mehr als T Schritte um sie zu erreichen

● ein Wort x ist genau dann in der Sprache wenn es eine Reihe von Konfigurationen gibt und die T-te Konfiguration eine akzeptierende ist

Satz von Cook● Wir brauchen nun eine Funktion die uns aus

der Turingmaschine und dem Eingabewort eine Boolsche Formel erstellt die genau dann wahr ist wenn x in L liegt

● eine erfüllende Belegung der Boolschen Formel beschreibt eine legale akzeptierende Rechnung in polynomiller Zeit

Satz von Cook● Wir können nun alle Probleme in NP in ein

SAT-Problem umwandeln. Wenn es einen deterministischen Algorithmus mit polynomieller Laufzeit gibt der SAT löst dann können wir auch alle anderen Probleme in NP lösen. Daraus folgt np-Vollständigkeit für das SAT-Problem

Cliquen Problem● Wir wollen wissen ob es in einem Graphen G

eine Clique größergleich k gibt● Eine Clique ist eine Menge an Knoten die

paarweise adjazent sind● Wir wollen zeigen das das Cliquen Problem

NP-nollständig ist und führen es einfach auf das Independent set Problem zurück

Independent set● Wir wollen wissen ob es in einem Graphen G

eine Menge an unabhängigen Knoten größer k gibt

● unabhängige Knoten sind untereinander paarweise nicht adjazent

● dieses Problem reduzieren wir auf das Cliquenproblem

Independent set● Wir bilden den inversen Graphen G' zu G indem

wir überall da wo Kanten waren die Kanten streichen und überall da wo keine Kanten waren Kanten hinzufügen

● in G' gibt es genau dann eine Clique größer als k wenn es in G ein Menge unabhängiger Knoten größer k gibt

Independent set● Nun zeigen wir noch das Independent set

wirklich in NP-schwer ist indem wir das SAT Problem darauf reduzieren

● Wir kriegen eine boolsche Formel und bringen sie in KNF

● wir konstruieren einen Graphen mit den Literalen als Knoten und verbinden alle Knoten einer Klausel und alle Literale mit ihrem negierten Gegenstück

Independent set● wenn es in dem Graph ein unabhängige Menge

größer als die Anzahl der Klauseln gibt dann ist die Formel erfüllbar

Quellen– Einführung in die Automatentheorie, Formale

Sprachen und Komplexitätstheorie (Hopcroft, Ullmann)

– Algorithms (Sedgewick)– Wikipedia– Uni-Hamburg– Uni-Ilmenau