WEBVTT

00:10.070 --> 00:11.110
Ja, guten Tag.

00:12.090 --> 00:18.130
Ich begrüße Sie zur letzten regulären Vorlesung von mir.

00:19.010 --> 00:20.390
Also es wird jetzt weiter so abläufen.

00:20.490 --> 00:26.170
Heute kommt noch eine Reduktion, eine heftige oder zwei, eine heftige

00:26.170 --> 00:27.330
und eine einfache.

00:29.530 --> 00:31.110
Dann machen wir Übung.

00:32.390 --> 00:35.450
Nächste Woche machen wir Wiederholungen von dem Stoff aus dem

00:35.450 --> 00:35.790
Schöning.

00:35.790 --> 00:41.730
Also Chomsky-Hierarchie, Berechenbarkeit, Komplexitätstheorie.

00:43.530 --> 00:49.990
Und in den ersten beiden Februarwochen macht mein Postdoc Simon Gock

00:49.990 --> 00:51.430
die Informationstheorie.

00:52.190 --> 00:55.170
Der ist da eigentlich der Experte, weil er sich mit komprimierten

00:55.170 --> 00:57.810
Datenstrukturen und sowas sehr gut auskennt.

00:58.650 --> 01:03.410
Und will sich da auch mal vor einer größeren Hörerschaft beweisen.

01:03.410 --> 01:05.990
Ich hoffe, dass die dann auch wieder größer wird.

01:06.870 --> 01:08.010
Neues Spiel, neues Glück.

01:09.070 --> 01:10.310
Genauso prüfungsrelevant.

01:12.630 --> 01:16.490
Bei der Wiederholung könnte vielleicht auch gut sein, da anwesend zu

01:16.490 --> 01:21.490
sein, weil mir da vielleicht auch irgendwie Tipps rausrutschen, was in

01:21.490 --> 01:24.570
der Klausur wichtig ist und was nicht.

01:25.570 --> 01:28.730
Ja, gut.

01:31.850 --> 01:37.710
Wir hatten hier immer diese schönen Bilder mit Ableitungen.

01:44.540 --> 01:48.240
Wir haben ja hier mal über diese Beispiele Hamilton Circle Traveling

01:48.240 --> 01:49.660
Salesman Problemen geredet.

01:50.360 --> 01:59.840
Aber uns fehlt eigentlich noch der Beweis, dass Hamilton Circle NPH

01:59.840 --> 02:00.200
ist.

02:00.340 --> 02:02.020
Und das machen wir aber auf einem kleinen Umweg.

02:02.120 --> 02:04.780
Wir machen das erstmal für den gerichteten Fall.

02:08.040 --> 02:11.480
Also was ist das gerichtete Hamilton Circle Problem?

02:16.870 --> 02:22.510
Wir haben die Menge aller gerichteten Graphen, also die Sprache ist

02:22.510 --> 02:28.670
die geeignete Kodierung der Menge aller gerichteten Graphen, der

02:28.670 --> 02:32.190
Eigenschaft, dass es einen Kreis gibt, der jeden Knoten genau einmal

02:32.190 --> 02:32.670
besucht.

02:32.670 --> 02:46.520
Das ist das gleiche wie beim ungerichteten Fall, nur man kann ja einen

02:46.520 --> 02:51.360
ungerichteten Graphen natürlich auch in einen gerichteten übersetzen.

02:51.520 --> 02:54.400
Also in die Richtung ist es sowieso das gleiche.

02:54.980 --> 02:59.200
Außer dass es bei ganz kleinen Kreisen noch einen Unterschied gibt.

02:59.200 --> 03:00.840
Das interessiert hier glaube ich auch nicht.

03:02.560 --> 03:06.920
Aber im gerichteten Fall haben wir die Möglichkeit, Graphen

03:06.920 --> 03:10.460
einzugeben, wo es wirklich so ist, es gibt in die eine Richtung eine

03:10.460 --> 03:11.800
Kante, aber nicht in die Gegenrichtung.

03:12.260 --> 03:14.120
Und damit können wir noch mehr kodieren.

03:14.260 --> 03:17.600
Das heißt, das gerichtete Hamilton Circle Problem ist ein bisschen

03:17.600 --> 03:18.320
allgemeiner.

03:19.140 --> 03:25.580
Und damit ist es auch erstmal leicht, eine Reduktion anzugeben eines

03:25.580 --> 03:29.180
NP -harten Problems auf das gerichtete Hamilton Circle Problem.

03:31.620 --> 03:35.840
Was wir machen werden, ist, dass wir direkt das Dreisatzproblem auf

03:35.840 --> 03:40.920
gerichtetem Hamilton Circle reduzieren.

03:42.020 --> 03:48.820
Wir betrachten wieder eine normalisierte Formel, bei der jede Klausel

03:48.820 --> 03:50.500
genau drei Literale enthält.

03:52.820 --> 03:58.940
Die Klauseln werden von 1 bis M durchnummeriert, die Variablen von 1

03:58.940 --> 03:59.440
bis N.

04:00.260 --> 04:05.800
Und die Literale kriegen so einen Doppelindex, erst die Klauselnummer

04:05.800 --> 04:07.420
und dann die Position in der Klausel.

04:11.000 --> 04:18.920
Wir müssen für diese Reduktion eine Abbildung von den Dreisatzformeln

04:18.920 --> 04:20.040
in Graphen angeben.

04:20.420 --> 04:26.200
Das wird ein Graph sein mit N plus 6 mal M Knoten und geeigneten

04:26.200 --> 04:27.040
Kanten.

04:28.340 --> 04:30.780
Also was sieht man daran schon?

04:31.700 --> 04:40.240
Wir haben Knotengadgets, da werden Variablen-Gadgets, wo eine Variable

04:40.240 --> 04:42.200
direkt auf einen Knoten abgebildet wird.

04:42.680 --> 04:46.760
Wir haben Klausel-Gadgets, jede Klausel wird durch sechs Knoten

04:46.760 --> 04:48.220
repräsentiert.

04:48.220 --> 04:51.900
Und der Trick liegt jetzt natürlich daran, welche Kanten ich da

04:51.900 --> 04:53.480
reinbaue, sodass das genau passt.

04:53.740 --> 04:59.920
Das ist schon ein bisschen Knobelei, würde ich sagen, aber man kann es

04:59.920 --> 05:01.420
noch ganz gut erklären.

05:06.600 --> 05:08.940
Die Variablen-Gadgets sind ganz einfach.

05:11.240 --> 05:14.700
Für jede Variable haben wir einen Knoten.

05:15.140 --> 05:18.780
Es gibt zwei eingehende Kanten und zwei ausgehende.

05:20.660 --> 05:26.640
Eine ausgehende interpretieren wir, als diese Variable wird auf wahr

05:26.640 --> 05:27.060
gesetzt.

05:28.140 --> 05:31.160
Und eine andere interpretieren wir, als diese Variable wird auf falsch

05:31.160 --> 05:31.620
gesetzt.

05:35.880 --> 05:41.120
Das ist einfach, aber natürlich noch völlig unklar, wozu das gut sein

05:41.120 --> 05:41.440
soll.

05:42.420 --> 05:45.420
Ein bisschen mehr erkennt man schon an den Klausel-Gadgets.

05:48.690 --> 05:55.190
Wir haben diese sechs Knoten für jede Klausel, die so untereinander

05:55.190 --> 05:56.070
verbunden sind.

05:56.350 --> 06:00.050
Man hat also eine linke Seite, eine Eingangsseite und eine

06:00.050 --> 06:02.110
Ausgangsseite mit jeweils drei Knoten.

06:02.110 --> 06:07.310
Jeder dieser Knoten steht für ein Literal in der Klausel.

06:10.130 --> 06:14.270
Also immer zwei Knoten, einer auf der Eingangsseite, einer auf der

06:14.270 --> 06:16.970
Ausgangsseite steht für ein Literal.

06:17.450 --> 06:23.530
Dann sind die Knoten untereinander kreisförmig verbunden, sowohl auf

06:23.530 --> 06:25.650
der Eingangsseite als auch auf der Ausgangsseite.

06:27.670 --> 06:32.950
Und das klingt jetzt auf den ersten Blick auch mysteriös.

06:33.190 --> 06:34.170
Wozu ist das gut?

06:36.030 --> 06:41.810
Und dann muss man natürlich auch noch darüber reden, welche Kanten da

06:41.810 --> 06:42.610
rein und raus gehen.

06:47.850 --> 06:51.330
Aber wenn ich jetzt die Grundidee beschreibe, wird das Ganze

06:51.330 --> 06:53.770
vielleicht schon ein bisschen intuitiver.

06:53.770 --> 06:58.510
Die Grundidee ist, so ein Hamilton-Kreis soll ja jetzt sozusagen

06:58.510 --> 07:04.050
irgendwie die Erfüllbarkeit der Formel bezeugen.

07:04.590 --> 07:08.570
Die Idee ist, so ein Hamilton-Kreis betritt ein Gadget ein bis drei

07:08.570 --> 07:08.970
Mal.

07:12.150 --> 07:16.770
Und zwar, das hängt davon ab, wie viele von den Literalen wahr sind in

07:16.770 --> 07:19.050
der Belegung, die dieser Kreis repräsentiert.

07:20.930 --> 07:25.530
Und zwar, er betritt sie einmal für jedes erfüllte Literal.

07:29.500 --> 07:34.480
Und wir müssen außerdem sicherstellen, dass so ein Hamilton-Kreis,

07:35.080 --> 07:37.240
jeder Hamilton-Kreis,

07:41.100 --> 07:46.940
so ein Clausel-Gadget in der gleichen Zeile betritt wie verlässt.

07:48.800 --> 07:53.280
Und zwar gilt das sowohl, wenn das nur einmal passiert, als auch, wenn

07:53.280 --> 07:54.260
das mehrmals passiert.

07:54.600 --> 07:57.040
Er kann mehrmals betreten werden, aber es wird immer in der gleichen

07:57.040 --> 08:00.660
Zeile das Ganze verlassen.

08:05.380 --> 08:08.420
Das erklärt immer noch nicht ganz, wie das funktioniert, aber das ist

08:08.420 --> 08:09.640
jetzt eine sehr lokale Sicht.

08:10.040 --> 08:14.860
Wir müssen jetzt nur verstehen, warum dieses Gadget diese Eigenschaft

08:14.860 --> 08:15.140
hat.

08:16.140 --> 08:18.460
Und das ist ein sehr kleiner Teilgraf.

08:18.580 --> 08:20.960
Man muss nur gucken, was passiert hier lokal.

08:21.980 --> 08:26.920
Und das kann man durch vollständige Fallunterscheidung machen.

08:27.100 --> 08:30.440
Und das werden wir jetzt mehr oder weniger tun, ohne einen formalen

08:30.440 --> 08:30.920
Beweis.

08:35.540 --> 08:40.560
Ich gucke mir jetzt an, wie dürfen Hamilton-Kreise aussehen bezüglich

08:40.560 --> 08:43.200
eines solchen Gadgets.

08:44.080 --> 08:46.960
Und da gibt es sieben Fälle.

08:48.900 --> 08:52.020
Kann mir jemand sagen, warum sieben und warum nicht acht oder drei?

08:57.540 --> 08:59.500
Warum ist sieben hier eine magische Zahl?

09:10.590 --> 09:12.410
Und was hat das mit der Zahl sieben zu tun?

09:16.670 --> 09:20.890
Es gibt acht Belegungen für die drei Literale in der Clausel.

09:21.950 --> 09:29.070
Aber eine davon ist nicht erlaubt für eine erfüllte Formel, nämlich

09:29.070 --> 09:30.070
die, wo alle null sind.

09:32.550 --> 09:33.730
Gucken wir uns das mal an.

09:34.590 --> 09:38.770
Hier zum Beispiel nur literal drei ist wahr.

09:39.610 --> 09:41.970
Und dann muss ich natürlich dafür sorgen, in dem Hamilton-Kreis, dass

09:41.970 --> 09:44.690
alle anderen Knoten auch besucht werden.

09:44.790 --> 09:48.830
Das kann ich machen, indem ich hier auf der zyklischen Verbindung die

09:48.830 --> 09:49.930
anderen beiden besuche.

09:49.930 --> 09:53.410
Dann wechsle ich rüber, gehe wieder auf die zyklische Verbindung,

09:53.970 --> 09:54.830
verbinde die auch.

09:55.350 --> 09:58.390
Und völlig analog funktioniert das mit den anderen, wo immer nur eine

09:58.390 --> 09:59.330
Variable wahr ist.

09:59.390 --> 10:03.450
Zum Beispiel, wenn der in der Mitte reinkommt, geht der halt hier rum.

10:04.530 --> 10:07.990
Man hätte dieses Ding vielleicht auch irgendwie dreidimensional

10:07.990 --> 10:11.090
zeichnen sollen, sodass man sieht, dass das völlig symmetrisch ist.

10:12.290 --> 10:19.090
Ich habe zwei Dreiecke, die miteinander verbunden sind.

10:19.170 --> 10:20.750
Das sind gleichseitige Dreiecke.

10:21.250 --> 10:24.030
Und je nachdem, wie ich das Ganze drehe, ist das auch egal, wo jetzt

10:24.030 --> 10:25.370
ein Ding reingeht.

10:26.610 --> 10:31.370
Insofern könnte man hier die Fallunterscheidungen sogar noch mal

10:31.370 --> 10:32.110
reduzieren.

10:32.730 --> 10:35.610
Man muss sich dann wirklich nur angucken, in dem Fall, dass einer

10:35.610 --> 10:36.330
reingeht.

10:37.250 --> 10:38.970
Also die anderen, wo einer reingeht.

10:39.070 --> 10:42.350
Das ist der und der.

10:42.610 --> 10:46.430
Das sind einfach Verdrehungen von diesem Ding, wenn man das Ganze

10:46.430 --> 10:47.910
dreidimensional zeichnen würde.

10:48.770 --> 10:54.310
Dann gibt es mindestens einen, wo zwei reingehen, zum Beispiel hier

10:54.310 --> 10:54.990
oben und unten.

10:55.170 --> 10:57.470
Dann mache ich hier so einen kleinen Schlenker und habe dann die

10:57.470 --> 10:58.710
beiden anderen mit abgedeckt.

11:02.090 --> 11:04.690
Und da gibt es dann andere Varianten davon.

11:06.090 --> 11:10.450
Aber man kann sich da auch überlegen, bei einer dreidimensionalen

11:10.450 --> 11:13.070
Zeichnung wäre das einfach Verdrehungen dieses Literals.

11:13.570 --> 11:16.490
Und dann gibt es den ganz einfachen Fall, dass sie alle drei sind,

11:16.590 --> 11:17.750
dann geht es einfach so durch.

11:22.670 --> 11:27.170
Man muss ja dann immer so eine Genau-dann-wenn-Bedingung machen.

11:27.410 --> 11:31.250
Also was wir hier jetzt zumindest lokal schon mal gezeigt haben auf

11:31.250 --> 11:37.230
dieser Folie ist, wenn es eine erfüllende Belegung gibt, dann kann ich

11:37.230 --> 11:41.790
auch solche Teile von Hamilton-Kreisen bauen, die die geforderten

11:41.790 --> 11:42.790
Eigenschaften haben.

11:43.490 --> 11:47.850
Aber damit da nichts schief geht in der anderen Richtung, ich will ja

11:47.850 --> 11:51.510
in der anderen Richtung auch, wenn es einen Hamilton-Kreis gibt, eine

11:51.510 --> 11:53.330
erfüllende Belegung ablesen können.

11:53.750 --> 11:59.170
Dafür muss ich ausschließen, dass es Hamilton-Kreise gibt, die diesen

11:59.170 --> 12:00.190
Regeln nicht genügen.

12:00.510 --> 12:06.890
Also zum Beispiel, der oben reingeht und unten wieder raus oder so,

12:06.990 --> 12:10.110
weil dann würde die restliche Konstruktion auch nicht funktionieren.

12:10.750 --> 12:13.050
Da muss man dann eine Fallunterscheidung machen.

12:15.150 --> 12:16.370
Kann das passieren?

12:18.570 --> 12:20.230
Gucken wir uns mal ein Beispiel an.

12:20.370 --> 12:24.790
Also könnte es sein, dass es einen Hamilton-Kreis gibt, wo der Kreis

12:24.790 --> 12:29.050
oben reinkommt, einen runter geht und rechts wieder raus geht.

12:30.430 --> 12:32.610
Und dann könnte es natürlich sein, dass zum Beispiel die beiden

12:32.610 --> 12:36.530
anderen dann abgedeckt werden, indem hier was durchgeht.

12:36.530 --> 12:41.130
Aber was völlig klar ist, es gibt dann keine Chance, diesen Knoten

12:41.130 --> 12:41.950
noch zu besuchen.

12:42.590 --> 12:45.570
Weil der hat nur zwei eingehende Knoten, die sind aber beide von

12:45.570 --> 12:48.090
diesem roten Pfad schon abgedeckt.

12:48.990 --> 12:52.890
Das heißt, es gibt keine weitere Möglichkeit, zu diesem Knoten

12:52.890 --> 12:53.490
hinzukommen.

12:54.030 --> 12:57.910
Und das heißt auch, es gibt keinen Hamilton-Pfad, der so etwas hier

12:57.910 --> 12:59.210
als Teilpfad enthält.

13:00.230 --> 13:02.390
Und das kann man jetzt durchichsen.

13:02.570 --> 13:04.290
Also was für Pfade können hier noch passieren?

13:04.290 --> 13:07.470
Jetzt nehmen wir mal alle Möglichkeiten, dass der hier von oben kommt

13:07.470 --> 13:10.430
und dass er von der Mitte oder von unten kommt.

13:10.510 --> 13:13.230
Das sind wieder symmetrische Fälle, die ich jetzt nicht extra

13:13.230 --> 13:14.050
betrachten muss.

13:14.850 --> 13:17.650
Jetzt habe ich hier den Fall, er geht runter rechts.

13:18.350 --> 13:24.130
Hier habe ich den Fall runter, runter und dann bleibt nur noch rechts.

13:26.310 --> 13:28.610
Und dann gibt es hier wieder eine Fallunterscheidung, er kann hier

13:28.610 --> 13:29.370
rechts gehen.

13:29.790 --> 13:33.050
Und in dem Fall sieht man, die beiden können nicht erreicht werden.

13:33.530 --> 13:37.670
Oder hier runter rechts und dann nach oben.

13:38.610 --> 13:40.950
Dann kann ich hier irgendwie sowas machen, dann kann der nicht

13:40.950 --> 13:41.550
erreicht werden.

13:41.650 --> 13:42.430
Und so geht das weiter.

13:42.570 --> 13:45.390
Ich will das jetzt gar nicht im Einzelnen alles durchprobieren.

13:45.730 --> 13:48.010
Aber man kann sich hier davon überzeugen, dass es in diesem Gadget

13:48.010 --> 13:54.710
keine Hamilton-Pfade geben kann, die nicht dieser Regel entsprechen,

13:54.870 --> 13:59.630
dass die Teile des Hamilton-Pfades immer in der gleichen Zeile rein

13:59.630 --> 14:00.430
wie rausgehen.

14:02.390 --> 14:03.750
Gibt es dazu Fragen?

14:08.640 --> 14:12.260
Jetzt kommt der schwierigste Teil, den ich letztes Mal dann auch nicht

14:12.260 --> 14:13.000
verstanden hatte.

14:13.000 --> 14:21.320
Jetzt muss ich diese Gadgets so hintereinander hängen, dass die

14:21.320 --> 14:28.080
Gesamteigenschaft von diesem Graphen die ist, diese Formel zu

14:28.080 --> 14:28.540
kodieren.

14:31.120 --> 14:33.620
Jetzt müssen wir uns eine Minute Zeit nehmen.

14:37.800 --> 14:40.280
Aber die Idee ist eigentlich ganz einfach.

14:40.400 --> 14:43.060
Wir hängen immer Gadgets zusammen.

14:46.660 --> 14:50.900
Also für jede Variable gucken wir uns den Fall an, die ist entweder

14:50.900 --> 14:51.780
wahr oder falsch.

14:51.780 --> 14:59.620
Wenn ich die jetzt wahrsetze, dann laufe ich durch alle Klauseln, in

14:59.620 --> 15:08.380
denen diese Variable positiv vorkommt, also die, die wahrgemacht

15:08.380 --> 15:11.040
werden, wenn ich die Variable wahrmache, laufe ich dadurch

15:11.040 --> 15:12.380
nacheinander durch.

15:15.140 --> 15:16.560
Und zwar wie laufe ich dadurch?

15:17.640 --> 15:20.700
Ich betrete das immer an der Stelle, wo diese Variable ist.

15:23.340 --> 15:25.160
Formal kann ich das jetzt so formulieren.

15:25.720 --> 15:28.160
Genau, analog das Ganze für den negierten Teil.

15:31.560 --> 15:39.320
Also sei jetzt j1 bis jk die Menge der Klauselnummern, in denen das

15:39.320 --> 15:40.580
Literal zi vorkommt.

15:41.740 --> 15:44.660
Das zi ist jetzt entweder xi oder nicht xi.

15:51.650 --> 15:55.370
Und dann gucke ich mir noch genauer an, an welchen Positionen kommt

15:55.370 --> 15:56.690
dann dieses zi jeweils vor.

15:56.790 --> 15:58.270
Das ist p1 bis pk.

15:59.130 --> 16:04.050
Und dann sorge ich dafür, dass es in dem Graphen einen Pfad gibt, xi.

16:14.100 --> 16:15.380
Und dann...

16:16.460 --> 16:19.920
Genau, das ist jetzt für den Fall zi gleich xi.

16:20.660 --> 16:26.980
Dann gibt es einen Pfad xi, also der Knoten, der die Variable xi

16:26.980 --> 16:35.180
repräsentiert, nach lp1j1, lp1j1, lp1j1.

16:35.920 --> 16:39.580
Also l war immer die linke Seite, l die rechte Seite.

16:41.800 --> 16:45.100
Und dann, also das ist klar, es gibt da immer eine Kante.

16:45.560 --> 16:59.520
Also ich verbinde jetzt xi mit dem ersten Gadget, in dem xi positiv

16:59.520 --> 17:00.160
vorkommt.

17:02.580 --> 17:06.920
Und zwar an der Stelle, also ich gehe an der Stelle rein, wo halt auch

17:06.920 --> 17:08.700
das Literal in der Formel steht.

17:09.560 --> 17:12.560
Dann gibt es sowieso, die Kante gibt es sowieso, das ist bereits

17:12.560 --> 17:14.060
Definition des Gadgets.

17:14.940 --> 17:19.880
Und dann, das Wichtige ist, das nächste Gadget, das ich betrete, also

17:19.880 --> 17:22.860
ich gehe dann zum Beispiel, wenn das hier steht, gehe ich hier durch,

17:23.280 --> 17:25.540
gehe dann hier wieder raus und wo führt das hin?

17:26.200 --> 17:31.440
Das ist das nächste Vorkommen des gleichen Literals, das hier stand.

17:33.500 --> 17:38.780
Also ich gucke mir die nächste Klausel an, in der das gleiche Literal

17:38.780 --> 17:39.780
vorkam wie hier.

17:41.980 --> 17:45.400
Es war in der gleichen Richtung, positiv oder negativ.

17:46.660 --> 17:48.520
Und dann gehe ich da an der Stelle rein.

17:48.980 --> 17:53.920
Und wenn es keins mehr gibt, dann gehe ich zur nächsten Variable.

17:56.140 --> 17:57.600
Jetzt steht hier noch mod n.

17:58.240 --> 17:59.620
Das Ganze mache ich zweimal.

18:01.160 --> 18:04.280
Ich gehe einmal ganz durch, dann habe ich alle Variablen abgehakt.

18:06.280 --> 18:08.820
Und wenn ich ganz am Ende bin, gehe ich wieder zurück.

18:10.880 --> 18:14.880
Und das Gleiche mache ich auch für die negierten Vorkommen einer

18:14.880 --> 18:15.080
Variable.

18:17.800 --> 18:19.840
Jetzt gucken wir uns am besten mal ein Beispiel an.

18:20.300 --> 18:22.040
Das ist auf den ersten Blick auch nicht übersichtlicher.

18:25.140 --> 18:29.840
Aber wenn man sich jetzt ein paar Minuten Zeit nimmt, ist es doch

18:29.840 --> 18:30.700
nicht so schwierig.

18:31.280 --> 18:33.880
Wir haben hier eine Formel mit drei Klauseln.

18:35.660 --> 18:40.680
Und wenig überraschend drei Klausel-Gadgets.

18:41.740 --> 18:43.780
Wir haben fünf Variablen.

18:45.360 --> 18:49.560
Und ebenso wenig überraschend fünf Variablen-Knoten.

18:49.640 --> 18:51.260
Eins, zwei, drei, vier, fünf.

18:53.380 --> 18:56.580
Was für Kanten haben wir jetzt zusätzlich?

18:57.020 --> 19:00.120
Oder wie verbinden wir diese Teile miteinander?

19:00.560 --> 19:03.200
Fangen wir mal bei der Variable x1 an.

19:04.920 --> 19:09.900
x1 tritt positiv auf in Klausel 1.

19:10.580 --> 19:11.820
Und zwar an der ersten Stelle.

19:12.140 --> 19:19.220
Folglich gibt es eine Kante von Variable 1 zum obersten Zeile von dem

19:19.220 --> 19:20.460
Klausel -Gadget 1.

19:22.080 --> 19:24.640
Dann gehe ich zu der rechten Seite von dem Gadget.

19:25.060 --> 19:27.180
Und jetzt ist die Frage, wo gehe ich als nächstes hin?

19:27.880 --> 19:31.020
Dafür muss ich gucken, tritt das x1 noch irgendwo auf?

19:31.880 --> 19:34.680
Nein, also es tritt negiert auf, weil es interessiert mich jetzt

19:34.680 --> 19:34.920
nicht.

19:35.300 --> 19:39.120
Also gehe ich zum nächsten Variablen, x2.

19:40.200 --> 19:43.240
Jetzt, x2, tritt das irgendwo positiv auf?

19:43.840 --> 19:48.520
Nein, wirklich gehe ich direkt weiter zu x3.

19:48.520 --> 19:50.900
Tritt x3 irgendwo positiv auf?

19:51.100 --> 19:51.720
Auch nicht.

19:52.220 --> 19:54.020
Gehe direkt weiter zu x4.

19:55.020 --> 19:57.600
Tritt x4 irgendwo positiv auf?

19:57.760 --> 19:59.920
Jawohl, in Klausel 4.

20:01.500 --> 20:03.260
Und zwar an der letzten Stelle.

20:03.440 --> 20:11.560
Deshalb gibt es eine Kante zur untersten Zeile von Klausel 2.

20:12.200 --> 20:15.080
Was ist das nächste Auftreten von x4?

20:15.180 --> 20:15.780
Gibt es nicht.

20:15.780 --> 20:19.120
Folglich gehe ich von da zur Variablen x5.

20:21.180 --> 20:23.740
Tritt x5 irgendwo positiv auf?

20:23.800 --> 20:26.840
Jawohl, ganz hinten in Klausel 1.

20:26.980 --> 20:32.300
Also gibt es eine Kante hier rüber zur untersten Zeile von Klausel

20:32.300 --> 20:33.260
Gadget 1.

20:34.040 --> 20:35.480
Tritt x5 nochmal auf?

20:35.600 --> 20:37.480
Jawohl, in Klausel 2.

20:38.120 --> 20:39.260
Und zwar an der zweiten Stelle.

20:39.420 --> 20:40.560
Deshalb gibt es diese Kante.

20:41.100 --> 20:42.720
Tritt es nochmal auf?

20:42.720 --> 20:43.540
Nein.

20:44.140 --> 20:45.740
Gehe ich zur Variablen x6?

20:46.320 --> 20:47.320
Nee, gibt es nicht.

20:47.680 --> 20:50.080
6 modulo 5 ist 1.

20:50.680 --> 20:52.520
Gehe zurück zur Variablen x1.

20:53.580 --> 20:57.720
Das gleiche Spiel mache ich mit den negierten Literalen.

20:59.160 --> 21:02.680
x1 tritt negiert das erste Mal auf in Klausel 2.

21:03.260 --> 21:07.720
Deshalb gibt es hier eine Kante zu Klausel 2.

21:07.820 --> 21:09.040
Und zwar in der ersten Zeile.

21:10.880 --> 21:12.620
Tritt x1 nochmal auf?

21:12.760 --> 21:13.100
Nein.

21:13.840 --> 21:16.170
Folglich geht es hier weiter zu Variablen x2.

21:18.560 --> 21:22.920
Nicht x2 tritt das erste Mal auf in Klausel 3.

21:23.340 --> 21:29.000
Deshalb gibt es hier eine Kante zu Klausel 2.

21:29.840 --> 21:30.960
Wo ist die nächste vorkommen?

21:31.040 --> 21:32.160
Oh, das kommt zweimal vor.

21:32.280 --> 21:33.600
Deshalb gibt es hier diese Kante.

21:34.580 --> 21:37.020
Dann gehe ich weiter zu Variablen x3 usw.

21:41.360 --> 21:42.780
Also das ist diese Vorschrift.

21:43.000 --> 21:46.720
Man geht sowohl für die positiven als auch für die negativen Literale

21:46.720 --> 21:51.820
einer Variablen durch alle Klausel-Gadgets, in denen das vorkommt.

21:51.900 --> 21:55.260
Und zwar geht man an der Stelle rein, an der Stelle, wo die vorkommen.

21:56.860 --> 21:59.940
Wenn es keine weiteren vorkommen gibt, gehe ich zunächst in Variablen.

22:00.340 --> 22:03.120
Wenn es keine weitere Variable gibt, gehe ich zurück zu x1.

22:05.140 --> 22:08.440
Und ich habe jetzt hier in dem Beispiel rot eingezeichnet einen

22:08.440 --> 22:09.200
Hamilton Pfad.

22:11.300 --> 22:14.080
Der die Erfüllbarkeit bezeugt.

22:14.180 --> 22:18.060
Also wir können jetzt erstmal hergehen und gucken, jeder Knoten hat

22:18.060 --> 22:24.180
tatsächlich eine eingehende rote Kante, eine ausgehende rote Kante.

22:25.200 --> 22:26.780
Ist damit schon ein Hamilton Pfad?

22:26.940 --> 22:28.660
Nein, es könnten irgendwie mehrere sein.

22:29.160 --> 22:30.920
Aber man kann jetzt halt auch wirklich hier durchgehen.

22:31.660 --> 22:36.300
So, so, man landet wirklich überall.

22:37.960 --> 22:39.660
Das heißt, man hat alles abgedeckt.

22:41.560 --> 22:43.660
Also wir sehen, dieses Ding hat einen Hamilton Pfad.

22:44.860 --> 22:46.400
Und jetzt ist ja die eine Richtung.

22:46.540 --> 22:51.160
Wir wollen aus einem Hamilton Pfad ablesen, eine erfüllende Belegung.

22:53.200 --> 22:54.400
Das kann man hier auch.

22:55.360 --> 23:04.100
Weil ich sehe, zum Beispiel x1, der Hamilton Pfad geht zu einem

23:04.100 --> 23:08.340
Knoten, der ein negiertes Literal repräsentiert.

23:08.500 --> 23:10.260
Nämlich zu diesem Nicht-x1 hier.

23:10.880 --> 23:13.280
Das heißt, x1 ist falsch.

23:15.620 --> 23:20.860
x1 wird auf 0 gesetzt und erfüllt damit diese Klausel, weil hier ja

23:20.860 --> 23:23.620
Nicht -x1 eine Möglichkeit ist.

23:25.800 --> 23:29.640
Dann gehe ich weiter, lande bei Variable x2.

23:31.700 --> 23:35.820
Und die rote Kante geht hier zum Klausel 3.

23:36.600 --> 23:38.220
Da tritt es auch negiert auf.

23:38.340 --> 23:40.200
Das heißt, x2 ist auch falsch.

23:42.040 --> 23:43.440
Sogar doppelt falsch.

23:43.760 --> 23:45.080
Aber das interessiert uns hier nicht.

23:45.800 --> 23:48.160
Dann geht es weiter zu Variablen x3.

23:54.210 --> 23:55.990
Jetzt müssen wir aufpassen.

24:01.640 --> 24:05.320
Genau, x3 kommt sowieso nur einmal vor und zwar negiert.

24:09.390 --> 24:11.610
Das war welche Kante?

24:11.730 --> 24:13.790
Das war die hier.

24:14.310 --> 24:15.670
Die wird aber nicht genommen.

24:16.970 --> 24:22.550
Das heißt, ich nehme die andere und die steht dafür, dass x3 wahr ist.

24:26.430 --> 24:29.430
Mir fällt jetzt gerade auf, diese Vorschrift.

24:29.970 --> 24:32.870
Da muss man sich überlegen, was mache ich denn, wenn ich hier eine

24:32.870 --> 24:35.730
Variable habe, die gar nicht in der Formel vorkommt.

24:37.030 --> 24:39.170
Ich meine, die Konstruktion sieht das gar nicht vor.

24:39.490 --> 24:43.530
Aber dann würden hier zwei parallele Kanten stehen, die ich eigentlich

24:43.530 --> 24:46.510
nicht haben darf bei einem einfachen Graphen.

24:46.930 --> 24:49.010
Aber kein Problem, weil das machen wir ja gar nicht.

24:50.310 --> 24:53.250
Trotzdem, wenn ich jetzt sagen würde, ich lasse das zu, dann habe ich

24:53.250 --> 24:57.010
da einen Multigraphen und dann kann ich mir eben tatsächlich auch

24:57.010 --> 24:59.670
aussuchen, welchen Wert ich für die Variable wähle.

25:02.970 --> 25:06.850
Also an der Tatsache, dass diese Kante hier gewählt wird und die steht

25:06.850 --> 25:11.210
im Endeffekt für das positive Literal, weiß ich, dass x3 gleich 1

25:11.210 --> 25:11.950
gesetzt wird.

25:12.970 --> 25:13.810
Jetzt gucken wir weiter.

25:15.270 --> 25:16.610
Hier bin ich bei x4.

25:17.450 --> 25:19.470
Und der Hamilton Pfad geht hier weiter.

25:19.650 --> 25:22.510
Das ist Klausel 2, letztes Literal.

25:22.990 --> 25:24.250
Da steht x4 positiv.

25:25.130 --> 25:27.310
Das heißt, x4 muss wahrgesetzt werden.

25:28.210 --> 25:31.670
Dann läuft er hier durch, geht weiter zu x5.

25:33.370 --> 25:35.130
Und dann weiter hierhin.

25:35.230 --> 25:37.430
Das ist ein positives Vorkommen von x5.

25:37.770 --> 25:39.610
Also muss auch x5 wahrgesetzt werden.

25:40.050 --> 25:43.610
Also habe ich da jetzt eine erfüllende Belegung abgelesen.

25:46.610 --> 25:47.310
Umgekehrt.

25:49.570 --> 25:53.850
Wenn ich eine erfüllende Belegung habe, möchte ich von der ablesen

25:53.850 --> 25:56.110
können, einen Hamilton Pfad.

25:57.790 --> 26:00.250
Nehmen wir zum Beispiel mal diese erfüllende Belegung.

26:01.390 --> 26:03.310
Die sagt x1 gleich 0.

26:05.170 --> 26:09.450
Das heißt, ich muss der Kante folgen, die zu einem negierten Vorkommen

26:09.450 --> 26:11.090
von der Variable führt.

26:11.830 --> 26:12.670
Wenn überhaupt.

26:12.790 --> 26:15.310
Wenn es die nicht gibt, gehe ich zur nächsten Variable mit meinem

26:15.310 --> 26:16.210
Hamilton Pfad.

26:16.310 --> 26:19.450
Das heißt, er sagt mir, nimm diese Kante für den Hamilton Pfad.

26:20.050 --> 26:26.370
Dann ist klar, ich gehe hier durch, lande dann automatisch bei der

26:26.370 --> 26:27.830
nächsten Variable.

26:29.650 --> 26:31.030
Dann fehlt da x2.

26:31.170 --> 26:32.690
Aha, x2 ist gleich 0.

26:32.790 --> 26:38.650
Dann muss ich gehen zu der ersten Klausel, die x2 negativ enthält.

26:38.650 --> 26:40.090
Das ist die.

26:42.970 --> 26:45.650
Da folge ich einfach dieser Kante.

26:46.570 --> 26:48.770
Das kann ich ganz mechanisch tun.

26:49.090 --> 26:50.510
Jetzt muss ich ein bisschen aufpassen.

26:55.440 --> 26:57.720
Also vielleicht ist das am einfachsten, das sich so zu überlegen,

26:57.800 --> 26:58.920
jetzt gehe ich erst mal weiter.

27:00.260 --> 27:05.000
Ich gehe direkt hier durch, lese dann weiter diese Sachen ab, bin dann

27:05.000 --> 27:09.860
sozusagen durch jede Klausel einmal durchgelaufen, weil die sind ja

27:09.860 --> 27:12.060
alle erfüllt, folglich habe ich jede einmal besucht.

27:12.480 --> 27:14.900
Aber es könnte sein, dass ich nicht alle Knoten besucht habe.

27:15.000 --> 27:19.440
Dann kann ich aber später hergehen und sagen, ich bin hier durch, hier

27:19.440 --> 27:22.640
durch, die beiden sind noch nicht besucht, aber wir haben ja gesehen,

27:22.780 --> 27:25.680
dass ich dann immer durch Umwege die auch noch abdecken kann.

27:27.880 --> 27:29.940
Also das wäre eine Möglichkeit, so etwas abzudecken.

27:30.440 --> 27:32.560
Gibt es dazu Fragen bis hierhin?

27:33.140 --> 27:34.800
Das machen wir jetzt als nächstes allgemein.

27:34.860 --> 27:38.640
Ich wollte es nur anhand des Beispiels erstmal einmal durchrechnen.

27:41.620 --> 27:45.760
Wir müssen jetzt formal den allgemeinen Beweis führen, wenn die Formel

27:45.760 --> 27:49.500
erfüllbar ist, dann ist die Instanz lösbar und umgekehrt.

27:53.590 --> 27:59.690
Wenn die Formel erfüllbar ist, heißt das, es gibt eine Belegung, die

27:59.690 --> 28:00.690
die Formel wahr macht.

28:01.470 --> 28:02.630
Die Belegung der Variablen.

28:03.190 --> 28:06.370
Und jetzt gucke ich mir einfach an, wenn eine Variable auf 1 gesetzt

28:06.370 --> 28:18.720
wird, x i gleich 1, dann baue ich jetzt ein Segment vom Hamilton-Kreis

28:18.720 --> 28:24.080
zwischen den Knoten x i und x i plus 1, indem ich die Gadgets

28:24.080 --> 28:31.560
durchlaufe, in denen x i in der entsprechenden Klausel vorkommt.

28:33.820 --> 28:38.360
Und dann kann man da jetzt interpretieren, ob ich mir gleich schon

28:38.360 --> 28:40.240
überlege, wer diese Umwege läuft.

28:40.600 --> 28:41.600
Aber besser erst mal nicht.

28:41.860 --> 28:43.480
Ich laufe einfach durch die Klauseln.

28:44.020 --> 28:48.800
Genauso, wenn x i gleich 0, laufe ich zwischen den Knoten x i und x i

28:48.800 --> 28:52.320
plus 1 die Gadgets, in denen das negativ vorkommt.

28:52.720 --> 28:57.020
Jetzt weiß ich, weil die Formel erfüllbar ist, wird jedes Gadget

28:57.020 --> 28:58.360
mindestens einmal durchlaufen.

28:59.540 --> 29:03.760
Und wir haben ja in dieser Fallunterscheidung gesehen, wie dieses

29:03.760 --> 29:07.720
Durchlaufen genau ablaufen muss, damit jeder Gadget-Knoten auch

29:07.720 --> 29:09.120
besucht wird.

29:11.580 --> 29:15.520
Und jeder variablen Knoten wird ohnehin einmal durchlaufen von dem so

29:15.520 --> 29:17.200
definierten Hamilton-Kreis.

29:20.400 --> 29:21.500
Fragen dazu?

29:26.260 --> 29:27.320
So umgekehrt.

29:28.080 --> 29:32.360
Wenn die Hamilton-Fahrtinstanz lösbar ist, müssen wir zeigen, dass

29:32.360 --> 29:33.840
dann noch die Formel erfüllbar ist.

29:34.200 --> 29:36.420
Dann schaue ich mir also den Hamilton-Kreis C an.

29:39.200 --> 29:44.020
Schaue dann zwischen den Variablen x i und x i plus 1, welche Gadgets

29:44.020 --> 29:44.940
durchläuft der.

29:48.300 --> 29:54.900
Und die Kanten sind schon so definiert, dass der nur Gadgets

29:54.900 --> 29:58.480
durchläuft, sodass in den entsprechenden Klauseln entweder nur

29:58.480 --> 30:07.240
positive oder nur negative Vorkommen von der Variablen x i drin sind.

30:08.060 --> 30:11.440
Und wenn das nur positive sind, setze ich die Variable auf 1.

30:12.660 --> 30:15.380
Und wenn es nur negative sind, setze ich sie auf falsch.

30:16.020 --> 30:20.040
Dadurch mache ich alle diese Klauseln erfüllbar, die dadurch laufen

30:20.040 --> 30:20.420
werden.

30:21.940 --> 30:24.760
Da das ein Hamilton-Kreis ist, wird insbesondere jedes Gadget

30:24.760 --> 30:26.440
mindestens einmal besucht.

30:27.820 --> 30:31.220
Das heißt, dadurch werden auch alle Klauseln erfüllt.

30:32.220 --> 30:33.100
Fragen dazu?

30:37.400 --> 30:40.580
So, jetzt haben wir das gerichtete Hamilton-Kreis-Problem gezeigt,

30:40.700 --> 30:41.700
dass das NP-hart ist.

30:42.320 --> 30:45.200
Und jetzt machen wir noch eine kleine Reduktion, die zeigt, dass das

30:45.200 --> 30:50.060
gerichtete Hamilton-Kreis-Problem polynomial reduzierbar ist auf das

30:50.060 --> 30:52.280
ungerichtete Hamilton-Kreis-Problem.

30:53.360 --> 30:54.480
Und das ist ziemlich simpel.

30:55.080 --> 30:59.360
Ich habe einfach ein Knotengadget, das jeden Knoten des gerichteten

30:59.360 --> 31:05.160
Graphen abbildet auf drei Knoten des ungerichteten Graphen.

31:05.160 --> 31:10.340
Ich male das jetzt mal so, dass von links die eingehenden Kanten des

31:10.340 --> 31:12.920
Knoten sind und nach rechts gehen die ausgehenden Kanten.

31:15.000 --> 31:17.080
Dann nehme ich hier drei Knoten.

31:18.180 --> 31:23.840
Der linke Knoten ist verbunden mit den Knoten, die die eingehenden

31:23.840 --> 31:24.820
Kanten beschreiben.

31:25.560 --> 31:29.080
Der rechte Knoten ist verbunden mit den Knoten, die die ausgehenden

31:29.080 --> 31:30.600
Kanten spezifizieren.

31:31.100 --> 31:34.200
Und dann habe ich noch so einen Pfad der Länge 2 zwischen den beiden

31:34.200 --> 31:35.480
mit einem Mittelknoten.

31:37.440 --> 31:38.700
Warum tut es das?

31:39.660 --> 31:45.620
Wir müssen zeigen, dass G einen Hamilton-Kreis hat, genau dann, wenn

31:45.620 --> 31:46.920
G' einen hat.

31:49.260 --> 31:53.500
Wenn der gerichtete Graph einen Hamilton-Kreis hat, kann ich direkt

31:54.200 --> 31:56.840
einen Hamilton-Kreis in dem ungerichteten ablesen.

31:57.820 --> 32:02.080
Wenn jetzt zum Beispiel der Kreis hier durchläuft über diese Kante

32:02.080 --> 32:08.100
rein, über die raus, dann nehme ich halt, aha, es ist diese Kante, ich

32:08.100 --> 32:10.520
durchlaufe diesen Pfad und laufe dann da raus.

32:12.260 --> 32:14.600
Also kann ich direkt ablesen.

32:17.080 --> 32:22.900
Umgekehrt, wenn G' einen Hamilton-Kreis hat, hat auch G einen.

32:23.000 --> 32:23.860
Warum ist das so?

32:24.200 --> 32:25.680
Mache ich einen Widerspruchsbeweis.

32:25.680 --> 32:30.520
Das Einzige, was schief gehen kann, nehmen wir mal an, es

32:33.620 --> 32:41.820
gibt einen Hamilton-Kreis durch ein Gadget, der nicht übersetzbar ist

32:41.820 --> 32:47.080
in Kanten, die auch den gerichteten Kanten entsprechen.

32:47.600 --> 32:52.520
Das wäre dann, ich denke OBDA, so was hier.

32:52.720 --> 32:58.400
Wir haben hier eine eingehende Kante des gerichteten Grafen und dann

32:58.400 --> 33:02.200
geht der ungerichtete hier raus für eine andere eingehende Kante, aber

33:02.200 --> 33:05.440
daraus kann ich keinen Pfad im gerichteten Grafen machen.

33:05.760 --> 33:06.480
Das ist doof.

33:07.180 --> 33:09.900
Das Analoge könnte auf der rechten Seite ja auch passieren, aber das

33:09.900 --> 33:10.960
ist völlig symmetrisch.

33:11.740 --> 33:13.200
Aber warum kann das nicht sein?

33:13.340 --> 33:16.520
Also nehmen wir mal an, das hier wäre ein Teil eines Hamilton-Kreises

33:18.540 --> 33:20.360
in dem ungerichteten Grafen.

33:20.360 --> 33:24.120
Dann ist es völlig unmöglich, dass dieser Knoten besucht wird.

33:24.980 --> 33:29.520
Kann natürlich sein, dass ein anderer Teil hier durchläuft, aber der

33:29.520 --> 33:32.880
kann nicht dahin, weil der könnte irgendwie hier rein, dann dahin und

33:32.880 --> 33:33.940
dann kommt er aber nicht zurück.

33:35.620 --> 33:39.900
Folglich kann das nicht sein, dass so ein Teilpfad hier Teil eines

33:39.900 --> 33:42.900
Hamilton -Kreises des ungerichteten Grafen ist.

33:45.480 --> 33:49.920
Das heißt, die haben immer diese schöne Form, es gibt eine Kante, eine

33:49.920 --> 33:51.880
eingehende Kante und eine ausgehende Kante.

33:52.800 --> 33:54.500
Das ist nochmal zu übersetzen.

33:54.580 --> 33:56.120
Wir haben hier einen ungerichteten Graf.

33:56.480 --> 34:00.220
Es gibt immer eine Kante des Hamilton-Kreises, die zu einer

34:00.220 --> 34:05.960
eingehenden Kante des gerichteten Grafen korrespondiert und eine Kante

34:05.960 --> 34:10.060
auf der rechten Seite zu einer ausgehenden Kante des gerichteten

34:10.060 --> 34:11.240
Grafen korrespondiert.

34:11.680 --> 34:17.160
Und deshalb kann ich von jedem Hamilton-Kreis durch G' sehr einfach

34:17.160 --> 34:20.020
auch wieder einen Hamilton-Kreis von G ablesen.

34:21.100 --> 34:22.080
Fragen dazu?

34:29.700 --> 34:35.360
Wir hatten bei Dreisat schon einen Exkurs, dass leicht veränderte

34:35.360 --> 34:38.200
Problemstellungen plötzlich doch wieder polynomiell sein können.

34:38.620 --> 34:41.480
Hier bietet sich an, sich das Eulatur-Problem anzuschauen.

34:42.300 --> 34:45.300
Wir wollen nicht mehr alle Knoten genau einmal besuchen, sondern alle

34:45.300 --> 34:45.740
Kanten.

34:48.980 --> 34:54.880
Wir wollen das Entscheidungsproblem für einen gegebenen ungerichteten

34:54.880 --> 34:55.980
Grafen entscheiden.

34:56.180 --> 34:59.740
Gibt es einen Kreis, der jede Kante genau einmal besucht?

35:00.280 --> 35:02.520
Das ist natürlich kein einfacher Kreis.

35:03.060 --> 35:05.000
Der darf Knoten durchaus mehrfach besuchen.

35:05.880 --> 35:11.540
Und da hat Herr Euler bereits 1736 gezeigt, dass G eine Eulatur hat,

35:11.980 --> 35:16.420
genau dann, wenn er erstens zusammenhängend ist und zweitens jeder

35:16.420 --> 35:18.760
Knoten geraden Grad hat.

35:21.020 --> 35:24.100
Und das lässt sich ganz leicht in polynomieller Zeit prüfen.

35:24.960 --> 35:28.500
Also diese Gradheit des Grades, das ist eine ganz einfache lokale

35:28.500 --> 35:32.360
Eigenschaft und die Eigenschaft, zusammenhängend zu sein, haben wir in

35:32.360 --> 35:35.220
Algorithmen 1, Linearzeitalgorithmen, kennengelernt.

35:41.620 --> 35:46.480
Damit haben wir alle Reduktionen gesehen, die ich jetzt für wirklich

35:46.480 --> 35:47.640
spannend halte.

35:47.820 --> 35:50.560
Also in Info 3 hatten wir noch eine Reduktion für das Set-Cover

35:50.560 --> 35:54.800
-Problem und für Steinerbäume

35:58.150 --> 36:06.410
und für Bin-Packing aber die sind jetzt für Coloring.

36:06.510 --> 36:07.730
Das heißt, Coloring hatten wir in der Übung.

36:09.610 --> 36:17.130
Also ich denke, das reicht jetzt auch an so klassischen Reduktionen.

36:17.970 --> 36:21.350
Jetzt wollen wir Ihnen mal nicht ganz so klassische Sachen vorführen,

36:21.910 --> 36:27.050
die auch wieder belegen, wie allgegenwärtig solche komplexen Probleme

36:27.050 --> 36:27.490
sind.

36:28.970 --> 36:31.750
Man kann sich überlegen, klassische Brettspiele.

36:34.650 --> 36:40.390
Da kann man immer fragen, gegeben eine Brettstellung, entscheiden Sie,

36:42.030 --> 36:44.270
kann ein Spieler gewinnen?

36:48.130 --> 36:53.050
Jetzt steht hier für allgemeinerter klassische Spiele.

36:53.210 --> 36:54.330
Warum steht das da?

36:54.690 --> 36:58.590
Kann mir jemand sagen, aus komplexitätstheoretischer Sicht, wie

36:58.590 --> 37:04.930
schwierig es ist, für Schach zu entscheiden, ob man gewinnen kann oder

37:04.930 --> 37:05.210
nicht?

37:10.150 --> 37:14.710
Es gibt nur konstant viele mögliche Schachpositionen.

37:15.130 --> 37:17.130
Kann ich eine große Tabelle machen?

37:17.630 --> 37:18.670
Gewonnen, nicht gewonnen?

37:19.390 --> 37:22.290
Kann sein, dass Sie da ein bisschen viel Speicher brauchen.

37:23.150 --> 37:29.250
Wahrscheinlich auch immer noch mehr, als selbst die NSA speichern

37:29.250 --> 37:29.510
kann.

37:31.750 --> 37:35.310
Aber aus komplexitätstheoretischer Sicht ist das alles Peanuts.

37:36.290 --> 37:40.350
Aber man kann jetzt hergehen und das Spiel verallgemeinern.

37:48.700 --> 37:54.620
Zum Beispiel könnte man sagen, wir haben jetzt ein NxN-Brett und muss

37:54.620 --> 37:57.300
sich dann bei Schach noch überlegen, was da dann in der untersten

37:57.300 --> 38:00.100
Zeile für Dinger stehen.

38:01.360 --> 38:06.040
Oder man könnte auch vielleicht bei acht Zeilen bleiben und aber ganz

38:06.040 --> 38:07.100
viel Spalten machen.

38:09.660 --> 38:12.780
Dann gibt es natürlich verschiedene Möglichkeiten, wie man das

38:12.780 --> 38:13.520
verallgemeinert.

38:13.840 --> 38:17.320
Aber für naheliegende Verallgemeinerungen wurde gezeigt, dass Schach,

38:17.500 --> 38:24.800
Dame und Go nicht nur NP-hard sind, sondern X-Time vollständig.

38:25.440 --> 38:28.340
Das heißt, das Problem ist weiterhin entscheidbar.

38:29.100 --> 38:29.600
Immerhin.

38:32.340 --> 38:36.220
Aber wenn man das schneller als in exponentieller Zeit lösen könnte,

38:36.360 --> 38:38.680
dann könnte man alles schneller lösen.

38:41.500 --> 38:44.660
Dann gibt es so Spiele wie Otello, Reversi.

38:44.760 --> 38:46.200
Wer von Ihnen kennt das Spiel?

38:46.520 --> 38:49.840
Das ist das gleiche Spiel, aber nicht ganz so viel.

38:49.920 --> 38:53.680
Das ist ein Brett, ich glaube auch 8x8 klassisch.

38:54.160 --> 38:59.680
Da kann man dann Punkte drauflegen, die zwei Seiten haben.

39:00.340 --> 39:03.300
Orange und Grün kenne ich eine Variante.

39:03.800 --> 39:05.400
Einer ist orange, einer ist grün.

39:06.160 --> 39:07.660
Dann legt man die immer da drauf.

39:08.180 --> 39:12.540
Und wenn man dann gegnerische Steine einschließt, dann darf man die

39:12.540 --> 39:13.320
alle umdrehen.

39:15.980 --> 39:20.640
Das ist leichter, das ist nur PSPACE vollständig und damit natürlich

39:20.640 --> 39:21.440
auch NP-hard.

39:22.260 --> 39:25.140
Oder dann so ein Einspieler-Puzzle.

39:25.700 --> 39:27.640
Ein ganz bekanntes ist das 15-Puzzle.

39:27.700 --> 39:30.300
Da haben Sie so einen 4x4-Rahmen

39:35.160 --> 39:36.560
mit beweglichen Stücken drin.

39:36.660 --> 39:37.340
Und da ist ein Loch.

39:38.620 --> 39:41.440
Sie haben die jetzt in irgendeiner permutierten Reihenfolge da drin

39:41.440 --> 39:45.160
und sollen die dann in die Reihenfolge 1, 2, 3 bis 15 bringen.

39:47.800 --> 39:49.380
Das Problem ist polynomiell.

39:50.580 --> 39:55.380
Sie können polynomiell entscheiden, ob das geht und auch so eine

39:55.380 --> 39:56.100
Lösung angeben.

39:56.200 --> 39:59.180
Aber wenn Sie die kürzeste Lösung suchen oder als

39:59.180 --> 40:01.640
Entscheidungsproblem, Sie kriegen noch eine Zahl dazu und sollen

40:01.640 --> 40:05.220
entscheiden, gibt es eine Lösung, die höchstens so lang ist, dann ist

40:05.220 --> 40:06.660
das NP-vollständig.

40:10.110 --> 40:14.510
Also ein ganz naheliegendes Problem, aber schon schwierig, das zu

40:14.510 --> 40:14.850
lösen.

40:16.410 --> 40:21.450
Wir haben dann noch eine Idee gehabt für so eine Research-Problem

40:21.450 --> 40:24.290
-Aufgabe, wo wir wieder nicht genau wissen, ob das nicht schon gelöst

40:24.290 --> 40:24.590
ist.

40:25.110 --> 40:29.130
Aber ich könnte mir vorstellen, dass Schach oder von mir aus auch eins

40:29.130 --> 40:33.030
von den anderen Spielen nicht nur exp-time-vollständig sind, sondern

40:33.030 --> 40:39.850
sogar unentscheidbar, wenn man eine geeignete Verallgemeinerung wählt.

40:41.170 --> 40:42.770
Das ist zum Beispiel jetzt auch so.

40:43.930 --> 40:46.810
Können Sie sich mal überlegen, warum ist Schach und Dame schwieriger

40:46.810 --> 40:48.170
als Othello und Reversi?

40:51.190 --> 40:52.850
Warum die N-mal-N-Version?

40:54.150 --> 40:59.010
Bei dem Ding hier wird in jedem Zug ein Stein gelegt.

40:59.890 --> 41:05.810
Das heißt, so ein N-mal-N-Ding, da gibt es nur N-Züge und danach ist

41:05.810 --> 41:06.650
das Spiel vorbei.

41:10.210 --> 41:15.630
Beim Schach kann ich irgendwie beliebig hin- und herziehen.

41:18.610 --> 41:25.050
Es gibt allerdings beim Schach auch noch mehrere Regeln, die dafür

41:25.050 --> 41:27.170
sorgen, dass ich nicht unendlich lange spielen kann.

41:29.470 --> 41:34.410
Eine, die sagt, es darf höchstens 40 Züge geben und dann nochmal 40

41:34.410 --> 41:37.530
und dann ist aber irgendwann Schluss und wenn es bis dahin nicht

41:37.530 --> 41:38.390
fertig ist, ist Remis.

41:40.010 --> 41:43.070
Und es darf sich auch eine Stellung höchstens dreimal wiederholen.

41:43.270 --> 41:44.710
Wenn das der Fall ist, ist es auch Remis.

41:45.810 --> 41:47.990
Deshalb ist es zum Beispiel so, selbst nur mit dieser

41:47.990 --> 41:54.950
Wiederholungsregel ist es klar, dass es bei einem N-mal-N-Brett nur

41:54.950 --> 41:58.950
endlich viele mögliche Positionen gibt, die ich erreichen kann.

41:59.630 --> 42:04.730
Dann kann ich einfach so einen Graphen aufbauen von Positionen und in

42:04.730 --> 42:07.750
dem dann irgendwie eine geeignete Suche durchführen und kann dann

42:07.750 --> 42:12.490
entscheiden, ob dann alles gewonnen, ob es dann eine Gewinnfahrt gibt

42:12.490 --> 42:13.130
oder sowas.

42:15.230 --> 42:19.490
Aber wenn ich diese Regel aufhebe oder wenn ich zum Beispiel sage, ich

42:19.490 --> 42:24.890
habe nicht ein N-mal-N-Brett, sondern ein 8-mal-unendlich-Brett, also

42:24.890 --> 42:27.550
nach rechts und links ist das Ding unendlich groß und da stehen

42:27.550 --> 42:32.710
überall Bauern von mir aus und ich muss aber irgendwie meine Eingabe

42:32.710 --> 42:35.290
beschreibe ich dadurch, dass irgendwie ein paar Bauern vorgeschoben

42:35.290 --> 42:39.890
sind oder nicht, dann ist mir nicht klar, ob das Ganze wirklich

42:39.890 --> 42:41.350
entscheidbar ist.

42:44.760 --> 42:46.660
Das heißt, die Aufgabenstellung wäre,

42:50.830 --> 42:57.670
geben Sie eine naheliegende Verallgemeinerung von Schach an, bei der

42:57.670 --> 43:02.510
die Frage, ob die Eingabeposition gewonnen ist oder nicht,

43:02.650 --> 43:03.470
unentscheidbar ist.

43:04.910 --> 43:06.430
Und ich denke, das wäre publizierbar.

43:07.030 --> 43:09.430
Es gibt zum Beispiel eine nette Konferenz, die heißt Fun with

43:09.430 --> 43:12.330
Algorithms, da könnte man das sehr schön hinschicken.

43:13.730 --> 43:18.730
Das ist aber jetzt nichts, was die akademische Welt revolutionieren

43:18.730 --> 43:21.490
würde oder tolle Anwendungen hätte, aber sehr spannend.

43:25.820 --> 43:29.340
Das habe ich aus einer Webseite von einem Algorithmiker, David

43:29.340 --> 43:32.480
Epstein, der sich aber auch für so Sachen nennt.

43:33.940 --> 43:36.460
Gibt es sonst noch Fragen zur Komplexitätstheorie?

43:39.060 --> 43:42.780
Dann wären wir aus Vorlesungssicht damit durch und sehen jetzt noch

43:42.780 --> 43:48.080
ein paar abgedrehte Reduktionen von Andreas und Lorenz.

43:48.240 --> 43:48.740
Dankeschön.

43:50.240 --> 43:55.740
Wir machen jetzt noch ein paar Sachen zu den Themen von der letzten

43:55.740 --> 43:57.020
Vorlesung hauptsächlich.

43:57.240 --> 44:01.800
Da wurde ja mal kurz das Integer-Linear-Programming angesprochen oder

44:01.800 --> 44:03.500
ILP.

44:03.860 --> 44:08.600
Da war das Szenario, dass man so einen Variablenvektor gegeben hat,

44:09.320 --> 44:13.040
für den man eine Belegung sucht, sodass das Ganze dann eine Menge von

44:13.040 --> 44:13.920
Constraints erfüllt.

44:14.020 --> 44:16.660
Da gibt es auch eine Optimierungsvariante davon, wo man dann noch eine

44:16.660 --> 44:22.640
Optimierungsfunktion hat, die auch ungefähr so ein Produkt mit X ist

44:22.640 --> 44:24.660
und das maximieren will.

44:28.700 --> 44:32.160
Der eine Trick, den wir da gesehen hatten, war, dass man 0,1

44:32.160 --> 44:36.260
Belegungen erzwingen kann dabei, indem man irgendwie solche Klauseln

44:36.260 --> 44:37.140
reinmacht.

44:37.880 --> 44:40.360
Manchmal passiert es auch, dass einem der Consolver beispielsweise nur

44:40.360 --> 44:42.800
kleiner gleich erlaubt, dann muss man halt den linken Teil noch

44:42.800 --> 44:43.280
umdrehen.

44:45.260 --> 44:50.240
Aber das ist so ein Trick, den man häufiger braucht bei ILPs, weil

44:50.240 --> 44:54.280
sich viele Probleme einfach mit diesen 0,1 Variablen darstellen

44:54.280 --> 44:54.620
lassen.

44:55.280 --> 44:57.440
Und so auch das Knapsack-Problem.

44:58.820 --> 45:04.360
Also Knapsack kennen wir ja schon von vielen Beispielen in der

45:04.360 --> 45:04.860
Vorlesung.

45:06.220 --> 45:10.060
Wir haben diesen Gewichtsvektor, der jedem Gegenstand ein Gewicht

45:10.060 --> 45:13.500
zuweist und einen Profitvektor, der irgendwie sagt, wie gerne wir

45:13.500 --> 45:15.100
diesen Gegenstand jetzt mitnehmen würden.

45:16.080 --> 45:20.520
Und das Maximalgewicht W und den Profit, den wir aber gerne mindestens

45:20.520 --> 45:26.220
dabei hätten, insgesamt P. Und das wollen wir jetzt in so ein ILP

45:26.220 --> 45:26.980
reinzwingen.

45:28.600 --> 45:32.220
Man kann sich ja überlegen, was ist das Gesamtgewicht von einer

45:32.220 --> 45:36.020
Belegung, wenn ich die jetzt als Vektor habe, von meinen Gegenständen.

45:36.100 --> 45:39.200
Also ich habe einen Vektor, da ist 0 oder 1, wenn der Gegenstand dabei

45:39.200 --> 45:39.880
ist oder nicht.

45:41.240 --> 45:41.660
Andersherum.

45:42.540 --> 45:46.780
Aber wenn ich dann ein Skalarprodukt mit dem Gewichtsvektor mache,

45:46.980 --> 45:49.540
dann ist das ja genau das Gesamtgewicht der Gegenstände.

45:50.820 --> 45:52.560
Und das gleiche beim Profit.

45:53.500 --> 45:56.540
Das heißt, wenn ich einen 0,1 Vektor habe, welche Gegenstände ich

45:56.540 --> 46:00.780
mitnehme und welche nicht, dann kann ich die einfach mit W und P, mit

46:00.780 --> 46:04.880
einem Skalarprodukt multiplizieren und habe dann Gewicht und Wert von

46:04.880 --> 46:05.580
dieser Lösung.

46:06.680 --> 46:11.700
Das heißt, ich habe hier den Constraint, dass das Gesamtgewicht der

46:11.700 --> 46:17.180
ausgewählten Gegenstände höchstens W sein darf und dass der Profit

46:17.180 --> 46:18.760
mindestens P sein muss.

46:20.580 --> 46:26.180
Dann habe ich hier noch, ich habe das hier mal in Vektorschreibweise

46:26.180 --> 46:30.160
hingemacht, dass jedes Element 0 oder 1 mal ausgewählt werden kann.

46:30.440 --> 46:31.100
Beziehungsweise muss.

46:32.840 --> 46:35.380
Diese 0 und diese 1 sind hier Vektoren.

46:37.080 --> 46:40.640
Wenn ich das jetzt noch wieder umdrehen muss, dass die ganzen größer

46:40.640 --> 46:44.460
-gleichs zu kleiner-gleichs werden, dann kann ich die hier einfach so

46:44.460 --> 46:48.760
umdrehen und kann das in meinen ILP-Solver reinwerfen.

46:49.180 --> 46:50.560
Der löst dann den Knapsack für mich.

46:55.100 --> 46:56.540
Damit gebe ich auch schon weiter.

46:56.700 --> 46:57.800
Wir tauschen heute ein paar Mal.

47:02.600 --> 47:03.160
Okay.

47:05.040 --> 47:09.040
Ich wollte einfach nochmal eingehen auf ein paar Sachen, die in der

47:09.040 --> 47:12.460
letzten Vorlesung ganz kurz angesprochen worden sind, aber noch nicht

47:12.460 --> 47:14.180
ausführlich erklärt worden sind.

47:14.600 --> 47:17.060
Zum Beispiel pseudopolynomielle Algorithmen.

47:18.380 --> 47:23.180
Und da wurde ja in der Vorlesung auch schon gesagt, pseudopolynomielle

47:23.180 --> 47:26.020
Algorithmen habt ihr eigentlich auch schon den Algo gesehen.

47:27.940 --> 47:31.640
Das stimmt natürlich so einigermaßen, aber euch hat keiner gesagt,

47:31.780 --> 47:32.960
dass der pseudopolynomielle war.

47:35.620 --> 47:38.680
Außerdem versteht man vielleicht den Algorithmus beim ersten Mal gar

47:38.680 --> 47:40.840
nicht, weil das ist, glaube ich, das erste Mal gewesen, dass ihr

47:40.840 --> 47:42.400
dynamische Programmierung gesehen habt.

47:43.300 --> 47:45.580
Deswegen wollte ich einfach nochmal durch den Algorithmus durchgehen

47:45.580 --> 47:54.240
und zeigen, warum der das Problem optimal löst und warum das trotzdem

47:54.240 --> 47:56.820
nicht genug ist, um das Problem polynomiell zu machen.

47:57.800 --> 48:00.400
Was haben wir über pseudopolynomielle Algorithmen gesagt?

48:00.860 --> 48:05.100
Wir haben gesagt, die laufen polynomiell in ihrer Eingabelänge plus

48:05.100 --> 48:08.800
der Größe ihrer größten Zahl.

48:09.540 --> 48:13.200
Also sei m mal die größte Zahl, die in der Eingabe vorkommt, dann

48:13.200 --> 48:20.360
läuft ein pseudopolynomieller Algorithmus in der Eingabekodierung plus

48:20.360 --> 48:21.620
der größten Zahl.

48:21.940 --> 48:25.800
Beziehungsweise was man genauso machen kann, ist, der Algorithmus

48:25.800 --> 48:30.580
läuft polynomiell in der Kodierungslänge, wenn man alle Zahlen in

48:30.580 --> 48:32.220
dieser Kodierung unnäher kodiert.

48:36.300 --> 48:40.140
Man kann sich einigermaßen leicht vorstellen, dass dieses hier

48:40.140 --> 48:40.920
dasselbe ist.

48:43.740 --> 48:46.060
Wir schauen uns jetzt einfach mal den Algorithmus an.

48:48.780 --> 48:51.660
Was der Algorithmus, den ihr gesehen habt, wahrscheinlich macht, ist,

48:51.720 --> 48:59.000
er hat die Kapazität der Elemente bis zur maximal erlaubten Kapazität

48:59.000 --> 49:02.380
auf der einen Seite aufgetragen und auf der anderen Seite aufgetragen

49:02.380 --> 49:05.380
hat er die Elemente selber, also die verwendet werden dürfen.

49:05.940 --> 49:11.220
Was dann zum Beispiel diese Zelle hier aussagt, ist, hier steht der

49:11.220 --> 49:17.760
maximale Profit drin, den ihr mit Kapazität 4 erreichen könnt, wenn

49:17.760 --> 49:20.940
ihr dabei nur die ersten zwei Elemente verwenden dürft.

49:21.540 --> 49:24.420
Also hier steht immer, welche Elemente verwendet werden dürfen, also

49:24.420 --> 49:27.500
das Element A und das Element B momentan.

49:28.440 --> 49:33.880
Und hier die Spalte gibt an, was für eine Kapazität man sich zur

49:33.880 --> 49:34.640
Verfügung stellt.

49:35.580 --> 49:39.440
Und man kann sich leicht überlegen, dass das Feld ausgefüllt werden

49:39.440 --> 49:41.140
kann, indem man dieses Feld hier anschaut.

49:42.340 --> 49:47.400
Also das ist der Fall, dass das Element 2, also hier ist ja dieselbe

49:47.400 --> 49:50.760
Probleminstanz, außer dass wir nicht Element 2 verwenden durften.

49:51.660 --> 49:55.640
Also hier steht der Wert drin, den wir erreichen können, ohne Element

49:55.640 --> 49:56.580
2 zu verwenden.

49:56.980 --> 50:01.660
Und hier steht der Wert drin, den wir erreichen können, indem wir

50:01.660 --> 50:02.680
Element 2 verwenden.

50:03.600 --> 50:09.080
Nämlich, wenn wir Element 2 verwenden, dann werden ja drei Kapazität

50:09.080 --> 50:11.560
schon wieder verbraucht, durch das Gewicht von Element 2.

50:12.200 --> 50:14.720
Dafür haben wir 20 zusätzlichen Gain.

50:15.280 --> 50:20.380
Das heißt, wir können hier reinschauen und darauf 20 addieren, wenn

50:20.380 --> 50:24.980
wir wissen wollen, wie groß unser Profit werden kann, wenn wir Element

50:24.980 --> 50:27.340
2 verwenden und nur Kapazität 4 haben.

50:28.820 --> 50:31.140
Und das macht man dann einfach einmal als Tabelle.

50:31.140 --> 50:32.400
Die erste Zeile ist klar.

50:34.400 --> 50:37.680
Wenn wir kein Element verwenden dürfen, kriegen wir keinen Gain.

50:38.260 --> 50:39.920
Da kann man nicht besonders viel machen.

50:40.760 --> 50:43.740
Ohne Kapazität ist eigentlich auch klar, dass wir keinen Gain kriegen

50:43.740 --> 50:44.080
können.

50:44.760 --> 50:49.920
Es gibt Varianten von der Problemstellung, wo manche Elemente Gewicht

50:49.920 --> 50:51.880
0 haben, aber es ist ziemlich uninteressant.

50:52.580 --> 50:55.880
Man nimmt einfach alles mit, was Gewicht 0 hat und positiven Gain hat.

50:57.880 --> 51:01.080
Deswegen schauen wir uns hier eins an, das nicht hat.

51:01.740 --> 51:06.260
Das erste Interessante passiert, wenn wir uns Kapazität 1 geben und

51:06.260 --> 51:07.880
Element 1 reinnehmen können.

51:08.280 --> 51:11.940
Klar, dann können wir 10 Gain kriegen, indem wir einfach Element 1

51:11.940 --> 51:12.200
nehmen.

51:13.620 --> 51:15.420
Genauso passiert das mit mehr Kapazität.

51:15.540 --> 51:17.500
Wir dürfen Element 1 nicht mehrfach nehmen.

51:19.080 --> 51:21.400
Also nehmen wir es immer nur einfach.

51:21.400 --> 51:25.280
Und umso mehr Kapazität wir kriegen, bringt uns in dem Fall nicht so

51:25.280 --> 51:25.460
viel.

51:26.860 --> 51:28.320
In der nächsten Zeile ist es genauso.

51:29.120 --> 51:30.160
Die 0 bleibt hier.

51:31.200 --> 51:34.580
Diese zwei Zehner hier bleiben auch, weil wir uns ja neu Element 2

51:34.580 --> 51:34.580
geben.

51:35.660 --> 51:37.620
Und das hat Kapazität 3.

51:37.720 --> 51:40.180
Das heißt, in diesen Fällen können wir das noch gar nicht einsetzen.

51:41.180 --> 51:44.080
Erst hier können wir Element 2 verwenden.

51:45.760 --> 51:49.740
Und das tun wir auch, weil es mehr Gain bringt, als Element 1 zu

51:49.740 --> 51:50.140
verwenden.

51:51.040 --> 51:54.900
Und hier können wir jetzt sogar Element 1 noch mit dazu verwenden.

51:55.080 --> 51:57.520
Hier haben wir gesehen, die Zellen, die wir anschauen, da waren keine

51:57.520 --> 51:58.020
10 drin.

51:58.560 --> 51:59.840
Wir addieren 20 drauf.

52:00.560 --> 52:03.020
Jetzt die Zellen, die wir anschauen, da ist schon was drin.

52:03.860 --> 52:05.920
Und wir kommen zu besseren Werten.

52:06.700 --> 52:08.140
Praktisch äquivalent läuft es hier.

52:09.760 --> 52:14.940
Wir nehmen uns Element 3 jetzt und schauen hier immer 2 zurück, weil

52:14.940 --> 52:16.400
Element 3 hat nur Gewicht 2.

52:18.460 --> 52:20.440
Und so kommt man eben auf diese Tabelle.

52:20.840 --> 52:22.960
Element 4 sieht man schon eigentlich.

52:23.480 --> 52:29.640
Es ist ziemlich schwer und hat nicht mehr Profit, als Element 2 hat.

52:30.240 --> 52:32.820
Das heißt, Element 4 zu nehmen, ist eigentlich immer sinnfrei.

52:34.780 --> 52:36.760
Damit kommen wir bei der ganzen Tabelle an.

52:38.940 --> 52:43.040
Viele von diesen pseudopolynomialen Problemen lassen sich lösen durch

52:43.040 --> 52:45.840
ähnliche dynamische Ansätze.

52:46.540 --> 52:49.860
Über dynamisches Programmieren wisst ihr eigentlich schon, dass es

52:49.860 --> 52:54.140
eigentlich immer daraus funktioniert, dass man kleinere Teillösungen

52:54.140 --> 52:56.080
zu größeren Lösungen zusammensetzt.

52:56.660 --> 53:00.360
Wir hatten ja hier, das sind alles Teillösungen für Teilprobleme.

53:01.200 --> 53:05.960
Diese Stelle hat mir gesagt, wie viel kann ich mit 2 Elementen und 4

53:05.960 --> 53:06.920
Kapazitäten machen.

53:07.000 --> 53:09.520
Das ist eine Teillösung, die ich für eine größere Lösung verwenden

53:09.520 --> 53:09.860
kann.

53:13.020 --> 53:17.800
Jetzt will ich so ein bisschen den Bogen schlagen zu etwas anderem.

53:17.920 --> 53:22.660
Was wir dafür brauchen, ist, man kann den selben Algorithmus auch

53:22.660 --> 53:26.120
machen, aber man wählt die Prioritäten aus.

53:26.900 --> 53:36.020
Die Spalten werden jetzt unsere Gains sein, unser Gewinn sein, den wir

53:36.020 --> 53:36.940
durch die Lösung kriegen.

53:36.940 --> 53:42.380
Und was gesucht ist, ist die kleinste Kapazität, sodass man über

53:42.380 --> 53:44.440
diesen Gewinn kommt.

53:45.060 --> 53:48.320
Wir sehen, 65 Gewinn ist unser Maximum, indem wir einfach alle

53:48.320 --> 53:49.160
Elemente mitnehmen.

53:50.040 --> 53:53.000
Und hier werden wir dann natürlich auch die Kapazität brauchen, um

53:53.000 --> 53:53.720
alle mitzunehmen.

53:53.840 --> 53:54.940
Das sind in dem Fall 10.

54:00.840 --> 54:05.520
Hier steht jetzt zum Beispiel drin, wie viel Kapazität brauche ich, um

54:05.520 --> 54:09.340
mit Element 1 und 2 über 25 Gain zu kommen.

54:10.540 --> 54:14.780
Und mit Element 1 und 2 sieht man hier, wenn ich nur die beiden haben

54:14.780 --> 54:20.100
darf, dann brauche ich 4 Kapazität, um über Gain 25 zu kommen.

54:21.260 --> 54:23.280
Ob das noch besser sieht, sehen wir dann.

54:24.240 --> 54:26.000
Man kann im Endeffekt genau dasselbe machen.

54:27.720 --> 54:31.100
Man schaut sich wieder die Stelle über einem an, wie viel brauche ich

54:31.100 --> 54:34.680
ohne dieses Element, um über 25 Gain zu kommen.

54:35.440 --> 54:37.360
Und dann schaut man sich eine Stelle hier drüben an.

54:37.940 --> 54:43.960
Wenn ich Element 2 verwende, dann muss ich ja 20 Gain weniger machen,

54:44.180 --> 54:46.280
weil die werden von diesem Element 2 gemacht.

54:47.100 --> 54:50.900
Ich brauche aber 3 Kapazitäten mehr, als wenn ich es nicht verwende.

54:51.880 --> 54:54.300
Und dann kann man hier in der Zelle nachschauen und es finden.

54:55.840 --> 54:57.200
Und dabei kommt dieses hier raus.

54:57.940 --> 55:03.080
Die Infinity stehen hier mal drin, weil wenn ich nur das 0.

55:03.220 --> 55:09.500
Element verwenden darf, dann kann ich natürlich nicht über 10 Gain

55:09.500 --> 55:11.720
kommen, weil das Element hat nur 10 Gain.

55:12.160 --> 55:14.080
Das heißt, ich kann hier ganz viel gar nicht erreichen.

55:14.400 --> 55:15.920
Aber wir sehen, am Ende ist hier die 10.

55:21.260 --> 55:24.980
Der Bogen, den ich damit schlagen will, geht zu approximativen

55:24.980 --> 55:25.600
Algorithmen.

55:25.600 --> 55:30.600
Was man jetzt hier relativ einfach sieht, ist, diese Tabelle ist jetzt

55:30.600 --> 55:39.080
schon riesig, aber die ist vollkommen ohne Grund riesig, weil ein Gain

55:39.080 --> 55:44.280
zu machen macht in dem Fall überhaupt keinen Unterschied dazu, 5 Gain

55:44.280 --> 55:48.360
zu machen oder 10 Gain zu machen, weil es gibt kein Element, das so

55:48.360 --> 55:49.220
wenig Gain gibt.

55:49.900 --> 55:52.220
Das heißt, ich kann den ganzen Gain runterbrechen

55:56.760 --> 55:58.300
auf Fünfer-Vielfache.

55:59.360 --> 56:02.140
Wenn ich den Gain runterbreche auf Fünfer-Vielfache, dann ist die

56:02.140 --> 56:04.120
Tabelle hier natürlich nur ein Fünftel breit.

56:05.100 --> 56:05.940
Das ist schon mal super.

56:07.480 --> 56:11.560
Und die Idee ist jetzt, man könnte die Tabelle ja noch schmaler

56:11.560 --> 56:11.860
machen.

56:13.100 --> 56:15.440
Was passiert, wenn man die Tabelle noch schmaler macht?

56:16.060 --> 56:19.500
Also hier haben wir jetzt erstmal 4 von 5 Dingern gestrichen, haben

56:19.500 --> 56:26.180
alles, was mit Gain zu tun hat, gekürzt im Endeffekt.

56:27.160 --> 56:30.320
Und die Lösung hier ist aber immer noch genau dieselbe.

56:31.480 --> 56:34.180
Einfach, weil die Problemstellung zu aufgebläht war.

56:36.440 --> 56:41.360
Und die Idee, was man jetzt noch weiterhin machen kann, ist, man macht

56:41.360 --> 56:42.720
weiter mit demselben Ansatz.

56:44.060 --> 56:45.180
Also vorher war die Idee,

56:54.620 --> 56:58.860
wir streichen überflüssige Informationen raus und jetzt ist die Idee,

56:58.960 --> 57:01.040
wir streichen wichtige Informationen raus.

57:01.740 --> 57:05.260
Also wir skalieren noch weiter und kürzen dann aber am Ende.

57:07.120 --> 57:10.800
Und das Tolle, was wir dadurch erreichen, jetzt verändert sich

57:10.800 --> 57:12.840
natürlich die Tabelle, die Tabelle wird viel kleiner.

57:13.560 --> 57:18.220
In dem Fall ist jetzt das Maximum der maximale Gain 6, weil hier bei

57:18.220 --> 57:21.660
dem C, das ist der Fall, der sich verändert.

57:22.240 --> 57:27.500
Wenn wir das jetzt nochmal mit 2 halbieren, dann sinkt der Gain von C.

57:28.240 --> 57:30.620
Und deswegen wird unsere Lösung nicht mehr optimal sein.

57:31.460 --> 57:34.800
Aber man kann eben zeigen, dass die Lösung immer noch gut ist.

57:36.180 --> 57:37.600
Und das ist das Interessante dran.

57:38.360 --> 57:40.840
Darum geht es bei Approximationsalgorithmen.

57:40.840 --> 57:44.960
Wir wollen im Endeffekt einen Algorithmus haben, der in polynomialer

57:44.960 --> 57:49.760
Zeit läuft, von dem wir sagen können, er ist nicht optimal, er gibt

57:49.760 --> 57:51.980
uns schlechtere Lösungen als die optimale Lösung.

57:55.240 --> 57:59.140
Aber wir können halt abschätzen, wie schlecht die Lösungen sind.

57:59.840 --> 58:04.020
Zum Beispiel, wenn man hier fragen würde, können wir einen Gain von 65

58:04.020 --> 58:07.640
erreichen, würde dieses Stupide runden und sagen, nein, wir können

58:07.640 --> 58:09.380
keinen Gain von 65 erreichen.

58:09.980 --> 58:12.640
Weil wir können jetzt nur noch einen Gain von 6 erreichen.

58:14.780 --> 58:19.920
Es wäre aber im ursprünglichen Problem nur ein Gain von 60 gewesen.

58:21.360 --> 58:25.220
Also man sieht auch hier in der Tabelle, ändern sich jetzt diese zwei

58:25.220 --> 58:26.060
Positionen.

58:26.160 --> 58:30.820
Und zwar die Position ist, wie kann ich am geschicktesten 25

58:30.820 --> 58:31.080
erreichen?

58:33.380 --> 58:35.980
Wie kann ich am geschicktesten 2,5 erreichen?

58:35.980 --> 58:38.880
Und die Information haben wir weggeworfen.

58:38.980 --> 58:40.600
Die Komma 5 hier gibt es nicht mehr.

58:42.000 --> 58:45.900
Und das heißt, jetzt ist unsere Lösung nicht mehr optimal, aber sie

58:45.900 --> 58:46.840
ist eben nah dran.

58:48.480 --> 58:50.680
Und die Frage ist, wie nah dran ist die Lösung?

58:52.340 --> 58:56.100
Naja, die Lösung ist sogar so nah dran, dass wenn man das richtig

58:56.100 --> 59:00.140
macht, kann ich beliebig nah an die optimale Lösung kommen.

59:01.740 --> 59:08.160
Und zwar können wir uns hier Zahlen ausdenken, die die Tabelle klein

59:08.160 --> 59:12.140
machen, also die polynomiale Größe von der Tabelle, sodass wir

59:12.140 --> 59:14.220
trotzdem nur sehr wenig Informationen wegwerfen.

59:16.160 --> 59:19.160
Und das ist die Idee hinter Approximationsschemata.

59:21.380 --> 59:25.520
Ein Approximationsschema gibt uns eine Menge von Algorithmen im

59:25.520 --> 59:30.320
Endeffekt, wo wenn wir eine Approximationsgrenze uns ausdenken, also

59:30.320 --> 59:35.520
in dem Fall 1 plus Y, dann gibt uns das Approximationsschema einen

59:35.520 --> 59:39.720
Algorithmus, der das Problem so nah approximiert.

59:40.240 --> 59:47.520
Also wenn wir jetzt sagen würden, Y sei 0,00001, dann liefert dieses

59:47.520 --> 59:54.800
Approximationsschema uns einen Algorithmus, der wirklich nur 0,00001

59:54.800 --> 59:56.740
von der optimalen Lösung entfernt ist.

59:57.920 --> 01:00:03.720
Und trotzdem läuft der Algorithmus selber in polynomialer Zeit.

01:00:05.420 --> 01:00:09.880
Das ist eine wirklich schöne Sache, die jetzt für unsere Klausur

01:00:09.880 --> 01:00:12.740
wahrscheinlich nicht relevant sein wird, aber die beschäftigt euch

01:00:12.740 --> 01:00:14.480
dann auch noch in Algorithmen 2.

01:00:15.280 --> 01:00:17.080
Insofern wollte ich sie mal vorgestellt haben.

01:00:20.540 --> 01:00:25.760
In dem Fall wäre jetzt dieser Faktor, mit dem man multipliziert, das

01:00:25.760 --> 01:00:30.380
kann man noch dazu sagen, der ist irgendwie Y mal die größte Zahl, die

01:00:30.380 --> 01:00:34.500
vorkommt bei den Profiten, geteilt durch N, also geteilt durch die

01:00:34.500 --> 01:00:35.980
Anzahl an Profiten.

01:00:36.520 --> 01:00:39.960
Dann erhält man eben eine sehr gute Approximation für das ganze

01:00:39.960 --> 01:00:41.220
Problem.

01:00:44.240 --> 01:00:47.220
Für euch ist erstmal vor allem wichtig, dass ihr wisst, was

01:00:47.220 --> 01:00:52.280
Approximation ist und dass es solche Algorithmen gibt, auch zum Teil

01:00:52.280 --> 01:00:55.060
für NP-vollständige Probleme.

01:01:00.820 --> 01:01:04.920
Dann kommen wir jetzt zu ein paar interessanteren NP

01:01:04.920 --> 01:01:07.080
-Vollständigkeitsreduktionen.

01:01:07.540 --> 01:01:11.100
Wie gerade eben schon angesprochen, viele Spiele sind NP-vollständig

01:01:11.100 --> 01:01:14.480
und wir wollen jetzt einfach für ein paar davon vorführen, wie man so

01:01:14.480 --> 01:01:15.900
eine Konstruktion machen könnte.

01:01:21.730 --> 01:01:24.650
Die meisten Spiele muss man dafür irgendwie erweitern, das ist auch

01:01:24.650 --> 01:01:25.590
bei Dominos so.

01:01:27.050 --> 01:01:30.490
Also wir haben jetzt nicht mehr irgendwie Zahlen von 1 bis irgendwas

01:01:30.490 --> 01:01:35.710
kleines, sondern erweitern das, wie wir es gerade brauchen für die

01:01:35.710 --> 01:01:36.210
Instanz.

01:01:36.550 --> 01:01:39.990
Also nehmen einfach mal an, dass da natürliche Zahlen draufstehen auf

01:01:39.990 --> 01:01:40.510
den Steinen.

01:01:40.650 --> 01:01:43.430
Aber ansonsten sind es die normalen Domino-Steine, auf denen zwei

01:01:43.430 --> 01:01:50.250
Zahlen stehen und die irgendwie so doppelt so hoch wie breit sind.

01:01:53.730 --> 01:01:57.690
Und wir sagen, dass die Spieler ein Multi-Set von Steinen kriegen,

01:01:58.070 --> 01:01:58.070
jeder.

01:01:59.090 --> 01:02:02.050
Und insbesondere müssen die auch nicht gleich viele Steine haben

01:02:02.050 --> 01:02:02.450
dafür.

01:02:03.370 --> 01:02:06.430
Also es ist jetzt nicht so, als würde da grundsätzlich immer gemischt

01:02:06.430 --> 01:02:09.030
und dann würde jeder irgendwie beliebige Steine kriegen, sondern wir

01:02:09.030 --> 01:02:13.070
konstruieren eine relativ spezielle Domino-Instanz, bei der der eine

01:02:13.070 --> 01:02:18.990
Spieler möglicherweise auch quadratisch mehr Steine haben kann als der

01:02:18.990 --> 01:02:21.270
andere, im Worst-Case.

01:02:22.970 --> 01:02:26.170
Aussetzen ist übrigens auch verboten, dann würde man sofort verlieren,

01:02:26.350 --> 01:02:29.350
aber ich glaube noch, dass das eine große Restriction ist.

01:02:30.370 --> 01:02:33.370
Denn in der Instanz, die wir gleich konstruieren werden, wird man

01:02:33.370 --> 01:02:36.550
sehen, dass es mit Aussetzen überhaupt nicht funktionieren kann.

01:02:37.370 --> 01:02:40.230
Wir nehmen außerdem an, dass die Steine offen liegen, also dass jeder

01:02:40.230 --> 01:02:42.430
Spieler alle Steine von den anderen sehen kann.

01:02:43.910 --> 01:02:47.350
Das ist, wenn man im Team spielt, irgendwie eine sinnvolle Annahme,

01:02:47.430 --> 01:02:50.110
weil man dann ja eh zusammenspielt und eigentlich alle Informationen

01:02:50.110 --> 01:02:50.710
teilen will.

01:02:51.810 --> 01:02:56.550
Und wenn man gegeneinander spielt, weiß man daraus, was die Teammates

01:02:56.550 --> 01:02:58.530
haben, ja irgendwie auch, was die anderen haben müssen.

01:03:00.110 --> 01:03:02.410
Also ganz so fürchterlich ist diese Annahme jetzt.

01:03:03.770 --> 01:03:08.290
Wir nehmen jetzt mal an, die Steine liegen offen, jeder sieht, was die

01:03:08.290 --> 01:03:08.870
anderen haben.

01:03:11.210 --> 01:03:14.970
Das Ziel ist, eine Domino-Kette zu legen, also eine Kette, keine Bäume

01:03:14.970 --> 01:03:15.510
oder so.

01:03:17.830 --> 01:03:21.810
Die zwei Probleme, die wir uns da anschauen werden, sind Cooperative

01:03:21.810 --> 01:03:23.190
und Competitive-Dominoes.

01:03:24.830 --> 01:03:28.370
Also in einem Fall geht es darum, dass alle Spieler zusammen

01:03:28.370 --> 01:03:31.130
kooperieren und die Frage ist, kann Spieler 1 gewinnen?

01:03:33.010 --> 01:03:37.830
Und die Competitive-Variante davon ist, kann Spieler 1 gewinnen, auch

01:03:37.830 --> 01:03:41.290
wenn der Gegner versucht, das zu verhindern?

01:03:42.830 --> 01:03:45.290
Die sind unterschiedlich schwer, das werden wir gleich sehen.

01:03:51.100 --> 01:03:56.760
Zuerst die Behauptung ist, dass mit zwei Spielern kooperativ das ganze

01:03:56.760 --> 01:04:02.000
NP vollständig ist und die Verallgemeinerung davon nachher, dass es

01:04:02.000 --> 01:04:03.360
auch für mehr als zwei Spieler gilt.

01:04:04.840 --> 01:04:08.220
Es ist irgendwie einfach zu sehen, dass es ein NP ist, denn dazu muss

01:04:08.220 --> 01:04:11.380
man nur irgendwie die Zugfolge anschauen, die dazu führt, dass der

01:04:11.380 --> 01:04:12.580
erste Spieler gewinnt.

01:04:13.180 --> 01:04:14.500
S1 ist hier Spieler 1.

01:04:16.080 --> 01:04:21.820
Und man kann dann schauen, hat er seine Steine losgeworden und wenn

01:04:21.820 --> 01:04:22.820
ja, dann hat er gewonnen.

01:04:25.840 --> 01:04:28.960
Und um das zu beweisen, wenn wir von Hamilton Path reduzieren,

01:04:29.040 --> 01:04:32.900
Hamilton Path ist fast wie Hamilton's Cycle, nur dass es kein Kreis

01:04:32.900 --> 01:04:36.240
sein muss, sondern nur ein Pfad, der alle Knoten besucht, ist auch NP

01:04:36.240 --> 01:04:36.900
vollständig.

01:04:41.570 --> 01:04:48.290
Also wenn das hier der Graph ist, G, der die Hamilton Path Instanz

01:04:48.290 --> 01:04:52.610
ist, dann konstruieren wir die Instanz so, dass Spieler 1 für jeden

01:04:52.610 --> 01:04:56.870
Knoten einen Stein kriegt, auf dem zweimal die ID dieses Knotens

01:04:56.870 --> 01:04:57.430
draufsteht.

01:04:58.670 --> 01:05:04.310
Und Spieler 2 kriegt für jede Kante einen Stein, auf dem zwei

01:05:04.310 --> 01:05:06.070
Endknoten der Kante draufstehen.

01:05:06.070 --> 01:05:09.010
Und dazu noch so ein Stein, Sternchen, Sternchen, der nirgendwo

01:05:09.010 --> 01:05:11.850
nirgends hinpasst und der verhindert nur, dass Spieler 2 gewinnen

01:05:11.850 --> 01:05:12.170
kann.

01:05:13.650 --> 01:05:16.730
Den kann er nirgends dranlegen und Spieler 1 fängt an.

01:05:17.210 --> 01:05:21.070
Also wird er den immer übrig haben und wenn es irgendwie möglich ist,

01:05:21.130 --> 01:05:22.970
das Spiel zu gewinnen, dann gewinnt Spieler 1.

01:05:26.310 --> 01:05:29.230
Man kann sich jetzt schon denken, wo das drauf rausläuft.

01:05:31.590 --> 01:05:35.530
Okay, die Reduktion ist polynomiell und die Behauptung ist jetzt, dass

01:05:35.530 --> 01:05:39.150
Spieler 1 genau dann gewinnt, wenn die Dominokette, die die Spieler da

01:05:39.150 --> 01:05:42.730
hinlegen, eine Hamilton Path beschreibt im Grafen.

01:05:44.390 --> 01:05:46.470
Also hier ist ein Beispiel, wie das dann aussieht.

01:05:46.830 --> 01:05:51.250
Hier ist der Graf und da ist eine Hamilton Path gesucht.

01:05:51.470 --> 01:05:53.650
Das hier sind die Dominosteine, die wir dann produzieren.

01:05:55.970 --> 01:05:58.990
Spieler 1 kriegt für jeden Knoten so einen Stein, auf dem zweimal das

01:05:58.990 --> 01:06:01.570
gleiche steht und Spieler 2 kriegt für jede Kante.

01:06:02.330 --> 01:06:11.750
Also von 1 nach 2, von 1 nach 5, von 2 nach 5, von 2 nach 3, von 4

01:06:11.750 --> 01:06:14.670
nach 5, von 3 nach 4 und von 4 nach 6.

01:06:16.350 --> 01:06:18.870
Und hier unten ist dann die Lösung, wie das aussehen kann.

01:06:19.010 --> 01:06:22.070
Also Spieler 1 legt zuerst den Stein mit der 6, mit Knoten 6.

01:06:22.990 --> 01:06:25.250
Spieler 2 kann nur diesen einen hier anlegen.

01:06:25.910 --> 01:06:29.050
Spieler 1 kann wieder nur seinen Knotenstein legen.

01:06:29.210 --> 01:06:32.150
Also Spieler 2 gibt immer vor, welchen Stein Spieler 1 als nächstes

01:06:32.150 --> 01:06:32.730
legen muss.

01:06:33.690 --> 01:06:35.370
Das passt ja nur der Knotenstein.

01:06:36.050 --> 01:06:38.910
Und da ihr von jedem von diesen Knotensteinen nur eins habt, muss das

01:06:38.910 --> 01:06:42.370
ja irgendwie dann, also zwingt das, dass jeder Knoten nur einmal

01:06:42.370 --> 01:06:43.310
gelegt werden kann.

01:06:45.890 --> 01:06:52.030
Und wir sehen, dass dann am Ende eben jeder Knoten hier einmal vorkam,

01:06:52.130 --> 01:06:54.330
also 6, 4, 3, 2, 5, 1.

01:06:55.550 --> 01:06:56.750
Und das ist der Hamilton-Pfad.

01:06:57.110 --> 01:06:59.830
6, 4, 3, 2, 5, 1.

01:07:01.790 --> 01:07:05.890
Spieler 2 hat noch was übrig plus sein Blocker-Domino.

01:07:08.050 --> 01:07:14.530
Also formell, Spieler 1 hat genau einen Stein für jeden Knoten und

01:07:14.530 --> 01:07:16.030
Spieler 2 für jede Kante.

01:07:16.550 --> 01:07:19.590
Das heißt, wenn es eins alle Steine gelegt hat, muss das Ganze

01:07:19.590 --> 01:07:20.950
irgendwie ein Hamilton-Pfad sein.

01:07:21.570 --> 01:07:24.590
Das fängt bei einem Knoten an, besucht alle und dazwischen sind nur

01:07:24.590 --> 01:07:24.930
Kanten.

01:07:25.770 --> 01:07:26.490
Das ist klar.

01:07:27.410 --> 01:07:32.010
Und rückwärts, wenn es eine Domino-Kette gibt, die einen Hamilton-Pfad

01:07:32.730 --> 01:07:34.630
beschreibt, dann gewinnt Spieler 1 auch.

01:07:38.680 --> 01:07:38.940
Gut.

01:07:40.520 --> 01:07:45.640
Also, da wir gezeigt haben, dass es in NP schwer ist durch Reduktion

01:07:45.640 --> 01:07:48.780
von Hamilton-Pfad, ist es NP-vollständig.

01:07:49.020 --> 01:07:51.180
Diese Antwortsätze sind ganz wichtig in der Klausur.

01:07:52.960 --> 01:07:56.240
Ja, sonst weiß man ja gar nicht, was ihr da jetzt wirklich vorhattet.

01:07:56.800 --> 01:07:58.860
Ob ihr vielleicht vorhattet, was anderes damit zu zeigen.

01:07:58.960 --> 01:08:00.760
Also schreibt immer so einen Antwortsatz drunter.

01:08:03.140 --> 01:08:04.840
Das ist auch in den Übungsblättern wichtig.

01:08:05.040 --> 01:08:07.000
Hoffentlich sind die Tutoren da ausreichend streng.

01:08:11.150 --> 01:08:11.590
Gut.

01:08:12.410 --> 01:08:15.050
Es gibt da jetzt eben auch noch andere Varianten.

01:08:15.210 --> 01:08:18.730
Wenn man mehr Spieler reinmachen will, dann kriegen die einfach für

01:08:18.730 --> 01:08:23.070
jede Zahl, die irgendwo auf einem der Steine von den anderen Spielern

01:08:23.070 --> 01:08:25.530
auftaucht, so einen Doppelstein.

01:08:26.330 --> 01:08:29.770
Das heißt, jeder von diesen anderen hat doppelt so viele Steine wie

01:08:29.770 --> 01:08:31.390
Spieler 1 und Spieler 2 zusammen.

01:08:31.990 --> 01:08:34.410
Und die können nichts machen, außer das Ganze irgendwie in die Länge

01:08:34.410 --> 01:08:39.070
ziehen, indem sie einfach immer solche Identitätssteine da hinlegen.

01:08:39.070 --> 01:08:42.870
Das heißt, für beliebige feste Anzahlen von Spielern ist das auch NP

01:08:42.870 --> 01:08:43.470
-vollständig.

01:08:44.790 --> 01:08:46.650
Mit einem Spieler allerdings nicht.

01:08:46.770 --> 01:08:48.170
Dadurch wird es eine Eulabfahrt.

01:08:49.290 --> 01:08:50.950
Die Reduktion habe ich jetzt noch dabei.

01:08:51.590 --> 01:08:53.990
Da haben wir ja gerade gesehen, dass das polynomial ist.

01:08:55.710 --> 01:09:00.230
Und wenn die Spieler sich auch noch feindlich gesinnt sind und jeder

01:09:00.230 --> 01:09:04.450
gerne gewinnen würde, dann ist das Ganze sogar PSPACE-vollständig.

01:09:04.650 --> 01:09:07.350
Aber die Reduktion war mir auch ein bisschen zu abgefahren, um die

01:09:07.350 --> 01:09:08.390
jetzt in der Übung zu machen.

01:09:10.650 --> 01:09:13.690
Zumal wir ja eigentlich keine wirklich PSPACE-vollständigen Probleme

01:09:13.690 --> 01:09:14.070
kennen.

01:09:17.230 --> 01:09:21.410
Dann vielleicht ein etwas moderneres Spiel, was vielleicht ein paar

01:09:21.410 --> 01:09:23.030
von euch kennen, Portal 2.

01:09:23.850 --> 01:09:25.730
Das ist auch NP-vollständig.

01:09:27.230 --> 01:09:28.550
Sorry, es ist NP-schwer.

01:09:29.210 --> 01:09:30.430
Ich weiß nicht, ob es in NP liegt.

01:09:33.290 --> 01:09:33.690
Wahrscheinlich.

01:09:33.870 --> 01:09:35.890
Das ist ein bisschen kompliziert zu formalisieren.

01:09:36.330 --> 01:09:41.450
Ja gut, es kann ja PSPACE-vollständig sein und in NP liegen.

01:09:46.900 --> 01:09:47.700
Ja stimmt.

01:09:47.880 --> 01:09:50.040
Es ist vermutlich in PSPACE, nicht in NP.

01:09:52.360 --> 01:09:54.740
Da kann man ganz gut Reiser drauf reduzieren.

01:09:54.820 --> 01:09:58.520
Dazu braucht man hier unten, man sieht es kaum, hier sind so Buttons,

01:09:58.640 --> 01:10:02.740
wo man Kisten drauflegen kann und passende Kisten daneben.

01:10:03.260 --> 01:10:05.740
Hier gibt man im Grunde die Variablenbelegung ein.

01:10:06.640 --> 01:10:08.930
Also es sind 6 Variablen und hier sind die 8 Klauseln.

01:10:22.960 --> 01:10:25.060
Jetzt sieht man es vielleicht etwas besser.

01:10:25.200 --> 01:10:28.980
Es gibt da leider nur diesen Low-Res-Screenshot und das lief gestern

01:10:28.980 --> 01:10:29.960
auf unserem Rechner nicht.

01:10:32.320 --> 01:10:35.280
Man sieht hier, das sind solche Kugeldispenser.

01:10:36.240 --> 01:10:37.560
Ich weiß nicht, ob ihr die seht.

01:10:37.660 --> 01:10:39.780
Das sind 3 pro Klausel.

01:10:40.900 --> 01:10:42.940
Da fällt dann irgendwo so eine Kugel raus.

01:10:43.500 --> 01:10:48.580
Und hier sind so Trapdoors, die verhindern, dass die Kugel rausfällt.

01:10:48.700 --> 01:10:51.520
Also die hier ist oben, die verhindert, dass hier die Kugel rausfällt

01:10:51.520 --> 01:10:54.100
und die beiden sind runtergeklappt, die können runterfallen.

01:10:54.480 --> 01:10:57.720
Dann ist unten ein Funnel, der das Ganze von links nach rechts trägt

01:10:57.720 --> 01:11:00.680
und am rechten Ende ist dann so ein Button, der nur von der Kugel

01:11:00.680 --> 01:11:01.760
ausgelöst werden kann.

01:11:03.360 --> 01:11:07.720
Das heißt, sobald eine Kugel irgendwie runterfällt, wird diese Klausel

01:11:07.720 --> 01:11:14.800
erfüllt und die werden dann alle noch mit dieser Konstruktion

01:11:16.720 --> 01:11:17.680
irgendwie verundet.

01:11:19.560 --> 01:11:21.900
Und dann gibt es noch irgendwo einen Knopf, den sieht man hier auf dem

01:11:21.900 --> 01:11:24.880
Bild, mit dem man das Ganze dann auslösen kann.

01:11:24.960 --> 01:11:26.400
Dann fallen die ganzen Kugeln runter.

01:11:27.000 --> 01:11:29.660
Dann muss man 2 Sekunden warten, bis die Funnel alles nach rechts

01:11:29.660 --> 01:11:33.000
getragen haben und wenn dann jede Klausel erfüllt ist, dann geht die

01:11:33.000 --> 01:11:33.500
Tür auf.

01:11:34.960 --> 01:11:39.360
Das heißt, man kann relativ einfach 3 Satz auf Portal 2 reduzieren.

01:11:39.920 --> 01:11:42.800
Das Lustige dabei ist eigentlich, dass keine Portale involvt sind.

01:11:43.660 --> 01:11:45.620
Eigentlich würde man ja denken, dass das das Schwere ist.

01:11:46.220 --> 01:11:47.040
Aber das reicht schon.

01:11:49.460 --> 01:11:54.060
Es gibt auch eine Reduktion von Quantified Boolean Formulas.

01:11:54.720 --> 01:11:56.760
So eines der PSPACE vollständigen Probleme.

01:11:56.760 --> 01:12:01.900
Aber die war zu kompliziert, um sie irgendwie von den Vorschaubildchen

01:12:01.900 --> 01:12:02.540
zu erkennen.

01:12:04.560 --> 01:12:06.110
War auch eher unvollständig.

01:12:10.210 --> 01:12:10.990
Gut.

01:12:11.530 --> 01:12:12.370
Dann übergebe ich wieder.

01:12:19.840 --> 01:12:20.120
Okay.

01:12:22.440 --> 01:12:23.220
Ja.

01:12:24.500 --> 01:12:27.440
Ich bin wieder zuständig für die nerdigeren Probleme.

01:12:29.180 --> 01:12:31.540
Und zwar Super Mario World.

01:12:32.260 --> 01:12:35.840
Die selbe Konstruktion funktioniert wahrscheinlich auch für Super

01:12:35.840 --> 01:12:37.900
Mario Spiele, die ihr irgendwann gespielt habt.

01:12:38.540 --> 01:12:40.680
Ich habe vor allem Super Mario World gespielt.

01:12:40.780 --> 01:12:42.920
Deswegen machen wir es damit.

01:12:43.460 --> 01:12:45.840
Ich glaube, es funktioniert auch mit neueren Marios.

01:12:46.060 --> 01:12:49.660
Aber ihr könnt mir sagen, wenn ein Problem besteht.

01:12:51.060 --> 01:12:51.200
Gut.

01:12:51.300 --> 01:12:52.720
Wir reduzieren 3 Satz.

01:12:52.820 --> 01:12:53.760
Ganz normales 3 Satz.

01:12:55.540 --> 01:12:58.380
Und dazu brauchen wir irgendwelche variablen Gadgets.

01:12:59.300 --> 01:13:01.560
Die negiert oder nicht negiert sein können.

01:13:01.940 --> 01:13:03.020
Und irgendwelche Klausel-Gadgets.

01:13:04.740 --> 01:13:08.800
Und dann brauchen wir irgendeine Möglichkeit, um die Variablen zu

01:13:08.800 --> 01:13:10.420
wählen und die Klauseln auszuwerten.

01:13:10.580 --> 01:13:13.520
Was irgendwie auf den ersten Blick komisch aussieht.

01:13:14.340 --> 01:13:16.980
Auf jeden Fall, ein Mario-Level hat irgendwo einen Start und irgendwo

01:13:16.980 --> 01:13:17.420
ein Ende.

01:13:18.260 --> 01:13:19.500
Und die müssen wir erstmal bauen.

01:13:22.360 --> 01:13:26.040
Und was wir dann machen ist, wir gehen vom Start aus in die Variablen

01:13:26.040 --> 01:13:26.380
rein.

01:13:27.640 --> 01:13:31.280
Wir werden uns hier etwas aussuchen, was wir machen.

01:13:32.060 --> 01:13:35.160
Also entweder die Variable auf True setzen oder sie auf False setzen.

01:13:36.000 --> 01:13:39.920
Und je nachdem, wie wir das machen, kommen wir zu anderen Klauseln.

01:13:40.960 --> 01:13:43.740
Zum Beispiel, wenn wir die Variable auf False setzen, kommen wir

01:13:43.740 --> 01:13:46.500
natürlich zu der Klausel, die die Variable auf False hat.

01:13:47.080 --> 01:13:48.560
Wir werden hier irgendwas verändern.

01:13:49.420 --> 01:13:53.380
Und gehen dann zurück zur nächsten Variable.

01:13:54.740 --> 01:13:56.440
Das ist erstmal die Idee.

01:13:57.700 --> 01:14:01.460
Also wir suchen uns etwas aus, setzen alle Klauseln, die damit etwas

01:14:01.460 --> 01:14:05.520
zu tun haben, verändern da etwas und gehen dann zurück zur nächsten

01:14:05.520 --> 01:14:05.980
Variable.

01:14:06.080 --> 01:14:07.180
Wir suchen uns für die etwas aus.

01:14:07.940 --> 01:14:09.260
Und das machen wir für alle Variablen.

01:14:12.100 --> 01:14:18.900
Und dann am Ende müssen wir jetzt noch schauen, dass alle Klauseln

01:14:18.900 --> 01:14:19.640
erfüllt worden sind.

01:14:19.740 --> 01:14:21.560
Also dass wir in allen Klauseln etwas gemacht haben.

01:14:21.560 --> 01:14:25.000
Das heißt, am Ende gehen wir noch mal durch alle Klauseln durch und

01:14:25.000 --> 01:14:25.720
überprüfen das.

01:14:27.180 --> 01:14:30.920
Das hört sich jetzt erstmal relativ kompliziert an oder es hört sich

01:14:30.920 --> 01:14:31.960
auf jeden Fall abstrakt an.

01:14:33.080 --> 01:14:37.840
Im Endeffekt bricht es runter auf fünf Gadgets, die man braucht.

01:14:38.260 --> 01:14:43.300
Man braucht ein Gadget für den Start, weil man sollte vielleicht etwas

01:14:43.300 --> 01:14:44.500
speziell anfangen.

01:14:45.680 --> 01:14:48.460
Man braucht Gadgets für diese Variablenbelegung.

01:14:49.600 --> 01:14:51.580
Man braucht Klausel-Gadgets.

01:14:51.720 --> 01:14:53.460
Man braucht am Ende ein Ziel-Gadget.

01:14:55.180 --> 01:14:58.220
Und Super Mario World ist zweidimensional und diese Dinger kreuzen

01:14:58.220 --> 01:14:58.840
sich hier überall.

01:14:59.320 --> 01:15:03.080
Das heißt, wir brauchen jetzt noch ein Gadget, das sicherstellt, dass

01:15:03.080 --> 01:15:08.820
wir zwei Wege durcheinander durchleiten können, aber man nicht in den

01:15:08.820 --> 01:15:09.680
anderen reinkommt.

01:15:09.920 --> 01:15:13.000
Also wenn ich von hier komme, sollte ich nicht noch nach hier gehen

01:15:13.000 --> 01:15:13.280
können.

01:15:14.400 --> 01:15:19.180
Sonst könnte ich mit dieser einen Nicht-Belegung zwei Sachen auf True

01:15:19.180 --> 01:15:21.060
setzen, die nicht zusammengehören.

01:15:21.400 --> 01:15:24.840
Das heißt, ich muss sicherstellen, dass ich von einem Weg hier nicht

01:15:24.840 --> 01:15:26.380
in den anderen Weg reinkomme.

01:15:27.360 --> 01:15:28.600
Und das ist alles, was ich machen muss.

01:15:29.200 --> 01:15:31.920
Also wir haben fünf Gadgets, die wir uns jetzt überlegen müssen.

01:15:33.880 --> 01:15:36.980
Und das Start- und das Ziel-Gadget sind relativ einfach.

01:15:37.640 --> 01:15:41.480
Für die ganze Konstruktion ist wichtig, dass Mario fast die ganze Zeit

01:15:41.480 --> 01:15:41.940
groß ist.

01:15:44.840 --> 01:15:49.580
Deswegen nehmen wir am Anfang einen Pilz und am Ende müssen wir

01:15:49.580 --> 01:15:51.080
überprüfen, dass er immer noch groß ist.

01:15:51.460 --> 01:15:53.240
Das heißt, wir machen hier so einen gelben Stein hin.

01:15:53.900 --> 01:15:56.440
Den kann man von oben nur kaputt machen, wenn man ein großer Mario

01:15:56.440 --> 01:15:56.660
ist.

01:15:56.740 --> 01:15:57.800
Dann gibt es diesen Spin-Kick.

01:15:59.740 --> 01:16:03.400
Das heißt, dieses Gadget überprüft, dass wir groß sind und am Anfang

01:16:03.400 --> 01:16:04.380
bauen wir so einen Pilz.

01:16:04.480 --> 01:16:06.200
Das heißt, wir werden am Anfang groß.

01:16:07.220 --> 01:16:08.460
Super, das ist schon mal der Anfang.

01:16:10.860 --> 01:16:12.280
Jetzt brauchen wir irgendwelche Variablenbelegungen.

01:16:13.320 --> 01:16:16.620
Wo wir uns aussuchen können, gehen wir den linken Weg lang oder den

01:16:16.620 --> 01:16:17.380
rechten Weg lang.

01:16:17.700 --> 01:16:19.700
Aber wir dürfen auf keinen Fall beides können.

01:16:20.860 --> 01:16:22.340
Das hört sich irgendwie schon einfach an.

01:16:23.260 --> 01:16:25.680
Das Bild ist jetzt leider nicht aus Super Mario World, sondern aus

01:16:25.680 --> 01:16:26.620
Super Mario Brothers.

01:16:27.720 --> 01:16:30.620
Das Paper, das hier unten auch nochmal aufgeschrieben steht, das könnt

01:16:30.620 --> 01:16:33.640
ihr gerne anschauen, da wird es für alle möglichen Nintendo-Spiele

01:16:33.640 --> 01:16:36.340
gezeigt, dass sie NP-hard sind.

01:16:38.700 --> 01:16:41.360
Für manche sind sie PSP-hard.

01:16:44.040 --> 01:16:49.160
Für alle Super Mario-Teile lässt sich zeigen, dass sie NP-hard sind.

01:16:49.640 --> 01:16:51.560
Entschuldigung, wenn ich mal NP-vollständig gesagt habe.

01:16:54.100 --> 01:16:55.860
Man weiß nicht, ob sie in NP sind.

01:16:57.440 --> 01:16:58.700
Aber sie sind NP-hard.

01:17:00.060 --> 01:17:02.900
Dieses Gadget erlaubt uns jetzt zu entscheiden, gehen wir links lang

01:17:02.900 --> 01:17:03.760
oder rechts lang.

01:17:04.180 --> 01:17:06.620
Wenn wir links lang gegangen sind, kommen wir nie wieder nach rechts.

01:17:07.240 --> 01:17:09.640
Und wenn wir rechts lang gegangen sind, kommen wir erst mal nie wieder

01:17:09.640 --> 01:17:10.060
nach links.

01:17:10.800 --> 01:17:13.000
Was auch wichtig ist, es gibt zwei Eingänge.

01:17:13.760 --> 01:17:16.820
Und von den Eingängen kann man nicht in den anderen wechseln.

01:17:17.900 --> 01:17:19.700
Weil wir haben ja hier dann später...

01:17:20.500 --> 01:17:23.580
Hier kommen wir von der einen Seite und hier von der anderen Seite.

01:17:24.160 --> 01:17:26.860
Und es wäre schlecht, wenn wir zu der anderen Seite wieder zurückgehen

01:17:26.860 --> 01:17:27.240
könnten.

01:17:27.340 --> 01:17:29.720
Dann können wir für eine Variable gleichzeitig True und False

01:17:29.720 --> 01:17:30.160
auswählen.

01:17:30.900 --> 01:17:31.740
Das geht nicht.

01:17:32.740 --> 01:17:34.220
Wir haben dieses Variablen-Gadget.

01:17:34.340 --> 01:17:35.180
Das ist total einfach.

01:17:36.040 --> 01:17:37.560
Wir können links lang oder rechts lang.

01:17:38.340 --> 01:17:40.180
Jetzt brauchen wir Klausel-Gadgets.

01:17:40.960 --> 01:17:41.940
Die sind interessanter.

01:17:44.660 --> 01:17:46.040
Wahrscheinlich macht man dieses hier.

01:17:46.860 --> 01:17:48.760
Das hier ist für Super Mario Bros.

01:17:49.020 --> 01:17:49.320
2.

01:17:50.860 --> 01:17:54.200
Was hier passiert, es gibt drei Eingänge, zu denen man reinkommen

01:17:54.200 --> 01:17:54.440
kann.

01:17:54.560 --> 01:17:55.740
Da kommen die drei Klauseln her.

01:17:57.220 --> 01:17:59.820
Und hier kann Mario dieses Fragezeichen auslösen.

01:17:59.940 --> 01:18:01.700
Und dieses Fragezeichen produziert einen Stern.

01:18:03.080 --> 01:18:03.880
Sterne sind super.

01:18:04.420 --> 01:18:06.420
Sterne bleiben dann in diesem Kästchen hier drin.

01:18:06.500 --> 01:18:07.480
Die springen da hin und her.

01:18:08.060 --> 01:18:11.940
Und später, wenn man zurückkommt, kann man diesen Stern aufsammeln.

01:18:13.320 --> 01:18:14.840
Und man braucht diesen Stern.

01:18:15.020 --> 01:18:16.060
Sterne machen unverwundbar.

01:18:16.100 --> 01:18:18.540
Man braucht diesen Stern, um hier durch dieses ganze Feuer

01:18:18.540 --> 01:18:19.160
durchzukommen.

01:18:19.680 --> 01:18:22.860
Das heißt, an jeder Klausel wird man später einmal hingehen.

01:18:23.160 --> 01:18:24.380
Schauen, liegt da ein Stern?

01:18:24.600 --> 01:18:27.020
Wenn da kein Stern liegt, dann stirbt man in dem Feuer.

01:18:27.780 --> 01:18:30.020
Und wenn da ein Stern liegt, kommt man über das Feuer drüber.

01:18:32.180 --> 01:18:36.900
Man baut diese Gadgets weit genug auseinander, dass man nicht einen

01:18:36.900 --> 01:18:39.780
Stern für mehrere von diesen Klauseln verwenden kann.

01:18:41.100 --> 01:18:42.140
Aber so macht man das.

01:18:43.120 --> 01:18:44.160
In Super Mario Bros.

01:18:44.320 --> 01:18:45.480
2 läuft es ein bisschen anders.

01:18:45.480 --> 01:18:46.720
Da gibt es diese Schildkröten.

01:18:48.600 --> 01:18:49.700
Auf die kann man draufspringen.

01:18:49.900 --> 01:18:52.000
Also es gibt drei Eingänge, auf die kann man draufspringen.

01:18:52.640 --> 01:18:58.220
Dann fliegt der Panzer von der Schildkröte hier nach unten, geht in

01:18:58.220 --> 01:19:01.760
diese Röhre rein, macht dieses Teil hier kaputt und fliegt dann nach

01:19:01.760 --> 01:19:02.280
unten weg.

01:19:03.140 --> 01:19:06.120
Und später wird man dann hier durchlaufen können durch diesen Weg.

01:19:06.820 --> 01:19:09.960
Das machen wir nicht in Super Mario World, weil in Super Mario World

01:19:09.960 --> 01:19:13.600
könnte Mario hingehen, diese Panzer aufnehmen, später mitnehmen, eine

01:19:13.600 --> 01:19:15.700
andere Klausel damit noch erfüllen oder sonst was.

01:19:17.820 --> 01:19:20.880
Das heißt, in Super Mario World gehen wir eher diesen Weg.

01:19:21.500 --> 01:19:23.020
Es sieht ein bisschen anders aus wie das.

01:19:23.160 --> 01:19:26.760
Und zwar gibt es in Super Mario World anscheinend keine Feuerstangen

01:19:26.760 --> 01:19:26.960
mehr.

01:19:27.020 --> 01:19:28.740
An die konnte ich mich jetzt auch nicht erinnern.

01:19:29.880 --> 01:19:31.880
Stattdessen nehmen wir solche Muscheln.

01:19:32.820 --> 01:19:33.900
Muscheln fressen dich auch.

01:19:35.380 --> 01:19:37.560
Wenn du einen Stern hast, kannst du über Muscheln drüber laufen.

01:19:38.160 --> 01:19:39.600
Im Endeffekt funktioniert alles genauso.

01:19:39.600 --> 01:19:45.080
Wir kommen dann von unseren Variablen hier hin, lösen diesen Stern

01:19:45.080 --> 01:19:46.540
aus, dann ist hier ein Stern drin.

01:19:48.040 --> 01:19:53.340
Und später, wenn wir dann wiederkommen, können wir hier hingehen, den

01:19:53.340 --> 01:19:55.480
Stern nehmen und über diese Muscheln drüber laufen.

01:19:57.020 --> 01:19:59.860
Und dann müssen wir das für das nächste Gadget auch machen und so

01:19:59.860 --> 01:20:00.060
weiter.

01:20:00.920 --> 01:20:02.680
Das heißt, das Prinzip ist eigentlich relativ klar.

01:20:02.940 --> 01:20:08.200
Wir kommen hier rein, erfüllen beliebig viele Klauseln mit dieser

01:20:08.200 --> 01:20:09.000
einen Belegung.

01:20:09.640 --> 01:20:12.400
Hier zum Beispiel kann man zwei Klauseln erfüllen.

01:20:13.080 --> 01:20:17.860
Man sucht sich Y aus, geht hier nach links, löst diesen Stern aus,

01:20:17.980 --> 01:20:26.900
geht zurück, geht hier hin, löst diesen Stern aus und geht dann

01:20:26.900 --> 01:20:28.020
weiter.

01:20:30.000 --> 01:20:32.880
Das Problem, was wir jetzt noch haben, und wahrscheinlich das

01:20:32.880 --> 01:20:38.140
komplexeste Gadget in der ganzen Konstruktion, sind diese Kreuzungen,

01:20:38.280 --> 01:20:39.100
die wir noch machen müssen.

01:20:39.640 --> 01:20:43.440
Es muss sichergestellt sein, dass wir an diesen Kreuzungen nicht

01:20:43.440 --> 01:20:44.180
abweichen können.

01:20:45.540 --> 01:20:47.100
Und dazu gibt es dieses witzige Gadget.

01:20:49.800 --> 01:20:53.000
Das ist auch der Punkt, wo ich mir nicht ganz sicher bin, ob es in

01:20:53.000 --> 01:20:55.720
einem modernen Super-Mario-Spiel noch funktioniert.

01:20:58.120 --> 01:21:02.560
Wir gehen davon aus, dass wir immer zuerst von links kommen und dann

01:21:02.560 --> 01:21:04.180
dürfen wir nicht nach oben oder unten können.

01:21:04.800 --> 01:21:08.840
Und dann kommen wir irgendwann von oben und dürfen nur nach unten

01:21:08.840 --> 01:21:09.160
können.

01:21:10.960 --> 01:21:12.080
Unser Mario ist groß.

01:21:13.200 --> 01:21:16.300
Das heißt, er kommt hier nicht durch, eigentlich.

01:21:17.280 --> 01:21:19.860
Was wir machen müssen, um hier durchzukommen, ist, wir müssen diesen

01:21:19.860 --> 01:21:21.280
Gegner uns einmal treffen lassen.

01:21:22.580 --> 01:21:23.720
Dann wird man klein.

01:21:24.580 --> 01:21:29.160
Dann kann man hier durch dieses Gadget durchlaufen, kann sich hier

01:21:29.160 --> 01:21:30.760
wieder groß machen und kommt hier raus.

01:21:31.280 --> 01:21:33.620
Das ist auch die einzige Möglichkeit, wie man hier durchgehen kann.

01:21:33.620 --> 01:21:37.720
Man kann hier nur durch, wenn man sich klein macht, weil diese Blöcke

01:21:37.720 --> 01:21:40.880
sind so gesetzt, dass man auch nicht irgendwie drunter durchrutschen

01:21:40.880 --> 01:21:41.260
kann.

01:21:43.460 --> 01:21:46.280
Also so Schwung nehmen und rutschen, das geht nicht.

01:21:47.000 --> 01:21:49.460
Also hier kommt man nur durch, wenn man sich klein macht und sich hier

01:21:49.460 --> 01:21:50.100
wieder groß macht.

01:21:52.380 --> 01:21:53.980
Der andere ist ganz einfach.

01:21:54.360 --> 01:21:57.580
Wenn wir groß sind und von oben kommen, können wir diese Steine hier

01:21:57.580 --> 01:21:59.040
kaputt machen und nach unten hindurchfallen.

01:21:59.820 --> 01:22:02.340
Genau, das sind die zwei Wege.

01:22:03.780 --> 01:22:07.280
Wenn wir hier von oben groß kommen, können wir nicht seitlich

01:22:07.280 --> 01:22:07.760
rausgehen.

01:22:08.920 --> 01:22:12.420
Und wenn wir hier uns klein gemacht haben, können wir nicht nach unten

01:22:12.420 --> 01:22:15.380
weitergehen, weil der kleine Mario die gelben Blöcke nicht kaputt

01:22:15.380 --> 01:22:15.640
kriegt.

01:22:17.180 --> 01:22:18.620
Und das ist alles, was man braucht.

01:22:19.600 --> 01:22:22.940
Wir haben jetzt im Endeffekt diesen ganzen Graph, können wir aufbauen.

01:22:25.080 --> 01:22:30.400
Und sollte es möglich sein, hier als großer Mario anzukommen, dann

01:22:30.400 --> 01:22:36.180
gibt es für diese Satzinstanz eine erfüllende Belegung.

01:22:36.880 --> 01:22:42.720
Und damit ist klar, Super Mario World Level zu meistern, ist irgendwie

01:22:42.720 --> 01:22:43.380
NP -hart.

01:22:45.860 --> 01:22:50.120
Das heißt, ihr seid wahrscheinlich relativ gut darin, manche NP-harte

01:22:50.120 --> 01:22:50.980
Probleme zu lösen.

01:22:52.260 --> 01:22:54.660
Gut, dann wäre es das für heute.