Hannes Diener -...

GTI

Hannes Diener

ENC B-0123,diener@math.uni-siegen.de

11.–18. Juli 2013

1 / 44

KomplexitatEinleitung

Im letzten Teil der Vorlesung soll es uns nicht so sehr darum gehen,ob ein Problem oder eine Funktion theoretisch berechenbar sind,sondern inwieweit dies auch praktisch vom Zeit- undRechenaufwand machbar ist; d.h. wie komplex ein Problem ist.

2 / 44

KomplexitatEinleitung

Wie wir gesehen haben sind alle Rechenmodelle, die wir betrachtethaben gleich machtig. Andererseits lassen sich einige Probleme z.B.viel einfacher mit WHILE-Programmen losen als mit Turingmaschinen(man denke nur an die Addition einer Binarzahl mit 1). D.h. wieauch immer wir Komplexitat definieren, der Begriff wird vomeigentlichen Modell und vielen anderen Details abhangig sein.

Allerdings werden wir auch sehen, daß fur die meistenKomplexitatsklassen, die wir betrachten viele dieser Unterschiedewieder verschwinden.

3 / 44

KomplexitatEinleitung

Wie wir gesehen haben sind alle Rechenmodelle, die wir betrachtethaben gleich machtig. Andererseits lassen sich einige Probleme z.B.viel einfacher mit WHILE-Programmen losen als mit Turingmaschinen(man denke nur an die Addition einer Binarzahl mit 1). D.h. wieauch immer wir Komplexitat definieren, der Begriff wird vomeigentlichen Modell und vielen anderen Details abhangig sein.Allerdings werden wir auch sehen, daß fur die meistenKomplexitatsklassen, die wir betrachten viele dieser Unterschiedewieder verschwinden.

3 / 44

KomplexitatEinleitung

Die Art von Komplexitat eines Problems, die uns am meisteninteressiert ist:

Wie viel Zeit benotigt ein Programm zur Berechnung einerAusgabe?

Es sei aber auch erwahnt, daß es auch Problemstellungen gibt beidenen man eher z.B. am Speicherbedarf, Bandbreitenbedarf, usw.interessiert ist.

4 / 44

KomplexitatEinleitung

Wir wollen uns im folgenden vor Allem auf den Zeitbedarf einerTuringmaschine konzentrieren. Auch wenn Turingmaschinenpraktisch nicht relevant sind lassen sich die Ergebnisse dennoch indie Praxis ubertragen. Ausserdem ist es anschaulicher denZeitbedarf einer (Turing)-maschine zu definieren, als den vonanderen Berechnungsmodellen.

5 / 44

KomplexitatEinleitung

Also kommen wir zu den ersten Definitionen.

DefinitionDie Rechenzeit einer Turingmaschine M ist definiert durch

RZMpx1, . . . , xkq “

$

’

&

’

%

nfalls M in genau n Rechenschritten

bei Eingabe x1, . . . , xk akzeptiert

K sonst.

DefinitionEine Turingmaschine M berechnet die Funktion f : Nk Ñ N in Zeitt : NÑ N, falls fur alle x1, . . . , xk P N gilt

RZMpx1, . . . , xkq ď tp|x1| ` ¨ ¨ ¨ ` |xk |q ,

wobei |x | die Lange der Binarzahldarstellung von x ist.6 / 44

Es ist wichtig, sich daran zu erinnern, daß wir annehmen, daßTuringmaschinen auf Binarzahldarstellungen arbeiten.

7 / 44

Beispiel

Die Turingmaschine M1, die 1 zu einer Binarzahl addiert benotigt:

RZM1p11q “ 10 .

Allgemein sieht man, daß M1 ca. 2|x | Schritte, bei Eingabe xbenotigt.

8 / 44

Um uns nicht unnotig mit Details aufzuhalten (siehe “ca.” auf dervorherigen Folie) treffen wir noch folgende Konvention:

DefinitionEine Turingmaschine M berechnet f in Zeit Optq, falls es ein c ą 0gibt, so daß M die Funktion f in Zeit

ctpnq ` c

berechnet.

Also berechnet M1 die Funktion S “ λn.n ` 1 in Zeit Opnq.

9 / 44

Berechnet man das Laufzeitverhalten fur verschiedene einfache Funktionenerhalt man folgende Tabelle:1

Eingabelange20 40 60 100 300

Laufzeitverhaltenpolynomiell n 10´8 s 10´7 s 10´7 s 10´7 s 10´7 s

n2 10´7 s 10´6 s 10´6 s 10´5 s 10´4 sn3 10´5 s 10´4 s 10´4 s 10´3 s 10´2 s

exponentiell 2n

log2 n 10´7 s 10´6 s 10´5 s 10´3 s 79 Tage2n 10´3 s 19 min 37 J. 1013 J. 1073 J.

1Die angegebenen Zeiten beziehen sich auf einen Rechner mit 1Mio.Operationen pro Sekunde. Beachte, dass schnellere Rechner lediglich eineBeschleunigung um einen konstanten Faktor bewirken, d.h. das Bild nichtwesentlich andern.

10 / 44

Wie man aus der Tabelle oben sieht sind Polynome praktischberechenbar, aber exponentielle Funktionen nicht.

§ Naturlich ist ein Algorithmus, der in Zeit n2 arbeitet besser alseiner, der Zeit n5 benotigt. Fur theoretische Untersuchungenbraucht man aber zumindest, dass die betrachteteFunktionsklasse unter Substitution abgeschlossen ist, was beiAlgorithmen mit polynomiellem Laufzeitverhalten der Fall ist,aber nicht bei solchen, die fur festes k in Zeit nk arbeiten.

§ Naturlich ist auch z.B. 2n fur kleine n schneller berechenbar,als n2000 ` 1024. Uns interessiert aber nur das asymptotischeVerhalten.

11 / 44

DefinitionSei f : Nk Ñ N. Eine Turingmaschine M berechnet die Funktion fin Polynomialzeit, wenn es ein Polynom p gibt, so dass f von M inZeit p berechnet wird. Sei

FP “ t f | f wird in Polynomialzeit berechnet u

P “

A Ď Nkˇ

ˇχA P FP(

12 / 44

Beispiel

1. Jedes Polynom ist in FP

2. Sei exppxq “ 2x . Dann ist exp R FP, da die Funktionswerte zugroß sind. Es ist |2x | “ x ` 1 ě 2|x |´1 ` 1. Somit wachst dieLange des Funktionswerts exponentiell mit der Lange derEingabe. Eine Turingmaschine benotigt also mindestens2|x |´1 ` 1 Schritte, allein um den Funktionswert 2x auf dasBand zu schreiben.

3. Beachte aber, dass

px , y , zq P N3ˇ

ˇ xy “ z(

P P.

13 / 44

Lemma

1. Die Klasse FP ist unter Komposition abgeschlossen.

2. P ist unter Vereinigung, Durchschnitt und Komplementbildungabgeschlossen.

3. Insbesondere ist wenn A P P auch A P P.

Beweis.Vorlesung.

14 / 44

Beobachtung

Wie erwahnt ist jede Mehrbandturingmaschine durch eineEinbandmaschine in quadratischer Zeit simulierbar. Fur P und FPist es also egal, welches Modell wir betrachten.

15 / 44

Als Nachstes wollen wir uns der Komplexitat entscheidbarerProbleme zuwenden. Wir werden insbesondere sehen, dass diemoglicherweise große Laufzeit von Rechnungen nichtnotwendigerweise durch einen langen Ausgabeprozess bedingt ist,sondern bei 0-1-wertigen Funktionen auftritt und also einecharakteristische Große von Problemen ist, so wie es auch bei derUnentscheidbarkeit der Fall war.

16 / 44

Vorher wollen wir aber noch einige Beispiele von in Polynomzeitentscheidbaren Problemen auflisten. Sie treten alle in derGraphentheorie auf. Sei G “ pV ,E q ein endlicher ungerichteterGraph. Ohne Einschrankung sei V “ t1, . . . ,mu. Jeder endlicheGraph ist vollstandig durch seine Adjazenzmatrix

¨

˚

˝

δ11 . . . δ1m...

. . ....

δm1 . . . δmm

˛

‹

‚

mit δi ,j “

#

1, falls pi , jq P E

0, sonst.

beschrieben. Diese Matrix kann als Wort

wG “ δ11δ12 . . . δ1mδ21 . . . δ2m . . . δm1 . . . δmm

in eine Turingmaschine eingegeben werden.

17 / 44

Beispiel Kn...

18 / 44

Definition

1. k-FARB “ tG |G ist mit k Farben farbbar u

2. ZH “ tG |G ist zusammenhangend u

3. EK “ tG |G besitzt einen Eulerkreis u

LemmaDie Probleme 2-FARB, ZH und EK sind in Zeit Opn2q entscheidbar,also insbesondere in P.

19 / 44

Allerdings gibt es auch Probleme, die zwar ahnlich aussehen, aberfur die kein Polynomzeitalgorithmus bekannt ist.

§ Das Problem k-FARB, fur k ą 2.

§ Das Problem HK “ tG |G besitzt Hamiltonkreis u.

§ Das Problem SOS (sum of subsets) mit

SOS “

t pa1, . . . , am, bq | Dc1, . . . , cm P t0, 1u : přm

i“1 ciai “ bq u

20 / 44

Allen betrachteten Problemen ist Struktur gemeinsam:

§ pt1, . . . ,mu ,K q P k-FARB ðñ

pDpa1, . . . , amq P t1, . . . , kumq

^ p@iqp@jqpti , ju P K ùñ ai ‰ ajq

§ pt1, . . . ,mu ,K q P HK ðñ

pDpv1, v2, . . . , vmqq tv1, . . . , vmu “ t1, . . . ,mu

^ p@1 ď i ă mq tvi , vi`1u P K ^ tvm, v1u P K

§ pa1, . . . , am, bq P SOS ðñ

pDc1, . . . , cm P t0, 1uqmÿ

i“1

ciai “ b.

D.h. kennen wir eine Losung, konnen wir diese einfach uberprufen.

21 / 44

Hierbei ist die Lange der Beschreibung der Losung ein Polynom p inder Lange der Eingabe. In den obigen Beispielen kann ppnq “ ngewahlt werden. Die Korrektheit der Losung, d.h. die Gultigkeit derForderung an die Losung, kann in Polynomzeit uberpruft werden.Wir wollen nun die Klasse NP der durch diese Eigenschaftencharakterisierten Probleme naher untersuchen.

22 / 44

Definition (NP)

Eine Menge A ist in NP, wenn es ein Polynom p und eine MengeB P P gibt, so dass fur alle x P N gilt:

x P A ðñ Dy : r|y | ď pp|x |q ^ px , yq P Bs .

23 / 44

Kurzer Exkurs: Dies ist vergleichbar mit folgender Charakterisierungvon semi-entscheidbar und entscheidbar.

SatzEine Menge A ist genau dann rekursiv aufzahlbar, wenn es eineentscheidbare Menge B gibt, so daß

x P A ðñ Dy : xx , yy P B

24 / 44

SatzEs gilt P Ď NP.

Beweis.Sei A P P beliebig. Wahle ppnq “ n und B “ Aˆ t0u. Damit gilt:

x P A ðñ px , 0q P B

ðñ Dy : r|y | ď |x | ^ px , yq P Bs .

Also ist A P NP

25 / 44

LemmaFur k ě 3 sind k-FARB,HK, SOS P NP

26 / 44

SatzDie Klasse NP ist abgeschlossen unter Vereinigung undDurchschnitt, d.h., es gilt:

A,B P NP ùñ AY B,AX B P NP

Es ist nicht klar, ob NP unter Komplementen abgeschlossen ist.

27 / 44

Beobachtung

Eine große offene Frage ist

P?“ NP

Außer den oben aufgefuhrten Problemen sind noch zahlreicheProbleme aus so wichtigen Gebieten wie Kostenoptimierung,Transportplanung, Lagerhaltung und Stundenplanerstellung, um nureinige zu nennen, in NP. Fur viele ist bisher nicht bekannt, ob sie inP sind.

28 / 44

Auf Grund der Definition der Klasse NP ist klar, dass man beieinem Problem A P NP zur Entscheidung der Frage, ob x P A ist,die Menge der potentiellen Losungen durchmustern kann, umfestzustellen, ob es eine korrekte Losung gibt. Fur NP-Probleme,von denen wir nicht wissen, ob sie in P sind, ist kein anderesVerfahren bekannt, als das mehr oder weniger geschickteDurchmustern aller moglicher Losungen. Davon gibt es aber 2ppnq

viele. Ist insbesondere x R A, so kann dies erst nach Durchlaufendieses exponentiell großen Suchraumes festgestellt werden.

DefinitionSei EXP die Gesamtheit der Mengen A Ď Nm m ě 1, fur die es einPolynom p gibt, so dass A in Zeit 2ppnq entschieden werden kann.

29 / 44

SatzEs gilt NP Ď EXP.

Ausserdem kann man zeigen, daß:

SatzEs gilt P Ĺ EXP.

Es ist aber nicht klar, ob

1. P “ NP

2. NP “ EXP

3. P Ĺ NP Ĺ EXP.

30 / 44

Eine Umfrage unter 100 fuhrenden Informatikern fuhrte zufolgendem Ergebnis:

1. 61 denken P ‰ NP.

2. 9 denken P “ NP.

3. 4 denken es ist unabhangig von ZFC.

4. 3 sagten einfach nur nicht unabhangig von der PeanoArithmetik.

5. 5 sagten daß es vom Modell abhangt.

6. 22 hatten keine Meinung.

31 / 44

Und bis wann?

2002–2009 52010–2019 122020–2029 132030–2039 102040–2049 52050–2059 122060–2069 42070–2079 02080–2089 12090–2099 02100–2110 72110–2199 02200–3000 5

32 / 44

Im folgenden wollen wir noch eine alternative Charakterisierung vonNP geben; via nichtdeterministischen Turingmaschinen. Nochmalszur Erinnerung: eine nichtdeterministische Turingmaschine istaufgebaut wie eine normale Turingmaschine, allerdings haben wirkeine Ubergansfunktion, sondern eine Ubergangsrelation. Somit gibtes zu einer Konfiguration oft mehrere Nachfolgekonfigurationen.

33 / 44

Wie wollen wir nun Zeitkomplexitat ins Spiel bringen?

DefinitionEine nichtdeterministische Turingmaschine akzeptiert eine MengeAk Ă N in polynomieller Zeit p, falls jede akzeptierende Rechnungbei Eingabe binpx1q# . . .# binpxkq P A hochstenspp|x1| ` ¨ ¨ ¨ ` |xk |q Schritte benotigt.

34 / 44

Wie wollen wir nun Zeitkomplexitat ins Spiel bringen?

DefinitionEine nichtdeterministische Turingmaschine akzeptiert eine MengeAk Ă N in polynomieller Zeit p, falls jede akzeptierende Rechnungbei Eingabe binpx1q# . . .# binpxkq P A hochstenspp|x1| ` ¨ ¨ ¨ ` |xk |q Schritte benotigt.

34 / 44

SatzDie folgenden Aussagen sind aquivalent:

1. A P NP

2. Es gibt eine nichtdeterministischen Turingmaschine N und einPolynom p mit naturlichen Zahlen als Koeffizienten, so dass Ndie Menge A in Zeit p akzeptiert.

35 / 44

Wenn man schon P “ NP? nicht entscheiden kann, hat dannzumindest NP eine Struktur, die man untersuchen kann?

36 / 44

Definition (Polynomzeitreduzierbarkeit)

Seien A,B Ď N.

1. A ist polynomzeitreduzierbar auf B, wenn es eine Funktionf P FP mit cA “ cB ˝ f gibt. Wir schreiben dann A ďp B.

2. A ”p B ðñ A ďp B ^ B ďp A.

37 / 44

Beispiel: 3-FARB ďp 4-FARB.

38 / 44

LemmaDie Relation ďp ist reflexiv und transitiv.

Ferner gilt:

Satz

1. B P P^ A ďp B ùñ A P P

2. B P NP^ A ďp B ùñ A P NP

39 / 44

Das nachste Resultat zeigt, dass die Mengen aus P die einfachstenMengen in NP sind.

SatzSeien H,N ‰ B und A P P. Dann ist A ďp B.

KorollarSind A,B nichtleere Mengen in P, die nicht schon N sind, so istA ”p B.

40 / 44

DefinitionEine Menge B heißt NP-vollstandig, wenn

§ B P NP ist und

§ fur alle A P NP gilt, so dass A ďp B.

Oft spricht man von

41 / 44

Zunachst einmal wissen wir naturlich nicht, dass es solche Mengenuberhaupt gibt. Das nachste Resultat zeigt u.a. die Bedeutung vonNP-vollstandigen Mengen bei der Losung der Frage, ob P “ NP.

SatzSei B NP-vollstandig. Dann gilt:

1. B P P ðñ P “ NP

2. p@C P NPq“

B ďp C ùñ C ist NP-vollstandig‰

.

42 / 44

Die folgenden Probleme sind als NP-vollstandig bekannt.

1. SAT

2. 3-SAT

3. Cliquen-Problem

4. Knotenuberdeckunsproblem

5. Hamiltonkreisproblem

6. Traveling Salesman

43 / 44

Wir zeigen NP-Vollstandigkeit der Aussagen 1,3,4 indem wir

§ zeigen daß SAT NP-vollstandig ist,

§ SAT ďp Cliquen-Problem, und

§ Cliquen-Problem ďp Knotenuberdeckunsproblem.

44 / 44