Ein kurzer Ausflug in die Welt „harter“ Probleme... (Fortsetzung und Abrundung zur ersten Vorlesung in MGI, 1. Semester)

Prof. Dr. Wolfram ConenVorlesung zu ADSJuni 2006

Alan Turing – Mini-Rückblick auf die erste MGI-Vorlesung

23. Juni 1912, London 1936: On computable numbers ...

(es gibt keine „definite“ Methode, die für jede mathematisch-logische Aussage entscheiden kann, ob sie beweisbar ist oder nicht.)

1939-40: Entwicklung der Bombe (zur Entschlüsselung der deutschen Enigma-Codes)

7. Juni 1954: Selbstmord

Von der Intuition zur Exaktheit

Hilbert suchte nach einem Verfahren, das für jede mathematisch-logische Aussage einen Beweis oder eine Widerlegung liefert:

„Das Entscheidungsproblem ist gelöst, wenn man ein Verfahren kennt, das bei einem vorgelegten logischen Ausdruck durch endlich viele Operationen die Entscheidung über die Allgemeingültigkeit bzw. Erfüllbarkeit erlaubt. (...) Das Entscheidungsproblem muss als das Hauptproblem der mathematischen Logik bezeichnet werden“,

Hilbert, Ackermann, Grundzüge der theoretischen Logik, 1928

Um zu zeigen, dass es so ein Verfahren gibt, könnte man einfach eines angeben.

Turing wollte zeigen, das es ein solches Verfahren nicht geben kann! Er mußte etwas finden, dass Hilberts Intuition eines Verfahrens

entsprach, diese präzisierte und wesentliche Eigenschaften aller anderen „möglichen“ Verfahren beinhaltete und so als „Prototyp“ dienen konnte:

Wenn der Prototyp die gewünschte Antwort nicht geben kann, dann kann es auch kein anderes Verfahren!

Die Turing-Maschine: Ein Modell der Berechenbarkeit

...... 0 0 0 1000

Zustand: z1

„Programm“

Falls Zustand == z1 und Zeichen unter Schreib/Lesekopf == 0,

dann schreibe 1, gehe in den Zustand z1 und bewege dich ein Feld nach rechts.

Kurz: (z1,0) (1,z1,R) (z1,1) (0,z1,R) (z1,_) (_,ende,L)

Was macht dieses Programm?

Die Turing-Maschine: Eine Berechnung

...... 0 0 0 1001

Zustand: z1

„Programm“

(z1,0) (1,z1,R) (z1,1) (0,z1,R)(z1,_) (_,ende,L)

0

Die Turing-Maschine: Eine Berechnung

...... 1 1 1 1111

Zustand: z1

„Programm“

(z1,0) (1,z1,R) (z1,1) (0,z1,R)(z1,_) (_,ende,L)

1

Die Turing-Maschine: Eine Berechnung

...... 1 1 1 0 0111

Zustand: z1

„Programm“

(z1,0) (1,z1,R) (z1,1) (0,z1,R)(z1,_) (_,ende,L)

Die Turing-Maschine: Eine Berechnung

...... 1 1 1 0111

Zustand: ende

„Programm“

(z1,0) (1,z1,R) (z1,1) (0,z1,R)(z1,_) (_,ende,L)

0

Die Berechnung hält an!

Noch wichtig: Programm, Eingabe und Zeichensatz sind endlich.

Universelle TM (1)

Turing führt eine Turing-Maschine UTM ein, die andere Turingmaschinen simulieren kann Bisher:

Eingabestring x ! Turingmaschine TM ! Ausgabestring y;kurz: TM(x) = y

Jetzt: Kodieren des Anweisungen der Turingmaschine als String z Eingabestring zx ! Turingmaschine UTM simuliert TM und

wendet die Simulation auf x an ! Ausgabe y;kurz also: UTM(zx) = y bzw. UTM(TM,x) = y

Die UTM von Turing kann alle Turingmaschinen simulieren...sie ist in einem bestimmten Sinn universell

Universelle TM (2)

B0.UTM=1000000101110100000001010110100000010010110100001010110100000100010110101001110100000101010111010000111010000100101011101001001101000010100101101010001101000100010101101010100111010010101010010111010000011101000000000111010000001010110100000100101101001000110100010101001011010010001000110100101010001110101000011101001010010010111010010001001011010100010100111010010000001110101010010111010010010100111010101010101110100000011101001010101010111010000100110100011010001010000110100000101110101001010001011101000101010111010010000110101010010100101101010010110100100101011010100010101101001010010111010101000010011101001010101011101000101010011101010000101101010010001101010001010110100010000101110101001011010010010011010100101010110100100100010111010101000101110101010100011010101001010110100100010110101010100101100111010001001011101001000001110100010001011101001000110100000101011010010010010011101000010010110100100110100001010101101010010010111010011010000000111010001001010110100100010101110100010100101110101001000101110100100001011101001010001010111010100100010111010010010010111010010100010111010010010001110100101000011101000100011010010100100111010010001001110100001110100101001110101001001110100101001110100101010111010000001110101000100010111010100010100101110101000001011101001000001110101000010101101000100110101000100101110101001001110101001010111010010101001010111010100010010101110101010100010111010100100101011101000010101101010100010101100111010101010101001011010001010110101010000101110101010010010110101000000111010001000001110100010001110100001110101010100101011101010000010011101001010000011101000011101010100101110100100000101110100000000110100100110100001010101011010100000010110100001010101101000100110100001000011010001010110100000100110101001110100000010101011101001011010000100010110100001110101010010101011101001001101010101010101011010010011010001001010110100100101011101010101110101000110101010001010101101010000100101101010100101110100000001110100010100101011010010000100111010001010001011010000000111010001010010111010010001101000101010101011010010001101001000101010110100010000110101010101000111010101010100100111010010000100111010000001001101000001000110100100011010000100101101000101011101010010010011101010000011101011101010101010101010110100100101010101101010000100110100010100111010101010000111010101010100001110100001001011101010001011101010000111010010100101010111010100001110100101010001011101010000111010100010010111010001000101110101010101110101010011101001010101010101110101010011101010000101010111010000000011010000000101101010000100011010100000001101000100100011010001001001011010101001110101010000101110100000011101010010000101110101000000111010100100101010111010001101010001010101011101000110101001000101011101000000111010101000001011101000110101001001001011101000110101010101011101000101001110101001110100110101001010010101110100110101001010100101110100110101001010101010111010011010010101010111010010100011101001001101000100101101010100010010111010101001001101010010100110101000110101010010001011010100011010101001001010110100001011101010010101010110100100001101010100101010101101001000011010101010000101101001000011010000000001110100001011101010101001001011101000010111010101010010101011101000010111010010010001011101010000010101110100101000010111011011100111010100001011001110101010101010110100001011101010101000101011101000001010110101011010001001010101101001001010010110101001110100000100101011101000010101101010010100101101010011101000001010010111010101000101110100001

Eine „binäre“ UTM von Stephen V. Gunhouse mit 176 Zuständen

Was kann die Turing-Maschine?

„Alles Machbare!“

Genauer formuliert dies die Church-Turing-These:„Genau das, was wir intuitiv für „effektiv berechenbar“ halten, kann durch

die Turing-Maschine tatsächlich berechnet werden.“

Wir nennen ab jetzt etwas berechenbar, wenn es eine Turingmaschine gibt (geben kann), die mit dem richtigen Ergebnis anhält!

Es wurden noch viele andere Modelle der Berechenbarkeit „erfunden“ (generelle rekursive Funktionen, -Definierbarkeit, Kombinatorische Systeme, Termersetzungssysteme, Registermaschinen, ...), aber alle (zumindest alle physikalisch realisierbaren) erwiesen sich als

„äquivalent“, sie können die gleichen Probleme lösen! Zeigen kann man dies, in dem man ein Modell durch ein anderes

simuliert (und vice versa).

Merke: Modelle der Berechenbarkeit präzisieren den Begriff Algorithmus / Lösungsverfahren (F1)

Noch ein Beispiel...fleissige Bieber

Bieber bauen Dämme aus Baumstämmen... Als Turingmaschine sieht das z.B. so aus:

z1 z2 z3 halt

1/1,L _/1,L

_/1,R 1/1,R

1/1,R_/1,L

_ _ _ _ _ _ _ _ _ _ _

z1 z2z1z1 z2z1 z3

1 111

z2 z3

11 1

z2z1z1 z2z1 z2z1 z3 haltz3

_/1,R

_/1,L

_/1,R

_/1,L1/1,L1/1,L

_/1,L_/1,L

_/1,L_/1,L

_/1,R_/1,R 1/1,R1/1,R

_/1,L_/1,L1/1,L1/1,L

1/1,R1/1,R

Satz: Die Rado-Funktion kann nicht durch eine Turing-Maschine berechnet werden

Luftholen... [Ende des Rückblicks]

Wahre Titanen des Geistes (auch, wenn manche von Ihnen ein unglückliches Ende gefunden haben...) legten die Grundlagen.

Wir wissen jetzt: es gibt Probleme, die sich nicht lösen lassen, obwohl sie „mathematisch genau“ beschrieben sind!

Modelle der Berechenbarkeit erlauben eine Analyse der Berechenbarkeit/Lösbarkeit eines Problems! (F2)

Aber: wie schwer kann es werden, ein konkretes Problem tatsächlich zu lösen?

Komplexität

Gegeben: ein berechenbares Problem P und ein bestimmtes Modell der Berechenbarkeit (z.B. Turing-Maschinen oder RAMs)

Zentrale Frage: Erfordert die Lösung des Problems einen Zeit oder Speicheraufwand, der polynomial oder (möglicherweise) exponentiell zur Größe der Eingabe ist?

Zur Größenordnung: Annahme: Jede Operation benötigt eine

Mikrosekunde

Eingabegröße n = 10 =100 =1000 =1000000

Zeitaufwand als Funktion von n: n 10us 0.1ms 1ms 1s n2 0.1ms 10ms 1s 2W n5 0.1s 3h 30J 3*1016J

2n 1ms 3*1016 J 3*10288J groß

• 3*1016 J ist übrigens mehr als eine Millionen mal die geschätzte bisherige Dauer des Universums...

TSP - Traveling Salesman Problem

Gegeben ist eine Menge von „Städten“, so dass jede von jeder direkt erreichbar ist (z.B. per Hubschrauber ;-)

Mit den Reisen sind Kosten verbunden (wir nehmen mal an, dass die Dreiecksungleichung erfüllt ist, d.h. kein „Umweg“ ist kürzer, als die direkte Verbindung)

Gesucht ist eine Rundtour durch alle Städte, die minimale Kosten über alle möglichen Rundtouren hat (jede Stadt wird nur einmal besucht)

Das ist das „metrische“ TSP

TSP

TSP

TSP

Wir können das TSP als Graphproblem auffassen

n Knoten (die Städte), n*n-1 ungerichtete Kanten (die Wege)

Der Graph ist also vollständig (er kann natürlich auch unvollständig sein...)

Wenn Hin- und Rückfahrt zwischen je zwei Städten gleich teuer sind, dann ist es ein symmetrisches TSP

Naiver Lösungsalgo: Suche zufällig einen Startpunkt

aus Generiere nach und nach alle

möglichen Rundtouren Vergleiche die Länge jeder

Rundtour mit der Länge der bisher besten

Merke dir ggfs. die neue „beste“ Tour

Aufwand? n-1*...*2*1 = (n-1)! im symmetrischen Fall (n-1)!/2

TSP

Für ein symmetrisches TSP gibt es also eine Menge Lösungskandidaten:

n = 5: 12 Touren n = 10: 181.440 Touren n = 20: 60.822.550.204.416.000 Touren

(~ 61 Billiarden Touren)

Das heißt: Die Anzahl von Lösungskandidaten explodiert exponentiell mit steigendem n

TSP

Das geht natürlich besser!

Aber wenn wir wirklich das Optimum haben wollen, dann erfordert jedes exakte Lösungsverfahren im worst case exponentiellen Aufwand es sei denn, NP = P (was das ist, sehen wir gleich)

Man kann metrische TSPs aber zu polynomialen Kosten approximieren (wie gut?)

Approximationen metrischer TSPs

Jetzt kommt unser alter MST zu Ehren: Gegeben: 8 Knoten, vollständiger, ungerichteter Graph

MST „Doppelter“ MST: jedeKante wird verdoppelt und die Kanten eines jeden Paares werden in gegensätzliche Richtungen orientiert

Rundtour mit „Abkürzungen“

v

Approximationen metrischer TSPs

Algo APP_TSP Bestimme einen MST T Wähle zufällig einen Knoten v

und laufe komplett um den Baum (=verdopple alle Kanten und mache eine Eulertour)

Vermerke dabei die Besuche der Knoten in einer Liste L

Entferne alle bis auf das jeweils erste Vorkommen der Knoten, zurück bleibt der Kreis C (oder kürze bei der Tour gleich ab)[C ist ein Preorder-Traversal von T]

Kosten für Prim: O(m + n log n) = O(n2) für kompletten Graph

O(1) (Auswahl) O(n) (n-1 Kanten * 2)

O(n) Speicher

O(n)

Dominiert von MST-Kosten, insgesamt O(n2)

Approximationen metrischer TSPs

Satz: C ist eine 2-Approximation der kürzesten Tour (Beweis gleich)

Aber: was ist eine 2-Approximation?

Gegeben ist ein Optimierungsproblem OPT mit der optimalen Lösung C*

Gegeben ist außerdem ein Approximationsalgorithmus, der eine Näherungslösung zu OPT bestimmt, seine Lösung hat den Wert C

Approximationen metrischer TSPs

C* = optimale Lösung, C = approximative Lösung

Approximationsfaktor für eine bestimmte Instanz bei einem Minimierungsproblem: C/C*

Approximationsfaktor des Algorithmus:p = sup C/C*

Hier wird das Supremum (also die Schranke nach oben) über alle Instanzen bestimmt (also eine Schranke für die schlechteste Approximation, die der Algo liefert)

p ist hier immer größer als 1 (klar, C kann ja nicht besser als C* sein)

Approximationen metrischer TSPs

Relativer Fehler des Approximationsalgorithmus: = sup |C-C*|/C*

Für Minimierungsprobleme äquivalent zuC · (1 + C*, d.h. p · (1 +

Approximationsschema: Eingabe: eine Probleminstanz I und ein > 0

Ausgabe: eine (1+)-Approximation des Optimums (für Minimierungsprobleme)

D.h. einem Approximationschema können sie sagen, welche Qualität es liefern soll! (sie geben also den maximal erlaubten relativen Fehler vor)

Approximationen metrischer TSPs

2-Approximation: = 1, d.h der relative Fehler ist schlechtestenfalls 1, der

Approximationsfaktor also nicht schlechter als (1+)=2, d.h. C ist höchsten doppelt so teuer, wie C*

Zurück zum Satz, dass APP_TSP eine 2-Approximation liefert (zur Erinnerung: T ist unser MST, C unser Kreis) Wenn man aus der optimalen Tour eine Kante entfernt, hat meinen

einen Spannbaum, d.h. C* ¸ Cost(T) In L wird jede Kante aus T zweimal aufgenommen, also Cost(L) =

2*Cost(T) C entsteht aus L durch Hinzufügen von Abkürzungen. Weil die

Dreiecksungleichung gilt, kann C nicht länger als L sein, also C · Cost(L)

Insgesamt also: Cost(T) · C* · C · Cost(L) = 2*Cost(T)

Approximationen metrischer TSPs

Christofides hat 1976 einen verbesserten polynomiales 3/2-Approximations-algorithmus gefunden (mittels MST und minimum weight matching)

Engebretsen hat 1999 gezeigt, dass kein Approximationsfaktor 5381/5380 - für > 0 möglich ist

Spannend wird es, wenn man gute polynomiale Approximationsschemata (AS) findet: PTAS sind AS, deren Laufzeit polynomial zu n bei gegebenem ist (PT =

polynomial time) FPTAS sind AS, deren Laufzeit polynomial zu n und 1/(FPT = fully

polynomial time) O(n1/), O(n/): Beides PTAS, nur das zweite FPTAS

Approximationen metrischer TSPs

Mit einem solchen Schema können sie in der Praxis wie folgt arbeiten:

Sie haben 2 Wochen Zeit, bis sie ein möglichst gute Lösung brauchen sie bestimmen mit der Abschätzung und lassen das PTAS loslaufen nach ungefähr 2 Wochen wird es in der entsprechenden Güte antworten dann brauchen sie aber natürlich eine Abschätzung, in der auch die

Konstanten enthalten sind und sie müssen wissen, wie lang elementare Operation (im Mittel) wirklich brauchen.

Approximationen metrischer TSPs

Sie können also den Trade-Off zwischen Aufwand und Güte bewusst steuern – was will man mehr! (wenn dann die zur Verfügung stehende Zeit auch noch für „gute“

Lösungen reicht, dann haben sie wirklich Glück ;-) Für euklidische TSP (=metrisch und in der Ebene, also ohne Berg-auf, Berg-

ab) hat Arora 1996 ein gutes PTAS gefunden (und ist damit berühmt geworden)!

Uneingeschränktes TSP ist in der Klasse der schwierigsten Optimierungsprobleme (NPO-complete), d.h. es gibt keine 2n^-Approximation für kleine (Orponen, Mannila, 1987)

Wie schwer ist TSP „wirklich“?

TSP lässt sich mit einer nicht-deterministischen Turingmaschine, die den richtigen Abarbeitungsweg „raten“ kann, in polynomialer Zeit lösen Man sagt: TSP ist in der Komplexitätsklasse NP

Es ist aber keine deterministische Turingmaschine bekannt, die alle TSPs in polynomialer Laufzeit lösen könnte Sonst wäre TSP in der Komplexitätsklasse P. Zu Problemen in P (z.B.

Kürzeste-Wege-mit-nicht-negativen-Kanten) sagt man auch: Problem dieser Problemklasse sind effizient lösbar!

Offene Frage: Ist P=NP?

TSP und Komplexität

TSP gehört zu den „schwersten“ Problemen in NP: wenn man dieses polynomiell lösen könnte, dann ginge das auch mit allen anderen Problemen aus NP! TSP ist deshalb ein NP-vollständiges Problem

Als erstes NP-vollständiges Problem wurde 1971 von Cook das SAT-Problem identifiziert: Erfüllbarkeit von aussagenlogischen Formeln! (kennen sie aus MGI) – alle anderen Probleme in NP lassen sich auf dieses Problem „reduzieren“.

TSP und Komplexität

Es gibt noch viele andere NP-harte Probleme: Matching-Probleme („Stabile Heirat“), Graph-Färbe-Probleme, div. Scheduling/Planungsprobleme (Stundenplan! ;-), ganzzahlige Programmierung, usw. – einen Überblick finden sie auch im Web: http://www.nada.kth.se/~viggo/problemlist/

Es gibt auch noch sogenannte NP-harte-Probleme, diese sind „mindestens so schwer, wie Probleme aus NP“ und ihre Lösung würde zur Lösung aller Probleme aus NP führen (alle NP-Probleme lassen sich auf sie reduzieren), aber es ist nicht sicher, ob sie wirklich in NP liegen (oder aber in EXP, also sicher exponentiellen Aufwand erfordern, auch im nichteterministischen Fall!)

Mögliche Auswege für den Informatiker (1)

Nicht alle Probleminstanzen sind schwer! Vielleicht gehören „unsere“ Probleminstanzen dazu? manchmal kann man das generell sagen (wenn das Problem nicht

„stark NP-schwer“ ist), manchmal helfen Experimente! manchmal findet man auch „langsam wachsende“ exponentielle

Algorithmen

Mögliche Auswege für den Informatiker (2)

Alternativ kann man vielleicht approximieren!

Man sucht nach polynomialen Algorithmen, die eine bestimmte Güte der Lösung garantieren können (etwa immer mindestens halb so gut wie das Optimum)

Manche Probleme lassen sich nicht sinnvoll approximieren, auch das kann man formal untersuchen!

Mögliche Auswege für den Informatiker (3)

Oder man wendet eine Heuristik an, die versucht mit Daumenregeln oder beispielsweise in Anlehnung an natürliche Prozesse „schnell“ „gute“ Lösungen zu finden Das kann natürlich grandios schief gehen! Auch hier kann man einiges analysieren!

Bei allem hilft die Theorie zu Komplexität und Approximierbarkeit, die aus den Modellen zur Berechenbarkeit hervorgegangen ist:

Die Analysen von Komplexität und Approximierbarkeit stecken den Rahmen für die erreichbare Lösungsqualität ab! (F3)

Sie weisen den Weg zu verwandten Problemen und bereits bekannten exakten, approximativen oder heuristischen Problemlösungen! (F4)

Rückblick: Bedeutung für den Informatiker

Zentrale Aufgaben: Problemanalyse und Problemlösung (das greift einige Fragen aus der ersten Vorlesung zur Geschichte der Informatik im ersten Semester / MGI auf)

(F1) Wie lassen sich mein Problem und eine ev. Lösung präzise beschreiben?

Präzision ist eine wesentlich Voraussetzung für Analyse und Lösung von Problemen (Übergang zur Logik)

Modelle der Berechenbarkeit präzisieren den Begriff Algorithmus/Lösungsvorschrift

(F2) Ist das Problem überhaupt lösbar?

Modelle der Berechenbarkeit erlauben eine Analyse der Berechenbarkeit/Lösbarkeit eines Problems!

Rückblick: Bedeutung für die Anwendungsentwicklung (2)

(F3) Wenn ja, kann ich es auch mit vertretbarem Aufwand lösen?

Die Komplexitätstheorie hilft uns, die Schwere des Problems einzuschätzen!

Die Analysen von Komplexität und Approximierbarkeit stecken den Rahmen für die erreichbare Lösungsqualität ab!

(F4) Wie kann ich das Problem lösen? Die Komplexitätstheorie hilft auch, verwandte Probleme zu

identifizieren! Die Analysen von Komplexität und Approximierbarkeit weisen den

Weg zu verwandten Problemen und bereits bekannten exakten, approximativen oder heuristischen Problemlösungen! (Übergang zur Algorithmik)