WEBVTT 00:07.230 --> 00:10.470 Guten Morgen, herzlich willkommen zur heutigen Vorlesung. 00:11.130 --> 00:16.670 Wir hatten in der letzten Vorlesung ja am Ende so einige Themen 00:16.670 --> 00:23.010 behandelt, die praktisch über die Klasse NP, NP-vollständige Probleme, 00:23.130 --> 00:25.130 so ein bisschen hinausragt. 00:27.610 --> 00:32.510 Und das wird uns auch heute und am Donnerstag noch beschäftigen. 00:32.510 --> 00:35.710 Sozusagen die Frage, wenn man jetzt also diese Theorie der NP 00:35.710 --> 00:43.650 -Vollständigkeit hat, die Klassen P, NP und NP-vollständig kennt, was 00:43.650 --> 00:45.530 ist in dem Kontext noch interessant? 00:45.810 --> 00:48.850 Ist sozusagen die Welt so einfach, dass es nur diese Klassen gibt oder 00:48.850 --> 00:53.730 gibt es eben noch Probleme, die rausfallen aus der Klasse, etwa, die 00:53.730 --> 00:58.090 noch schwerer sind als NP-vollständige Probleme oder nicht in NP sind, 00:58.170 --> 01:01.850 aber mindestens so schwer wie alle NP-vollständigen oder NP 01:01.850 --> 01:06.230 -vollständig sind, aber trotzdem irgendwie einfacher in gewisser 01:06.230 --> 01:09.050 Hinsicht sind als andere NP-Vollständige. 01:09.370 --> 01:12.890 Also diesen Kontext werden wir im Prinzip behandeln. 01:13.830 --> 01:17.970 Und ein Aspekt in dem Kontext ist eben erstmal, wie sieht denn wohl 01:17.970 --> 01:22.850 vermeintlich die Welt aus bezüglich der Komplexitätsklassen, die wir 01:22.850 --> 01:23.170 kennen? 01:23.170 --> 01:30.270 Und das hatte ich letztes Mal schon gezeigt. 01:35.000 --> 01:43.020 Wenn wir hier die Klasse NP haben, dann liegt offensichtlich P dort 01:43.020 --> 01:47.400 drin, aber möglicherweise sonst auch gar nichts. 01:48.340 --> 01:51.580 Wahrscheinlicher ist aber, dass da eben noch mehr drin liegt. 01:51.680 --> 01:56.020 Und es ist klar, welche Probleme da auch noch drin liegen, per 01:56.020 --> 02:00.660 Definition, die NP-Vollständigen, sozusagen die schwersten in NP. 02:02.160 --> 02:05.120 Hier schreibe ich hier NPC für NP-Complete. 02:05.980 --> 02:10.360 Und es ist klar, dass wenn unsere generelle Vermutung gilt, dass P 02:10.360 --> 02:14.740 ungleich NP ist, NPC und P disjunkt sind. 02:15.220 --> 02:15.700 Das ist klar. 02:16.980 --> 02:20.860 Da sind ja gerade die NP-Vollständigen definiert, dass wenn auch nur 02:20.860 --> 02:25.740 eines von denen in P liegen würde, P gleich NP wäre. 02:27.080 --> 02:30.140 So, jetzt ist aber die Frage, gibt es da noch was dazwischen? 02:33.850 --> 02:36.650 Gibt es da so ein NP-Intermediate, 02:40.180 --> 02:45.540 das wirklich eine echte Menge ist, also Probleme, die in NP liegen, 02:45.980 --> 02:48.000 aber weder in P noch in NPC? 02:48.900 --> 02:51.440 Die Vermutung ist, ja, das gibt es. 02:51.920 --> 02:55.820 Und wir werden gleich ein Problem kennenlernen, wenn das Kandidat ist, 02:55.960 --> 02:57.380 genau da reinzufallen. 02:58.020 --> 03:02.400 Und andererseits hatten wir die Klasse QNP betrachtet. 03:02.580 --> 03:08.040 Das sind die Probleme, die Komplementprobleme von Problemen aus NP 03:08.040 --> 03:08.340 sind. 03:10.460 --> 03:12.080 QNP heißt diese Klasse. 03:13.540 --> 03:16.860 Und die liegt vermutlich, so wie ich es hier eingezeichnet habe, 03:16.860 --> 03:25.600 zunächst mal so eine große Frage und auch Vermutung, dass NP und QNP 03:27.830 --> 03:30.610 verschieden sind. 03:31.930 --> 03:33.070 Und wenn dem so ist, 03:37.560 --> 03:46.500 dann ist sogar NP geschnitten mit QNP leer. 03:48.280 --> 04:01.080 Also so sieht das wahrscheinlich aus, dass QNP hier so rausragt und 04:01.080 --> 04:04.080 insbesondere das Jungt ist von NPC. 04:05.000 --> 04:09.720 Dass P in QNP ist, ist wiederum klar, weil QP gleich P ist. 04:10.100 --> 04:11.560 All das hatten wir uns das letzte Mal überlegt. 04:11.560 --> 04:17.180 So, jetzt gehen wir mal auf den Punkt hier ein. 04:17.340 --> 04:23.660 Gibt es Probleme, die zwischen P und NPC liegen, aber sehr wohl in NP? 04:24.440 --> 04:30.200 Ich will Ihnen nur den Kandidaten eines Problems, das da vermutlich 04:30.200 --> 04:33.540 liegt, wenn P ungleich NP ist, vorstellen. 04:33.720 --> 04:35.660 Wir werden hier nichts weiter darüber beweisen. 04:37.400 --> 04:42.660 Der Kandidat ist das Problem Grafisomorphie. 04:44.040 --> 04:48.680 Es kommt gleich auch die formelle Definition, aber ich erläuter Ihnen 04:48.680 --> 04:50.040 das jetzt erst mal am kleinen Beispiel. 04:50.760 --> 04:53.880 Also es gibt so zwei Varianten von Grafisomorphie. 04:53.880 --> 04:57.800 Das ist die Subgrafisomorphie. 05:04.700 --> 05:08.980 Da hat man gegeben zwei Grafen, einen Grafen G und einen Grafen H. 05:10.240 --> 05:13.460 G könnte zum Beispiel folgendermaßen aussehen. 05:39.770 --> 05:42.270 Und jetzt einen kleineren Grafen H. 05:53.600 --> 05:59.680 Und die Frage ist, ob ein Graf, der so aussieht wie H, in G enthalten 05:59.680 --> 06:00.140 ist. 06:26.530 --> 06:30.650 Also Isomorphie kennen Sie, Sie haben eine 1 zu 1 Abbildung, wo Sie 06:30.650 --> 06:36.570 eben auf Knoten abbilden und dadurch Kanten induziert werden. 06:37.810 --> 06:42.270 Aber für die Anschauung einfach ein Graf, der so aussieht wie H, ob so 06:42.270 --> 06:43.370 einer in G drin ist. 06:43.470 --> 06:46.450 Das ist die Frage bei Subgrafisomorphie. 06:53.080 --> 06:55.380 Ich denke mal, so einen finden wir hier. 07:28.400 --> 07:30.980 Diese zweieinanderhängenden Vierecke haben wir zum Beispiel an der 07:30.980 --> 07:31.340 Stelle. 07:50.400 --> 07:53.680 Das ist nicht richtig, weil wir hier noch eine Kante drin haben, die 07:53.680 --> 07:54.660 hier nicht drin ist. 07:57.960 --> 08:04.440 Üblich müssen wir ein bisschen nachbessern. 08:07.660 --> 08:09.880 Das ist Subgrafisomorphie. 08:10.860 --> 08:14.980 Grafisomorphie, da haben Sie zwei Grafen gegeben, die gleich groß 08:14.980 --> 08:15.360 sind. 08:52.800 --> 08:53.440 So. 08:54.780 --> 09:03.840 Und die Frage ist, ist G Isomorph zu H? 09:04.940 --> 09:10.220 Also finden Sie eine 1 zu 1 Abbildung zwischen den Knoten von G und H, 09:10.860 --> 09:14.920 sodass die dadurch induzierten Kanten in G auch in H sind. 09:18.920 --> 09:24.600 Ja gut, Sie haben ja gesehen, dass ich das H im Prinzip so hingemalt 09:24.600 --> 09:26.860 habe, dass man sieht, die zwei sind Isomorph. 09:26.980 --> 09:30.100 Also wenn Sie das hier rausklappen, da sehen Sie die zwei, das sind 09:30.100 --> 09:30.540 dieselben. 09:31.980 --> 09:35.340 Also das heißt, dieses Problem sieht jetzt ein bisschen einfacher aus 09:35.340 --> 09:37.140 als das Subgrafisomorphie-Problem. 09:37.540 --> 09:40.560 Und es scheint eben auch so zu sein, dass das ein bisschen einfacher 09:40.560 --> 09:40.620 ist. 09:40.620 --> 09:45.740 Subgrafisomorphie ist ein NP-Vollständiges Problem. 09:46.480 --> 09:50.860 Grafisomorphie ist ein Kandidat zwischen den NP-Vollständigen 09:50.860 --> 09:53.560 Problemen und dem Problem NP. 09:54.940 --> 10:00.960 Für die Probleme zwischen den NP-Vollständigen und den NP innerhalb 10:00.960 --> 10:01.660 von NP. 10:03.080 --> 10:11.080 So und jetzt die Definition dazu, also was ist mit Subgrafisomorphie 10:11.080 --> 10:11.920 gemeint? 10:12.160 --> 10:17.600 Sie haben gegeben zwei Grafen G und H und die Knotenmenge von H ist 10:17.600 --> 10:22.660 eine Menge von Knoten, die kleinere Kardinalität hat als die 10:22.660 --> 10:23.940 Knotenmenge von G. 10:24.660 --> 10:28.760 Und die Frage ist, gibt es jetzt eine Teilmenge der Knotenmenge von G, 10:28.760 --> 10:33.540 die gleiche Kardinalität hat wie die Knotenmenge von H und eine 10:33.540 --> 10:40.900 bioaktive Abbildung zwischen den Knoten in H und den Knoten in dieser 10:40.900 --> 10:47.500 Teilmenge, der Knotenmenge von G, so dass für alle Paare von Knoten 10:47.500 --> 10:53.000 aus der Knotenmenge von H gilt, wenn die beiden Knoten in H durch eine 10:53.000 --> 10:59.420 Kante verbunden sind, dann sind deren Bildknoten in G ebenfalls durch 10:59.420 --> 11:01.440 eine Kante verbunden und umgekehrt. 11:04.400 --> 11:10.000 Und die Frage ist also, ist H isomorph zu einem Subgraf von G? 11:15.780 --> 11:18.860 Das Problem ist NP-Vollständig, beweisen wir hier nicht. 11:20.100 --> 11:26.580 Das Graf-Isomorphie-Problem ist eine Variante dieses Problems oder ein 11:26.580 --> 11:31.640 Spezialfall, nämlich der Spezialfall, dass G und H die gleiche Anzahl 11:31.640 --> 11:32.920 von Knoten haben. 11:33.160 --> 11:37.080 Also wir haben gegeben den Graf G mit Knotenmenge V und den Graf H mit 11:37.080 --> 11:38.300 Knotenmenge V'. 11:38.590 --> 11:42.180 Und Kardinalität V ist gleich Kardinalität V'. 11:42.180 --> 11:46.180 Und die Frage ist einfach nur, gibt es eine objektive Abbildung 11:46.180 --> 11:54.240 zwischen V' und V, so dass zwei Knoten in H genau dann verbunden sind, 11:54.580 --> 11:57.780 wenn deren Bilder in G verbunden sind. 11:58.480 --> 12:00.820 Also anschaulich sind G und H isomorph. 12:04.390 --> 12:08.910 Das Problem ist ein Kandidat für ein Problem aus NP-Intermediate. 12:13.250 --> 12:13.850 Warum? 12:14.110 --> 12:17.790 Unter anderem, weil Graf-Isomorphie, also dieses Problem, einerseits 12:17.790 --> 12:20.910 in NP liegt, andererseits aber auch in QNP. 12:21.970 --> 12:28.730 Das ist immer ein ganz starkes Indiz dafür, dass ein Problem in NPI 12:28.730 --> 12:29.310 liegt. 12:34.800 --> 12:39.840 Es gibt sozusagen noch stärkere Indizien, aber einfach, dass Sie mal 12:39.840 --> 12:40.420 gesehen haben. 12:40.420 --> 12:45.240 Also es gibt vermutlich auch Probleme, die hier irgendwo liegen. 12:51.200 --> 12:55.640 Zumindest intuitiv kann man das vielleicht auch gerade an diesem 12:55.640 --> 12:59.600 Beispiel, Subgraf-Isomorphie, einem NP-Vollständigen Problem, und der 12:59.600 --> 13:03.280 leichteren Variante, also leichter erscheinenden Variante zumindest, 13:03.760 --> 13:07.240 Graf -Isomorphie nachvollziehen. 13:10.680 --> 13:18.360 Gut, jetzt Beyond-NP ist sozusagen jetzt so ein bisschen die Frage. 13:18.800 --> 13:23.220 Also was gibt es da außerdem noch, sozusagen nah an dieser Klasse NP, 13:23.780 --> 13:28.420 Klasse der NP-Vollständigen Probleme, an Problemstellungen, die man da 13:28.420 --> 13:34.160 irgendwie anordnen kann, noch in Vergleich setzen kann zu diesen 13:34.160 --> 13:38.080 Problemen innerhalb von NP, die aber trotzdem gleich ein bisschen 13:38.080 --> 13:38.980 außerhalb liegen. 13:39.280 --> 13:44.200 Oder aber auch innerhalb von NPC liegen, aber sich dort irgendwie 13:44.200 --> 13:45.740 unterscheiden von anderen Dienen. 13:48.200 --> 13:50.100 Zunächst mal Suchprobleme. 13:50.380 --> 13:58.020 Sie erinnern sich, für die Definition der Klassen P, NP und NPC haben 13:58.020 --> 14:01.300 wir Probleme als Entscheidungsprobleme formuliert. 14:02.340 --> 14:05.660 Das heißt also, so wie die Klassen definiert sind, betreffen die immer 14:05.660 --> 14:07.340 nur Entscheidungsprobleme. 14:08.140 --> 14:12.520 Der Grund, warum wir diese Entscheidungsprobleme angesehen haben, war 14:12.520 --> 14:16.100 insbesondere der, dass man das Entscheiden eines 14:16.100 --> 14:19.380 Entscheidungsproblems, also ob eine vorgegebene Instanz eines 14:19.380 --> 14:23.880 Entscheidungsproblems, Ja-Instanz oder Nein-Instanz ist, genau 14:23.880 --> 14:27.960 dasselbe ist wie das Entscheiden der zugehörigen Sprache. 14:28.880 --> 14:33.700 Also ob ein Wort Element einer vorgegebenen Sprache ist oder nicht. 14:36.300 --> 14:40.680 Und dann haben wir auch gesagt, naja gut, eigentlich interessieren wir 14:40.680 --> 14:43.760 uns für Optimierungsprobleme, aber die kann man ja so als 14:43.760 --> 14:50.540 Entscheidungsproblem formulieren und das Optimierungsproblem, das 14:50.540 --> 14:57.340 entsprechende scheint auch nicht deutlich schwerer zu lösen sein als 14:57.340 --> 14:58.900 das entsprechende Entscheidungsproblem. 14:58.900 --> 15:03.320 Das haben wir an diesem Beispiel Travelling Salesman klar gemacht. 15:04.040 --> 15:06.600 Wenn man ein bisschen Fantasie hat, kommt man aber sehr schnell 15:06.600 --> 15:10.700 darauf, dass es schon auch noch Problemstellungen gibt, die sich nicht 15:10.700 --> 15:14.320 so ohne weiteres als Entscheidungsproblem mehr oder weniger äquivalent 15:14.320 --> 15:18.040 ausdrücken lassen und die vielleicht auch doch irgendwie schwerer sind 15:18.040 --> 15:20.620 als entsprechende Entscheidungsprobleme. 15:21.160 --> 15:24.300 Und eine Sorte von Problemen sind Suchprobleme. 15:24.970 --> 15:28.140 Ein Suchproblem Pi wird beschrieben durch die Menge der 15:28.140 --> 15:36.700 Probleminstanzen, üblich, und die Menge aller Lösungen zu jeweils 15:36.700 --> 15:37.660 einer Instanz. 15:42.270 --> 15:49.290 Die Lösung eines Suchproblems für eine Instanz des Problems definiert 15:49.290 --> 15:52.990 als entweder ein beliebiges Element aus der Menge aller Lösungen, 15:52.990 --> 15:57.010 falls diese Menge ungleich leer ist, oder leer sonst. 15:57.750 --> 16:04.600 Und um solche Suchprobleme herum kann man jetzt Fragen stellen. 16:04.900 --> 16:07.380 Zunächst mal TSP als Suchproblem. 16:13.230 --> 16:15.890 Eine wäre eine Variante, die wir auch schon kennen. 16:16.390 --> 16:22.170 Also Sie haben gegeben eine Instanz zu TSP und die Frage ist, gib eine 16:22.170 --> 16:25.590 optimale Tour zu dieser Instanz an. 16:26.890 --> 16:31.130 In dem Fall wäre also die Menge der Lösungen die Menge aller optimalen 16:31.130 --> 16:31.450 Touren. 16:33.490 --> 16:37.590 Oder Variante eines etwas anders formulierten und etwas anders 16:37.590 --> 16:39.830 gelagerten Suchproblems zu TSP. 16:40.310 --> 16:45.570 Wir haben wieder Ihre TSP-Instanz gegeben und einen Parameter k, einen 16:45.570 --> 16:51.250 Zahlenwert k, und die Frage ist, gib eine Tour an, deren Länge 16:51.250 --> 16:52.550 höchstens k ist. 16:59.220 --> 17:02.760 Ja, deren Länge höchstens k ist, falls eine existiert. 17:03.380 --> 17:08.780 Da ist die Menge der Lösungen, die Menge aller Touren, die eine Länge 17:08.780 --> 17:09.960 kleiner gleich k haben. 17:13.100 --> 17:17.160 Und in dieses Konzept Suchproblem passt zum Beispiel auch folgende 17:17.160 --> 17:20.700 Problemstellung, die so ein bisschen verwandt ist mit TSP. 17:20.700 --> 17:22.700 Wir haben wieder gegeben einen Graph. 17:23.280 --> 17:26.220 In so einem Graph nennt man so eine Tour, die jeden Knoten genau 17:26.220 --> 17:30.560 einmal besucht, wie wir das bei TSP ja auch haben wollen, Hamilton 17:30.560 --> 17:30.960 -Kreis. 17:31.500 --> 17:37.240 Bei TSP nehmen wir typischerweise an, dass der gegebenen Graph 17:37.240 --> 17:40.680 vollständig ist, also dass es zwischen je zwei Knoten eine Kante gibt. 17:42.200 --> 17:46.440 Für das Hamilton-Kreis-Problem schauen wir einfach irgendeinen Graphen 17:46.440 --> 17:50.560 an, also bestimmte Knotenpaare nicht durch eine Kante verbunden sind. 17:51.100 --> 17:54.180 Und da ist dann nicht so offensichtlich, ob überhaupt so eine Tour 17:54.180 --> 17:58.460 existiert, die jeden Knoten genau einmal besucht. 18:00.080 --> 18:02.440 Dementsprechend wäre das Hamilton-Kreis-Suchproblem. 18:02.900 --> 18:05.760 Wir haben gegeben einen ungerichteten, ungewichteten Graphen, einen 18:05.760 --> 18:10.420 ganz normalen Graphen g. Und die Frage ist, gibt es überhaupt einen 18:10.420 --> 18:12.840 Hamilton -Kreis in g? 18:12.980 --> 18:15.060 Und wenn ja, gib einen solchen an. 18:15.060 --> 18:18.200 Also gibt es einen Hamilton-Kreis, das wäre wieder das 18:18.200 --> 18:20.880 Entscheidungsproblem, aber beim Suchproblem wollen wir den auch 18:20.880 --> 18:21.620 angeben. 18:23.040 --> 18:26.760 Da wäre also die Menge der Lösungen die Menge aller Hamilton-Kreise im 18:26.760 --> 18:27.080 Graph. 18:29.300 --> 18:31.240 Das ist so eine Sorte von Problem. 18:31.340 --> 18:34.440 Also wenn man nach einer konkreten Lösung einer bestimmten Art sucht, 18:34.500 --> 18:36.020 dann nennt man das ein Suchproblem. 18:37.920 --> 18:40.700 Man könnte auch solche Aufzählungsprobleme betrachten. 18:41.420 --> 18:44.860 Ein Aufzählungsproblem ist wieder gegeben durch die Menge aller 18:44.860 --> 18:49.680 Probleminstanzen zu dem Problem und der Menge aller Lösungen. 18:50.280 --> 18:55.760 Und hier sucht man nach der Kardinalität der Menge aller Lösungen. 18:56.020 --> 19:00.360 Also man will wissen beim Hamilton-Kreis-Problem, wie viele Hamilton 19:00.360 --> 19:01.460 -Kreise gibt es. 19:02.420 --> 19:10.380 Beim TSP-Problem, wie viele Touren gibt es, deren Länge kleiner gleich 19:10.380 --> 19:13.320 am vorgegebenen Wert k ist etwa. 19:15.500 --> 19:19.420 Also Hamilton-Kreis-Aufzählungsproblem ergeben ein ungerichteter, 19:19.500 --> 19:22.580 ungewichteter Graph g. Wie viele Hamilton-Kreise gibt es in g? 19:26.060 --> 19:31.340 Diese Problemstellungen, die passen von ihrer Formulierung her nicht 19:31.340 --> 19:35.620 in das Konzept, das wir bisher betrachtet haben bei der Definition der 19:35.620 --> 19:40.180 Klasse NP, wo wir die Formulierung eines Entscheidungsproblems 19:40.180 --> 19:40.440 brauchen. 19:41.100 --> 19:43.980 Aber natürlich möchte man solche Problemstellungen, die sind ja eng 19:43.980 --> 19:47.660 verwandt mit den Entscheidungsproblemen, gibt es einen Hamilton-Kreis 19:47.660 --> 19:52.780 mit dem Entscheidungsproblem, gibt es eine Tour der Länge größer 19:52.780 --> 19:53.300 gleich k. 19:54.100 --> 19:58.160 Solche Problemstellungen, die möchte man doch in Relation setzen zu 19:58.160 --> 20:02.720 Problemstellungen, die als Entscheidungsproblem formuliert sind. 20:03.240 --> 20:04.980 Und dazu gibt es auch ein Konzept. 20:06.420 --> 20:09.200 In Relation setzen bezüglich ihrer Schwierigkeit. 20:09.940 --> 20:13.560 Das Konzept, das wir kennen, dafür ist immer reduzieren. 20:13.560 --> 20:17.440 Es lässt sich das eine Problem auf das andere reduzieren. 20:17.980 --> 20:20.720 Wenn dem so ist, dann ist es mindestens so schwer. 20:21.700 --> 20:27.000 Bei Berechenbarkeit haben wir eben auch dieses Prinzip der Reduktion 20:27.000 --> 20:27.620 verwendet. 20:27.960 --> 20:30.520 Und dieses Prinzip kann man auch auf solche Problemstellungen 20:30.520 --> 20:32.660 anwenden. 20:33.480 --> 20:40.760 Dazu schauen wir uns erstmal zu Suchproblemen eine mathematische 20:40.760 --> 20:43.760 Beschreibung dessen an, was bei einem Suchproblem eigentlich gefordert 20:43.760 --> 20:44.020 ist. 20:47.320 --> 20:50.980 Zu einem Suchproblem können wir eine Relation betrachten. 20:51.080 --> 20:54.500 Wenn das Suchproblem Pi heißt, dann können wir dazu eine Relation RP 20:54.500 --> 21:00.100 betrachten, die gerade in Relation setzt eine Probleminstanz und ein 21:00.100 --> 21:01.940 Element aus der Lösungsmenge. 21:04.240 --> 21:09.420 Also das ist einfach eine Relation, die zu einer Probleminstanz eine 21:09.420 --> 21:10.920 Lösung zuordnet. 21:12.840 --> 21:16.760 Und dann kann man sagen, eine Funktion realisiert eine solche 21:16.760 --> 21:25.940 Relation, wenn für alle x-Modierungen von Instanzen des Suchproblems 21:25.940 --> 21:33.860 gilt, f bildet x entweder auf y ab, wenn es überhaupt keine Lösung zu 21:33.860 --> 21:41.020 x gibt, also kein y gibt Codierung einer Lösung, sodass xy in der 21:41.020 --> 21:47.260 Relation zu dem Problem ist, beziehungsweise f bildet x auf y an, ab 21:47.260 --> 21:51.140 für ein beliebiges y, das in Relation zu x ist. 21:54.080 --> 22:02.580 In dem Sinne kann man auch Turing-Berechnungen auf Lösungen von 22:02.580 --> 22:08.140 Suchproblemen anwenden. 22:08.920 --> 22:14.080 Eine Turing-Berechnung kann auch ein Output haben und das ist eben 22:14.080 --> 22:20.620 jetzt das, was man als Turing-Berechnung für ein Suchproblem anschaut, 22:20.840 --> 22:26.880 dass diese entsprechende Relation zum Suchproblem realisiert wird, 22:27.060 --> 22:32.180 also eine Funktion berechnet wird, die diese Relation realisiert. 22:32.500 --> 22:36.040 Das heißt also, ein Algorithmus löst das durch RP beschriebene 22:36.040 --> 22:41.600 Suchproblem P, wenn er eine Funktion berechnet, die RP realisiert. 22:42.600 --> 22:48.100 Nachdem wir ein Einverständnis haben bezüglich Lösungen von 22:48.100 --> 22:53.540 Suchproblemen, können wir auch eine Relation herstellen zwischen 22:53.540 --> 22:59.100 solchen Suchproblemen in Bezug auf ihre Komplexität und der 22:59.100 --> 23:01.940 Komplexität von Problemen, die wir als Entscheidungsprobleme 23:01.940 --> 23:02.700 formuliert haben. 23:03.400 --> 23:06.960 Und dazu benutzt wird eine Orakel-Turing-Maschine und jetzt kommt eine 23:06.960 --> 23:07.800 Warnung. 23:07.800 --> 23:12.180 Diese Orakel-Turing-Maschine ist etwas anderes als eine nicht 23:12.180 --> 23:17.860 deterministische Turing-Maschine, wie wir sie aus anschaulichen 23:17.860 --> 23:22.260 Gründen betrachtet haben, die also so ein Orakel realisieren kann, 23:22.360 --> 23:24.480 nicht deterministisch. 23:24.660 --> 23:30.520 Diese Orakel-Turing-Maschine, die wir hier jetzt brauchen, ist eine 23:30.520 --> 23:31.700 deterministische Turing-Maschine. 23:32.300 --> 23:36.960 Das ist eben eine deterministische Turing-Maschine, die ein Orakel 23:36.960 --> 23:44.040 hat, G, was einfach ein Wort aus dem Eingabealphabet abbildet auf ein 23:44.040 --> 23:48.520 Wort aus dem Eingabealphabet, aber eben deterministisch. 23:49.200 --> 23:53.260 Und die Maschine sieht so aus, die hat eben zusätzlich zu dem, was 23:53.260 --> 23:57.340 eine Turing-Maschine typischerweise hat, also Eingabeband, Arbeitsband 23:57.340 --> 24:02.880 und Lese-Schreibkopf, ein ausgezeichnetes Orakelband und zwei 24:02.880 --> 24:06.680 zusätzliche Zustände Qf und Qa. 24:07.080 --> 24:12.040 Qf steht für Fragezustand, Qa steht für Antwortzustand. 24:15.400 --> 24:20.560 Und die Arbeitsweise dieser Turing-Maschine ist für alle Zustände Q, 24:20.640 --> 24:24.520 die ungleich dem Fragezustand sind, wie bei einer normalen Turing 24:24.520 --> 24:24.920 -Maschine. 24:25.500 --> 24:28.540 Also muss man jetzt nur angucken, also normalen deterministischen 24:28.540 --> 24:31.800 Turing -Maschinen, muss man also nur angucken, was macht diese Orakel 24:31.800 --> 24:36.120 -Turing -Maschine, wenn sie mal in den Zustand Qf, in den Fragezustand 24:36.120 --> 24:36.420 kommt. 24:39.060 --> 24:45.980 Also nur dann, wenn sie in den Fragezustand kommt und der Kopf, nur 24:45.980 --> 24:48.920 dann, wenn sie in den Fragezustand kommt, schauen wir nach, wo der 24:48.920 --> 24:53.600 Kopf auf dem Orakelband steht. 24:54.460 --> 25:01.280 Wenn der Kopf auf der Position I des Orakelbands steht und der Inhalt 25:01.280 --> 25:09.140 des Orakelbandes auf den Positionen 1 bis I das Wort Y ist, dann 25:09.140 --> 25:13.140 verhält sich die Orakel-Turing-Maschine folgendermaßen, sie guckt sich 25:13.140 --> 25:14.480 dieses Wort Y an. 25:15.180 --> 25:21.460 Wenn das Y kein Wort über dem Eingabealphabet ist, dann sagt sie, da 25:21.460 --> 25:22.480 kann man nichts mit anfangen. 25:22.860 --> 25:26.300 Das stoppt, eine Fehlermeldung, sage ich mal. 25:35.180 --> 25:42.080 Ansonsten wird dieses Y überschrieben letztendlich oder gelöscht und 25:42.080 --> 25:47.920 ein G von Y auf die Positionen 1 bis G von Y des Orakelbandes 25:47.920 --> 25:48.500 geschrieben. 25:48.500 --> 25:55.540 Und das Ganze kostet uns nur, sage ich mal, einen Schritt fürs Löschen 25:55.540 --> 26:01.340 und dieses Schreiben von 1 bis G von Y auf das Orakelband. 26:01.660 --> 26:09.700 Danach ist sozusagen dieser Teil, wo das Orakelband überhaupt benutzt 26:09.700 --> 26:13.740 wird, beendet und der Folgezustand ist der Antwortzustand. 26:17.650 --> 26:22.250 Wie kann man diese Berechnung interpretieren? 26:22.390 --> 26:26.570 Die kann man so interpretieren, dass in einer deterministischen Turing 26:26.570 --> 26:31.530 -Maschinen -Berechnung es die Möglichkeit gibt, mehr oder weniger 26:31.530 --> 26:39.190 einem Schritt eine Eingabe anzugucken und dazu dann eine Lösung zu 26:39.190 --> 26:44.850 schreiben, dieses Orakel-G von Y zu schreiben. 26:48.430 --> 26:49.790 Wohlgemerkt, das ist alles deterministisch. 26:50.630 --> 26:55.030 Jedes Mal, wenn man für eine bestimmte Eingabe diese Orakel-Turing 26:55.030 --> 26:58.170 -Maschine laufen lässt, macht die dasselbe. 26:59.190 --> 27:03.070 Das ist bei der nicht-deterministischen Turing-Maschine anders. 27:05.210 --> 27:07.450 Das heißt, die Orakel-Turing-Maschine und die nicht-deterministische 27:07.450 --> 27:09.630 Turing -Maschine, das sind zwei verschiedene Konzepte. 27:11.410 --> 27:15.650 Diese Orakel-Turing-Maschine braucht man jetzt aber um Reduktion von 27:15.650 --> 27:20.720 Problemen, die nicht Entscheidungsprobleme, auf andere Probleme zu 27:20.720 --> 27:22.120 definieren. 27:22.340 --> 27:24.700 Es gibt den Begriff der Turing-Reduktion. 27:26.780 --> 27:30.840 Dazu betrachtet man wieder zwei Relationen, die zu Suchproblemen 27:30.840 --> 27:32.500 gehören, wie wir sie eben betrachtet haben. 27:32.980 --> 27:39.000 Eine Turing-Reduktion der einen Relation R auf die andere R', das 27:39.000 --> 27:41.680 entsprechende Zeichen, das wir da schreiben, sieht genauso aus wie bei 27:41.680 --> 27:47.980 der normalen Turing-Reduktion, also eine Orakel-Turing-Maschine M, 27:49.140 --> 27:54.560 deren Orakel gerade diese Relation R' realisiert und die selbst in 27:54.560 --> 27:58.720 polynomialer Zeit die Funktion berechnet, die R realisiert. 28:00.140 --> 28:06.140 Wenn man mit diesem Reduktionsbegriff ein Problem auf das andere 28:06.140 --> 28:11.280 reduzieren kann, dann kann man daraus auch folgern, dass man mit einem 28:11.280 --> 28:14.860 polynomialen Algorithmus für das eine auch das andere polynomial lösen 28:14.860 --> 28:15.220 kann. 28:15.760 --> 28:23.880 Genau wie bei polynomialer Reduktion zwischen Entscheidungsproblemen. 28:24.260 --> 28:34.400 Also, falls R', wenn wir haben R', R' ist polynomial reduzierbar auf R 28:34.400 --> 28:39.240 oder umgekehrt, wir haben so eine Transformation von R nach R', 28:39.240 --> 28:44.700 mithilfe so einer Orakel-Turing-Maschine, die in polynomialer Zeit R 28:44.700 --> 28:45.460 realisiert. 28:46.380 --> 28:53.160 Dann gilt, falls das R' in polynomialer Zeit realisierbar ist und R' 28:53.700 --> 28:59.740 reduzierbar auf R, so ist auch R in polynomialer Zeit realisierbar. 28:59.900 --> 29:06.560 Das ist ganz genau dieselbe Überlegung wie bei entweder vollständigen 29:06.560 --> 29:10.540 Problemen oder bezüglich einer polynomialen Transformation ineinander 29:10.540 --> 29:12.260 überführbare Probleme. 29:13.660 --> 29:17.600 Man hat auch diese Transitivität der Turing-Reduzierbarkeit. 29:18.900 --> 29:21.500 Wir werden mit diesen Begriffen nicht weiter arbeiten. 29:21.640 --> 29:25.060 Ich will Ihnen nur klar machen, dass die Probleme, die Art von 29:25.060 --> 29:28.260 Problemen, die einen typischerweise eigentlich interessieren, so etwas 29:28.260 --> 29:31.160 wie ein Suchproblem, so etwas wie ein Aufzählungsproblem, so etwas wie 29:31.160 --> 29:37.020 ein Optimierungsproblem, auch sich in Kontext bringen lassen bezüglich 29:37.020 --> 29:40.880 ihrer Komplexität zu den Problemen, die wir genau betrachtet haben, 29:40.980 --> 29:41.840 die Entscheidungsprobleme. 29:43.980 --> 29:48.880 Man sagt dann bei so einem Suchproblem, dass es NP-schwer ist, falls 29:48.880 --> 29:54.920 sich irgendein NP-vollständiges Problem, sozusagen Turing 29:54.920 --> 29:58.440 transformieren lässt auf dieses, oder falls sich dieses Suchproblem 29:58.440 --> 30:02.840 Turing reduzieren lässt auf ein NP-vollständiges Problem. 30:04.740 --> 30:06.980 Das heißt also, wenn man bei einem Suchproblem jetzt wissen will, und 30:06.980 --> 30:13.840 wie schwer ist das dann denn, passt nicht in unsere Betrachtung von 30:13.840 --> 30:18.420 Entscheidungsproblemen direkt rein, dann würde mal irgendein NP 30:18.420 --> 30:21.160 -vollständiges, und man hat das Gefühl, aber das ist ja mindestens so 30:21.160 --> 30:24.480 schwer wie all diese NP-vollständigen Entscheidungsprobleme, die wir 30:24.480 --> 30:25.840 da schon kennengelernt haben. 30:26.480 --> 30:29.080 Dann würde man sich ein NP-vollständiges Entscheidungsproblem 30:29.080 --> 30:34.560 raussuchen, ein passendes, und dann zeigen, dieses Suchproblem ist 30:34.560 --> 30:37.800 Turing reduzierbar auf dieses NP-vollständige. 30:38.320 --> 30:42.320 Und die Art, wie so ein Beweis geführt wird, ist durchaus ähnlich wie 30:42.320 --> 30:46.740 normale NP-Vollständigkeitsreduktionsbeweise. 30:47.280 --> 30:51.180 Und in so einem Fall nennt man das Problem P-NP-schwer, also nicht NP 30:51.180 --> 30:53.200 -vollständig, sondern NP-schwer. 30:53.200 --> 30:58.040 Der Begriff, Sie werden immer schon mal NP-schwer, NP-hard im 30:58.040 --> 31:03.420 Englischen lesen, und dann eben das NP-vollständig, NP-complete im 31:03.420 --> 31:03.920 Englischen. 31:04.900 --> 31:08.860 Von NP-schwer spricht man dann, wenn man ein Problem hat, was 31:08.860 --> 31:11.640 mindestens so schwer ist, wie all die NP-vollständigen, sich sozusagen 31:11.640 --> 31:16.980 auf die reduzieren lässt, aber selber vielleicht gar nicht in NP 31:16.980 --> 31:17.660 liegt. 31:18.480 --> 31:19.520 Das ist der Punkt. 31:19.520 --> 31:23.140 Für ein Suchproblem kann man nicht so unweiter sagen, das liegt in NP, 31:23.260 --> 31:26.520 weil es schon von der Art der Formulierung da nicht reinpasst. 31:28.600 --> 31:33.580 Also ein Problem, das NP-schwer ist, das muss nicht notwendig in NP 31:33.580 --> 31:33.960 liegen. 31:34.240 --> 31:38.440 NP -schwer sagt man dann oft einfach für diese Probleme, die 31:38.440 --> 31:40.500 mindestens so schwer sind wie NP-vollständige. 31:40.560 --> 31:43.660 Manchmal sagen das Leute auch, so NP-vollständige Probleme, das heißt 31:43.660 --> 31:46.960 dann immer, naja gut, also das gehört zu diesen schweren. 31:49.360 --> 31:54.600 Enthalten sein in NP oder nicht, das ist das, was möglicherweise nicht 31:54.600 --> 31:55.220 klar ist. 31:57.640 --> 32:02.700 Also wenn wir die beiden Varianten oder die erste Variante des TSP 32:02.700 --> 32:06.540 -Suchproblems anschauen, wo es darum geht, eine optimale Tour 32:06.540 --> 32:12.620 anzugeben, dann ist das ein NP-schweres Problem. 32:15.020 --> 32:16.960 Beweis will ich hier nicht führen. 32:18.320 --> 32:22.800 Wenn Sie das interessiert, können Sie sich den ansehen. 32:31.620 --> 32:36.260 Also nochmal, wir nennen ein Problem NP-schwer, wenn es mindestens so 32:36.260 --> 32:38.540 schwer ist wie alle NP-vollständigen Probleme. 32:40.560 --> 32:47.840 Also darunter fallen natürlich die Optimierungsprobleme für NP 32:47.840 --> 32:49.960 -vollständige Entscheidungsprobleme. 32:53.620 --> 33:00.780 Aber es ist noch ein bisschen mehr hier zu bemerken und das lohnt 33:00.780 --> 33:03.660 vielleicht auch, um jetzt nochmal mit ein bisschen mehr Konzentration 33:03.660 --> 33:04.380 anzugucken. 33:04.380 --> 33:10.120 Es gibt auch Entscheidungsprobleme, für die gilt, alle anderen 33:10.120 --> 33:14.180 Entscheidungsprobleme aus NP lassen sich polynomial auf dieses 33:14.180 --> 33:15.140 transformieren. 33:15.760 --> 33:20.740 Also es sieht aus wie NP-vollständig, aber man weiß nicht, ob es in NP 33:20.740 --> 33:21.160 ist. 33:23.140 --> 33:24.280 Sowas gibt es auch. 33:24.900 --> 33:27.540 Und bei so einem würde man dann auch sagen, na gut, das ist NP-schwer. 33:27.540 --> 33:32.820 Also Zugehörigkeit zu NP vielleicht nicht klar, aber es ist mindestens 33:32.820 --> 33:35.300 so schwer wie alle anderen NP-vollständigen Probleme. 33:37.400 --> 33:41.680 Jetzt mögen Sie fragen, was kann das für ein Problem sein, wo es nicht 33:41.680 --> 33:44.080 so offensichtlich ist, dass es in NP ist. 33:46.320 --> 33:50.820 Bisher hatten wir immer diesen Teil des Beweises, dass ein Problem NP 33:50.820 --> 33:53.080 -vollständig ist, sehr schnell abgehakt. 33:54.560 --> 34:01.040 Überprüfung, ob ein Lösungsvorschlag belegt dafür ist, dass die 34:01.040 --> 34:06.720 Eingabeinstanz Ja-Instanz ist, das ging immer wie selbstverständlich 34:06.720 --> 34:10.240 polynomial und damit hatten wir sozusagen Zugehörigkeit zu NP. 34:10.740 --> 34:13.400 Hier ist zum Beispiel ein Problem, bei dem die Zurückgehörigkeit von 34:13.400 --> 34:16.100 NP nicht ganz so leicht zu beweisen ist. 34:16.680 --> 34:20.140 Das Problem ist in NP, aber da muss man deutlich mehr Aufwand 34:20.140 --> 34:22.020 betreiben, als wir das bisher so kennen. 34:23.080 --> 34:26.180 Und dieses Problem ist außerdem ein sehr wichtiges 34:26.180 --> 34:27.200 Optimierungsproblem. 34:31.100 --> 34:35.060 Also ich formuliere es jetzt gleich wieder als Entscheidungsproblem. 34:35.480 --> 34:41.860 Das Problem ist eine Variante des Problems lineare Programmierung, 34:41.940 --> 34:46.340 Integer Programming, ganzzahlige Programmierung. 34:46.340 --> 34:53.380 Wir haben gegeben, Werte aij ganzzahlig für i zwischen 1 und m und j 34:53.380 --> 34:54.320 zwischen 1 und n. 34:54.460 --> 34:59.380 Also eigentlich ist das hier eine m kreuz n Matrix A. 35:01.800 --> 35:05.880 Und dann haben sie noch bi gegeben für i gleich 1 bis m, auch 35:05.880 --> 35:09.500 ganzzahlige Werte, und cj für j gleich 1 bis n. 35:09.500 --> 35:14.180 Das heißt also, sie haben so einen m Vektor b mit ganzzahligen 35:14.180 --> 35:18.500 Einträgen und einen n Vektor c mit ganzzahligen Einträgen. 35:19.480 --> 35:24.080 Und als letztes haben sie noch einen Wert b Groß b aus z gegeben. 35:24.820 --> 35:33.600 Und die Frage ist jetzt, gibt es x1 bis xn aus n Null, sodass die 35:33.600 --> 35:42.940 Summe i gleich 1 bis n der cj mal xj dieses b ergibt, einerseits und 35:42.940 --> 35:49.260 andererseits die Summe j gleich 1 bis n aij mal xj jeweils kleiner 35:49.260 --> 35:52.460 gleich bi ist für i zwischen 1 und m. 35:53.360 --> 35:59.220 Erstmal dieses erste hier, Summe j gleich 1 bis n cj mal xj gleich b. 35:59.680 --> 36:00.240 Was ist das? 36:00.560 --> 36:06.060 Naja gut, die cj, j zwischen 1 und m, als Vektor aufgefasst, als m 36:06.060 --> 36:06.580 Vektor. 36:07.160 --> 36:10.760 xj, sorry, 36:14.100 --> 36:20.560 cj, j zwischen 1 und n als n Vektor aufgefasst und xj, j zwischen 1 36:20.560 --> 36:22.900 und n als n Vektor aufgefasst. 36:26.540 --> 36:31.380 Wird als Produkt gerade j gleich 1 bis n cj xj ergeben. 36:31.760 --> 36:35.960 Also sie multiplizieren den c Vektor mit dem x Vektor. 36:37.500 --> 36:43.140 Die Frage ist, kommt dabei gerade genau b raus, das vorgegebene Groß 36:43.140 --> 36:43.400 b. 36:44.400 --> 36:51.120 Unter der Nebenbedingung, dass die Matrix, die durch die aij gegeben 36:51.120 --> 36:58.940 ist, Matrix A, multipliziert mit dem x Vektor, einen Vektor ergibt, 36:59.120 --> 37:03.400 der kleiner gleich, komponentenweise kleiner gleich dem b Vektor ist. 37:04.820 --> 37:09.260 Das sieht jetzt sehr abstrakt aus, die Sache ist aber die, dass sich 37:10.630 --> 37:16.750 unheimlich viele Optimierungsprobleme so ausdrücken lassen. 37:17.710 --> 37:21.490 Optimierungsprobleme, in denen nur ganzzahlige Werte vorkommen als 37:21.490 --> 37:31.330 Gewichte oder Kosten, lassen sich oft sehr leicht als so ein 37:31.330 --> 37:33.250 Integerprogramm ausdrücken. 37:34.070 --> 37:39.830 Wenn man jetzt also Lösungsmethoden hat für solche Integerprogramming 37:39.830 --> 37:47.250 Instanzen, dann hat man automatisch dann auch Lösungsverfahren für all 37:47.250 --> 37:50.010 diese verschiedenen Optimierungsprobleme, die sich so ausdrücken 37:50.010 --> 37:50.390 lassen. 37:51.190 --> 37:55.090 Das ist tatsächlich ein Weg, Optimierungsprobleme zu lösen, indem man 37:55.090 --> 38:01.630 sie als ein lineares Programm formuliert und dann Lösungsmethoden zur 38:01.630 --> 38:03.410 Lösung linearer Programme anwendet. 38:04.710 --> 38:07.950 Hier, das ist ein spezielles lineares Programm, weil alles, was hier 38:07.950 --> 38:12.090 vorkommt an Werten, sind ganzzahlige Zahlenwerte und insbesondere sind 38:12.090 --> 38:19.290 auch die Lösungswerte, die Belegungen der Variablen x1 bis xn als 38:19.290 --> 38:23.550 sogar positiv oder nicht negativ ganzzahlig gefordert. 38:26.210 --> 38:30.650 Das Problem ist np-schwer und der Beweis, dass np-schwer ist, dass 38:30.650 --> 38:33.630 sich polynomial reduzieren lässt auf ein anderes np-vollständiges 38:33.630 --> 38:34.970 Problem, der ist ganz leicht. 38:35.450 --> 38:38.390 Den führen wir mal jetzt, nur weil er ganz leicht ist. 38:40.970 --> 38:46.930 Also nochmal, das Problem ist, gibt es x1 bis xn aus N0, sodass Summe 38:46.930 --> 38:53.050 j gleich 1 bis n cj mal xj im Wert b ergibt und Summe j gleich 1 bis n 38:53.050 --> 38:58.190 aij mal xj kleiner gleich bi ist für alle i zwischen 1 und m. 38:58.930 --> 39:04.110 Und wir zeigen, dass sich Subset-Sum polynomial transformieren lässt 39:04.110 --> 39:05.910 auf Integer-Programming. 39:06.210 --> 39:09.850 Subset-Sum war ein Problem, von dem wir schon gezeigt haben, dass es 39:09.850 --> 39:10.930 np -vollständig ist. 39:10.930 --> 39:12.890 Wie sieht das aus? 39:13.830 --> 39:18.210 Subset-Sum sieht so aus, wir haben gegeben eine endliche Menge m und 39:18.210 --> 39:22.430 jedes Element aus m hat ein Gewicht aus N0. 39:23.190 --> 39:29.610 Also jedes Element i aus m hat ein Gewicht w von i aus N0 und außerdem 39:29.610 --> 39:32.190 haben sie so ein k gegeben aus N0. 39:32.190 --> 39:37.170 Und die Frage war, ob es innerhalb von m eine Teilmenge m' gibt, 39:37.390 --> 39:44.510 sodass die Gewichte der Elemente aus m' aufsummiert genau k ergibt. 39:44.790 --> 39:46.210 Das war die Problemstellung. 39:47.910 --> 39:51.710 Und das transformieren wir jetzt auf Integer-Programming, das heißt 39:51.710 --> 39:55.530 für so eine beliebige Instanz von Subset-Sum, bestehend aus einer 39:55.530 --> 39:59.090 Menge m, einer Gewichtsfunktion w, die jedem Element aus m eine 39:59.090 --> 40:03.870 natürliche Zahl zuordnet und einem Parameter k, konstruieren wir in 40:03.870 --> 40:07.510 Polynomialzeiten ein Beispiel von Subset-Sum, sodass das 40:07.510 --> 40:13.510 Ausgangsbeispiel genau dann eine Ja-Instanz ist, wenn das Subset-Sum 40:13.510 --> 40:17.590 -Instanz, das wir konstruieren, eine Ja-Instanz ist. 40:17.590 --> 40:20.490 Und die Transformation ist jetzt ganz einfach. 40:21.030 --> 40:28.210 Wir nehmen die Kardinalität der Menge m von Subset-Sum und definieren 40:28.210 --> 40:37.670 unsere Zahlenwerte n und m aus der Instanz für Integer-Programming 40:37.670 --> 40:39.810 gerade gleich dieser Kardinalität. 40:40.210 --> 40:44.470 m gleich n soll die Kardinalität dieser Menge m von Subset-Sum sein. 40:45.250 --> 40:50.110 Wir nehmen jetzt mal an, diese Elemente heißen 1 bis n, diese Elemente 40:50.110 --> 40:50.530 aus m. 40:52.550 --> 41:00.950 Wir wählen die cj gerade gleich dem Gewicht von j bei der Subset-Sum 41:00.950 --> 41:01.590 -Instanz. 41:02.110 --> 41:08.130 Wir wählen das b, dieses b hier, gleich dem k, dem Parameter k aus der 41:08.130 --> 41:09.830 Subset -Sum-Instanz. 41:09.830 --> 41:14.070 Und die bi, die wählen wir alle 1. 41:15.290 --> 41:18.750 Jetzt müssen wir die aj noch wählen, also wie sieht diese Matrix A 41:18.750 --> 41:21.230 aus, die in Integer-Programming vorkommt. 41:21.490 --> 41:23.630 Na gut, das soll einfach die Einheitsmatrix sein. 41:26.190 --> 41:35.490 Wenn wir jetzt eine Lösung von Subset-Sum anschauen, das heißt eine 41:35.490 --> 41:40.590 Teilmenge von m, für die gilt, die Gewichte der Elemente aus dieser 41:40.590 --> 41:42.930 Teilmenge aufsummiert, ergeben gerade k. 41:44.490 --> 41:48.610 Dann induziert uns das direkt eine Lösung des konstruierten Integer 41:48.610 --> 41:51.830 -Programming -Beispiels und umgekehrt. 41:51.830 --> 41:57.590 Nämlich, wir nehmen einfach folgende Werte für die xj. 41:58.270 --> 42:06.010 Wenn j in m' ist, dann wird der entsprechende xj-Wert 1 gesetzt und 42:06.010 --> 42:06.950 ansonsten 0. 42:09.350 --> 42:14.370 Wenn das so ist, also die xj werden gerade genau dann 1 gesetzt, wenn 42:14.370 --> 42:22.230 das j hier in dem m' ist, dann ergibt gerade Summe j aus m bj mal xj 42:22.230 --> 42:24.370 dieses b, b ist ja gleich k. 42:25.110 --> 42:29.190 Die xj sind gerade 1 für die j in m', ansonsten 0. 42:29.350 --> 42:31.830 Das heißt also, die Summe, die hier steht, ist dieselbe wie hier. 42:32.670 --> 42:38.290 Und die xj erfüllen alle auch die Bedingungen, jeweils einen Wert 42:38.290 --> 42:39.570 kleiner gleich 1 zu haben. 42:39.750 --> 42:47.170 Das heißt, diese Bedingung hier, Einheitsmatrix mal Vektor x ist 42:47.170 --> 42:51.110 kleiner gleich dem gewählten b-Vektor, Sie erinnern sich, bi ist 1, 42:52.750 --> 42:53.530 ist auch erfüllt. 42:55.470 --> 43:00.710 Und umgekehrt, wenn Sie hierfür eine Lösung haben, dann induziert die 43:00.710 --> 43:04.210 automatische Lösung für die Subset-Sum-Instanz. 43:04.290 --> 43:09.670 Sie nehmen einfach die xj, die 1 sind bei dieser Belegung hier und 43:09.670 --> 43:11.830 stecken die entsprechenden j in m'. 43:12.990 --> 43:16.210 Also das ist eigentlich trivial, das Ganze. 43:16.790 --> 43:21.130 Also Integer-Programming ist mindestens so schwer wie Subset-Sum, also 43:21.130 --> 43:21.730 np schwer. 43:23.370 --> 43:26.570 Zugehörigkeit in np ist, wie gesagt, nicht so leicht zu beweisen. 43:27.170 --> 43:29.910 Wenn Sie den Beweis sehen wollen, dann können wir zum Beispiel mal 43:29.910 --> 43:37.550 nachgucken in dem Paper, wo das erste Mal ein einfacher Beweis für 43:37.550 --> 43:42.310 Integer -Programming in np geführt wurde. 43:43.950 --> 43:49.470 Sie werden sich fragen, naja, warum ist das nicht so offensichtlich in 43:49.470 --> 43:50.850 np, dieses Problem? 43:55.790 --> 44:03.350 Um für einen Lösungsvorschlag, also Werte x1 bis xn zu überprüfen, ob 44:03.350 --> 44:07.630 Sie diese Bedingungen hier erfüllen, müssen Sie auch nicht viel 44:07.630 --> 44:07.930 machen. 44:08.230 --> 44:10.490 Sie müssen das hier ausrechnen und das hier ausrechnen. 44:12.190 --> 44:20.930 Problem ist, diese Werte der xj, die könnten theoretisch exponentiell 44:20.930 --> 44:23.630 abhängig von den anderen Zahlen werden, also nicht mehr polynomial 44:23.630 --> 44:24.630 davon abhängig. 44:25.130 --> 44:28.010 Es kann sein, dass Sie für eine ganz kleine Instanz, wo nur kleine 44:28.010 --> 44:36.370 Zahlen für die aij und bi und cj vorkommen, gigantisch große x' 44:36.490 --> 44:39.050 brauchen, um eine Lösung zu bekommen. 44:40.670 --> 44:45.510 Es könnte erstmal sein, dass diese xj nicht polynomial von der 44:45.510 --> 44:51.110 Eingabegröße abhängen und damit, oder deren Länge, Zahlenwerte gehen 44:51.110 --> 44:55.790 ja logarithmisch ein, und damit die Überprüfung, ob konkrete xj das 44:55.790 --> 44:58.730 hier erfüllen, nicht unbedingt polynomial ist. 44:58.910 --> 44:59.670 Das brauchen Sie. 45:01.330 --> 45:05.950 In Wirklichkeit ist es so, dass man zeigen kann, die Werte für so eine 45:05.950 --> 45:12.550 Lösung, die können nicht weit entfernt sein, also die hängen nur 45:12.550 --> 45:12.990 polynomial. 45:14.030 --> 45:18.010 Aber das ist eben im ersten Moment der Punkt, wo Sie aufpassen müssen. 45:18.010 --> 45:21.470 Ich sage Ihnen auch das deshalb, weil Sie bei solchen Beweisen, 45:22.290 --> 45:32.330 Problem ist in p, nicht immer so leicht durchkommen, sage ich mal, mit 45:32.330 --> 45:34.730 der Argumentation, wie das bisher schien. 45:35.170 --> 45:38.430 Bisher hatten wir ja immer so ganz leichte Beweise, dass ein Problem 45:38.430 --> 45:39.330 in p ist. 45:39.690 --> 45:40.550 Das muss nicht unbedingt. 45:42.210 --> 45:44.350 So, was noch? 45:44.470 --> 45:47.170 Ich habe ja gesagt, dieses Integer-Programming-Problem ist ein ganz, 45:47.250 --> 45:48.330 ganz wichtiges Problem. 45:49.790 --> 45:54.410 In dem npSchwere-Beweis, den wir gerade eben geführt haben, da war es 45:54.410 --> 46:02.590 sogar so, dass die Werte der aij, bi und xj, die bei der Konstruktion 46:02.590 --> 46:06.450 der Instanz aus subset-sum, aus einem beliebigen Beispiel für subset 46:06.450 --> 46:10.170 -sum, entstanden sind, dass dann alle sogar 0,1-Werte sind. 46:11.530 --> 46:15.570 Das ist dann nochmal ein Spezialfall von Integer-Programming, wo all 46:15.570 --> 46:18.250 diese Werte ganzzahlig sein müssen. 46:18.930 --> 46:24.290 Und man nennt ein solches Programm dann sogar 0,1-Programming. 46:25.270 --> 46:31.230 Und selbst dieses Problem ist np-vollständig, kann ich jetzt ruhig 46:31.230 --> 46:31.530 sagen. 46:31.530 --> 46:36.170 Denn man weiß, dass Integer-Programming, damit auch Siri, 0,1 46:36.170 --> 46:37.770 -Programming in np ist. 46:38.910 --> 46:44.070 Aber interessant ist, dass wenn Sie diese Ganzzahligkeit weglassen, 46:46.710 --> 46:55.390 Forderung aij, bi, cj oder Vorgabe, die sind ganzzahlig und 46:55.390 --> 46:58.790 insbesondere die xj, die Lösungswerte sollen ganzzahlig sein. 46:58.790 --> 47:02.710 Wenn Sie das weglassen, können Sie natürlich auch diese Art von 47:02.710 --> 47:07.010 Problemstellung betrachten, das ist ganz normale lineare 47:07.010 --> 47:12.370 Programmierung, dann gibt es polynomiale Lösungsangebote. 47:13.890 --> 47:19.930 Dass dem so ist, ist zwar alles andere als offensichtlich gewesen, das 47:19.930 --> 47:26.370 ist erst in den 80er Jahren bewiesen worden, aber wenn Sie ein 47:26.370 --> 47:32.170 Optimierungsproblem als ein lineares Programm formulieren können und 47:32.170 --> 47:39.950 die Forderung an die Belegung der Variablen xi ist, dass es nur 47:39.950 --> 47:45.570 irgendwelche rationalen Zahlen sein müssen, dann ist das Problem 47:45.570 --> 47:47.690 polynomial lösbar. 47:49.430 --> 47:53.030 Man hat aber meistens die Forderung oder sehr oft die Forderung, dass 47:53.030 --> 47:57.550 es ganzzahlige Werte sein müssen und dann sind wir bei einem np 47:57.550 --> 47:59.310 -Fehrenproblem oder np-Vollständigen. 48:03.590 --> 48:08.270 Es hilft aber für weiterführende Dinge enorm, dass wir diese 48:08.270 --> 48:13.170 polynomiale Lösbarkeit von linearen Programmen haben, wo die 48:13.170 --> 48:16.510 Zahlenwerte nicht notwendig ganzzahlig sind. 48:18.990 --> 48:27.970 Denn manchmal kann man mit der Lösung eines Integer-Linear-Programming 48:27.970 --> 48:35.510 -Instants, bei dem man einfach relaxiert und sagt, die xij sollen 48:35.510 --> 48:39.630 ganzzahlig sein, vergesse ich mal einen Moment. 48:40.870 --> 48:42.970 Da kann man mit der Lösung durchaus was anfangen. 48:44.210 --> 48:47.890 Also Sie hätten jetzt so ein Programm, da müssen eigentlich die xi 48:47.890 --> 48:49.070 ganzzahlig sein. 48:49.190 --> 48:52.210 Sie lösen es jetzt einfach, da kommen irgendwelche xi-Werte raus, die 48:52.210 --> 48:53.490 nicht ganzzahlig sind. 48:54.150 --> 48:57.250 Die haben möglicherweise auch im Zusammenhang, im Kontext mit dem 48:57.250 --> 49:00.970 dahinterliegenden Problem, keine so richtige Bedeutung. 49:01.850 --> 49:06.570 Aber Sie könnten ja dann etwa eine gerundete Lösung betrachten, wo Sie 49:06.570 --> 49:11.970 einfach alle diese xi-Werte auf den nächsten ganzzahligen Wert darüber 49:11.970 --> 49:15.310 oder darunter, je nachdem, um was für eine Art von Problemstellung es 49:15.310 --> 49:17.430 sich handelt, runden. 49:18.350 --> 49:21.850 Dann hätten Sie möglicherweise wieder eine brauchbare Lösung für Ihr 49:21.850 --> 49:22.270 Problem. 49:22.930 --> 49:28.930 Und tatsächlich können solche Techniken dazu führen, dass Sie für ein 49:28.930 --> 49:34.370 NP -schweres Problem immerhin in Polynomialzeit Lösungen konstruieren 49:34.370 --> 49:41.470 können, deren Qualität, deren Wert nicht zu weit von der Optimallösung 49:41.470 --> 49:46.090 entfernt ist und das in mathematisch garantierter Weise, also wirklich 49:46.090 --> 49:50.850 eine Garantie angeben können, wie viel schlechter die Lösung, die Sie 49:50.850 --> 49:54.490 bekommen, nur werden kann als die Optimallösung. 49:55.390 --> 50:01.050 Auf solche Algorithmen werden wir gleich eingehen. 50:01.530 --> 50:05.130 Aber jetzt erstmal noch einen Aspekt, den ich auch schon angekündigt 50:05.130 --> 50:05.470 hatte. 50:06.910 --> 50:07.970 Pseudipolynomiale Algorithmen. 50:08.290 --> 50:12.070 Also der Kontext, in dem wir uns jetzt hier bewegen, ist, wir kennen 50:12.070 --> 50:17.070 diese NP-vollständigen Probleme, wir kennen NP-schwere Probleme, also 50:17.070 --> 50:20.290 so eine Problemklasse von Problemen, die wir eigentlich lösen wollen, 50:20.290 --> 50:23.450 wo aber nicht zu erwarten ist, dass wir einen polynomialen 50:23.450 --> 50:26.230 Lösungsalgorithmus finden. 50:27.170 --> 50:31.330 Eine Möglichkeit ist, dass Sie einen Lösungsalgorithmus finden, der 50:31.330 --> 50:34.630 zumindest so aussieht, als sei er polynomial und nur beim zweiten 50:34.630 --> 50:39.030 Hingucken nicht wirklich polynomial in der Eingabegröße ist. 50:39.570 --> 50:42.470 Ich habe Ihnen angekündigt, dass für Knapsack sowas existiert. 50:42.810 --> 50:44.090 Das werden wir uns jetzt angucken. 50:46.750 --> 50:48.510 Also pseudipolynomiale Algorithmen. 50:48.790 --> 50:50.310 Ich kann es jetzt mal so rumdrehen. 50:51.490 --> 50:56.250 Wenn Sie die vorkommenden Zahlen in einer Problemstellung nicht wie 50:56.250 --> 51:00.970 gefordert bei unserem Kostenmodell binär kodieren, sondern unnäher, 51:02.730 --> 51:08.770 dann gehen die in die Eingabelänge, diese Zahlen nicht mehr 51:08.770 --> 51:12.470 logarithmisch ein, wie bisher gefordert, sondern linear. 51:13.490 --> 51:16.070 Die Eingabelänge wird plötzlich größer. 51:17.250 --> 51:20.290 Womit die Forderung, dass ein Algorithmus polynomial in der 51:20.290 --> 51:23.490 Eingabelänge ist, eher schwächer wird. 51:26.630 --> 51:32.530 Es gibt NP-vollständige Probleme, bei denen für solch eine Kodierung 51:32.530 --> 51:37.550 der Eingabe polynomiale Algorithmen existieren. 51:37.550 --> 51:40.930 Und so einen Algorithmus nennt man dann pseudipolynomial. 51:41.450 --> 51:46.310 Also ein Algorithmus, der polynomial ist in der Eingabelänge, wenn man 51:46.310 --> 51:50.970 voraussetzt, die Zahlenwerte, die in der Eingabe vorkommen, werden 51:50.970 --> 51:52.310 unnäher kodiert. 51:53.270 --> 51:54.610 Das ist also andersrum. 51:55.610 --> 52:01.110 Der Algorithmus ist polynomial in der Größe der Instanz und in den 52:01.110 --> 52:02.750 Werten, die in der Instanz vorkommen. 52:02.750 --> 52:05.010 Also dem maximalen Zahlenwert, der vorkommt. 52:06.090 --> 52:10.830 Befordert wäre aber eigentlich polynomial im Logarithmus des maximal 52:10.830 --> 52:11.530 Vorkommens. 52:12.690 --> 52:15.550 Da ist sozusagen die Klippe. 52:18.570 --> 52:23.870 Also sei Pi ein Optimierungsproblem, ein Algorithmus, der das Problem 52:23.870 --> 52:28.310 Pi löst, heißt pseudipolynomial, falls seine Laufzeit durch ein 52:28.310 --> 52:33.890 Polynom der beiden Variablen Eingabegröße und Größe der Größten in der 52:33.890 --> 52:37.430 Eingabe vorkommenden Zahl beschränkt ist. 52:38.710 --> 52:41.570 Bei Knapsack werden wir uns jetzt so einen pseudipolynomialen 52:41.570 --> 52:45.270 Algorithmus überlegen und das ist eigentlich gar nicht schwer. 52:45.770 --> 52:47.190 Also nochmal zum Knapsackproblem. 52:47.930 --> 52:50.750 Das ist ja das Problem, das der Weihnachtsmarkt zu lösen hat. 52:51.750 --> 52:56.290 Er hat zur Auswahl eine endliche Menge von Geschenken. 52:58.170 --> 53:02.050 Die Geschenke haben alle ein bestimmtes Gewicht, die Geschenke haben 53:02.050 --> 53:03.350 alle einen bestimmten Wert. 53:04.670 --> 53:09.830 Der Weihnachtsmann kann nur ein Maximalgewicht Groß W tragen und er 53:09.830 --> 53:14.230 will aber möglichst viel an Wert mitnehmen, zum Austeilen. 53:15.370 --> 53:19.150 Entsprechend hat er sozusagen so einen Mindestwert C vorgegeben. 53:19.150 --> 53:25.590 Und die Frage ist, existiert eine Teilmenge M' von M, sodass die 53:25.590 --> 53:31.850 Gewichte der Elemente in M' aufsummiert höchstens Groß W wiegt, aber 53:31.850 --> 53:37.550 die Werte der Elemente in M' aufsummiert mindestens so groß wie das 53:37.550 --> 53:38.810 vorgegebene C ist. 53:39.870 --> 53:46.470 Er will Elemente einpacken, deren Gesamtgewicht gleich dem 53:46.470 --> 53:50.350 Maximalgewicht ist, was er tragen kann, deren Gesamtwert aber 53:50.350 --> 53:53.830 mindestens einen vorgegebenen Wert C übertrifft. 53:54.990 --> 54:02.250 Und ein solches Problembeispiel, also ein beliebiges Beispiel M W C 54:02.250 --> 54:09.790 Groß W Groß C für Knapsack, kann in der Laufzeit O von Kardinalität 54:09.790 --> 54:12.150 von M mal Groß W entschieden werden. 54:13.270 --> 54:15.870 Wenn das so ist, dann haben wir hier einen pseudopolynomialen 54:15.870 --> 54:16.430 Algorithmus. 54:16.430 --> 54:20.970 Das Groß W geht als Zahlenwert in die Laufzeit ein. 54:21.890 --> 54:26.970 Für einen wirklich polynomialen Algorithmus, nur erlaubt, dass es 54:26.970 --> 54:29.270 logarithmisch eingeht. 54:30.630 --> 54:32.270 Wie sieht der Algorithmus aus? 54:33.410 --> 54:37.310 Unsere Elemente nummerieren wir wieder durch, 1 bis N heißen die. 54:38.510 --> 54:40.710 Und jetzt machen wir folgendes. 54:41.010 --> 54:47.190 Für jedes W, also für jeden ganzzahligen Wert zwischen 0 und dem 54:47.190 --> 54:56.690 Maximalgewicht und für jedes I aus M definieren wir ein C und ein I 54:56.690 --> 54:57.730 oben W. 54:58.480 --> 55:07.310 Das soll sein, dass was man maximal an Wert erzielen kann durch 55:07.310 --> 55:16.650 Elemente aus der Teilmenge 1 bis I, wenn man die Forderung hat, die 55:16.650 --> 55:21.130 zusammen die Elemente dürfen höchstens klein W viel biegen. 55:22.850 --> 55:27.630 Also C und ein I oben klein W ist das Maximum über alle M Strich 55:27.630 --> 55:29.330 Teilmenge von 1 bis I. 55:30.050 --> 55:31.610 Dieses I geht hier ein. 55:33.170 --> 55:38.510 Summe J aus M Strich, C von J unter der Nebenbedingung Summe J aus M 55:38.510 --> 55:41.110 Strich, W von J ist kleiner gleich W. 55:41.110 --> 55:49.010 Also die Nebenbedingung ist, die Elemente, die ich hier aus 1 bis I 55:49.010 --> 55:53.610 rauswähle, dürfen zusammen höchstens klein W wiegen. 55:54.950 --> 56:01.590 Unter allen Möglichkeiten, das zu erzielen, nehme ich diejenige, wo 56:01.590 --> 56:05.270 ich maximalen Wert bekomme mit den Elementen. 56:05.770 --> 56:09.930 Diesen maximalen Wert, den nenne ich C und ein I oben klein W. 56:10.730 --> 56:15.870 So ein C und ein I oben klein W kann ich definieren für jedes I 56:15.870 --> 56:21.870 zwischen 1 und N, also im Prinzip für jeden Abschnitt 1 bis I 56:21.870 --> 56:30.690 Teilmenge von M und für jeden ganzzahligen Wert klein W zwischen 0 und 56:30.690 --> 56:31.350 groß W. 56:34.040 --> 56:44.100 An dieser Formel ist das Schöne, dass ich so ein Cj für J größer I 56:44.100 --> 56:53.300 berechnen kann aus den Cj Strich, J Strich kleiner J. 56:53.300 --> 57:06.200 Insbesondere kann ich Ci plus 1 oben W aus den Ci oben W Strich für W 57:06.200 --> 57:09.620 Strich kleiner gleich W berechnen. 57:09.620 --> 57:14.660 Nämlich C und ein I plus 1 W ist ja was? 57:15.160 --> 57:21.180 Das ist der maximale Wert, den ich erzielen kann mit Elementen aus 1 57:21.180 --> 57:26.520 bis I plus 1 unter der Nebenbedingung, dass deren Gesamtgewicht 57:26.520 --> 57:29.080 kleiner gleich W ist, klein W. 57:30.480 --> 57:35.900 Jetzt weiß ich, welchen maximalen Wert ich erzielen kann mit Elementen 57:35.900 --> 57:41.760 aus 1 bis I unter der Nebenbedingung, dass deren Gesamtgewicht kleiner 57:41.760 --> 57:42.600 gleich W ist. 57:43.480 --> 57:46.440 Ich muss jetzt also nur noch dieses Element I plus 1 ins Rennen 57:46.440 --> 57:46.880 bringen. 57:48.780 --> 57:50.360 Was gibt es da an Möglichkeiten? 57:50.360 --> 57:56.540 Entweder das I plus 1 bringt mir keinen Wertgewinn, dann ist C und ein 57:56.540 --> 58:00.240 I plus 1 W dasselbe wie C und ein I W. 58:02.300 --> 58:04.160 Oder es bringt mir einen Wertgewinn. 58:04.980 --> 58:08.440 Na gut, dann muss ich natürlich dessen Gewicht noch einrechnen in das 58:08.440 --> 58:08.660 W. 58:08.660 --> 58:14.100 Das heißt also, dass C I plus 1 oben W, das ist doch nichts anderes 58:14.100 --> 58:20.060 als das Maximum aus C I oben W, wenn das Element I plus 1 gar nichts 58:20.060 --> 58:26.360 bringt, und Gewicht von dem Element I plus 1 plus, nicht Gewicht, Wert 58:26.360 --> 58:33.460 des Elements I plus 1 plus C unten I oben klein W minus Gewichts von I 58:33.460 --> 58:34.060 plus 1. 58:36.920 --> 58:40.020 Das ist praktisch nur die Alternative, die ich habe. 58:40.160 --> 58:42.840 Entweder das I plus 1 bringt mir nichts oder wenn es mir was bringt, 58:43.220 --> 58:45.180 dann muss ich mal gucken, was bringt es mir an Wert. 58:45.820 --> 58:53.960 Aber dafür darf ich dann natürlich nur noch für den Rest das Gewicht W 58:53.960 --> 58:57.620 minus W von I plus 1 ansetzen. 58:57.620 --> 59:07.180 Aber wenn ich für alle kleineren Zahlenwerte W Strich, so ein C I oben 59:07.180 --> 59:10.760 W Strich, kenne, dann kenne ich ja das hier hinten auch. 59:15.110 --> 59:18.570 Das ist also so ein dynamischer Programmierungsansatz, den ich hier 59:18.570 --> 59:19.430 anwenden kann. 59:22.070 --> 59:27.570 Wenn ich das für alle, also diese Berechnung von I oben W, für alle I 59:27.570 --> 59:31.990 aus M und klein W, kleine gleich W machen kann, dann kann ich das 59:31.990 --> 59:36.930 insbesondere auch für C unten N oben gleich W machen. 59:39.390 --> 59:44.010 Und die Instanz ist also genau dann lösbar oder eine Ja-Instanz, wenn 59:44.010 --> 59:51.170 dieses C unten N oben W größer gleich meinem vorgegebenen Wert C ist. 59:52.710 --> 59:54.930 So sieht der Algorithmus aus. 59:55.130 --> 59:58.270 Ich berechne C unten N oben W wie folgt. 59:58.270 --> 01:00:04.530 Für klein W zwischen 1 bis groß W setze ich erstmal C0 oben klein W 01:00:04.530 --> 01:00:08.430 gleich 0 und dann mache ich folgendes für I gleich 1 bis N. 01:00:08.870 --> 01:00:14.790 Für klein W gleich 1 bis groß W setze ich C unten klein W, I oben 01:00:14.790 --> 01:00:16.290 klein W. 01:00:16.990 --> 01:00:23.030 C unten I oben klein W gleich das Maximum aus C unten I minus 1 oben 01:00:23.030 --> 01:00:30.750 klein W und C von I plus C unten I minus 1 oben klein W minus W von I. 01:00:32.430 --> 01:00:37.430 Aufwand, na gut, hier diese Doppelschleife, die äußere läuft von 1 bis 01:00:37.430 --> 01:00:40.430 N, die innere von 1 bis groß W. 01:00:40.430 --> 01:00:45.190 Damit habe ich hier diese Laufzeit O von Kardinalität M mal groß W. 01:00:47.070 --> 01:00:50.710 Mit dynamischer Programmierung kann man ganz einfach in O von 01:00:50.710 --> 01:00:57.590 Kardinalität M mal groß W Knapsack lösen. 01:00:58.130 --> 01:01:00.790 Das heißt also Knapsack Pseudopolynomial. 01:01:05.290 --> 01:01:09.590 Jetzt könnte man natürlich fragen, geht das jetzt für alle NP 01:01:09.590 --> 01:01:12.630 -vollständigen Probleme, wo irgendwelche Zahlenwerte vorkommen? 01:01:14.190 --> 01:01:16.590 Ist Knapsack eine Ausnahme? 01:01:16.950 --> 01:01:19.410 Na gut, für manche Probleme geht das wie für Knapsack. 01:01:19.510 --> 01:01:23.370 Man hat pseudopolynomiale Algorithmen, obwohl die Probleme NP 01:01:23.370 --> 01:01:24.210 -vollständig sind. 01:01:24.650 --> 01:01:28.170 Aber für andere NP-Vollständige hat man das nicht nachweislich. 01:01:28.170 --> 01:01:32.050 Man kann beweisen, wenn P ungleich NP ist, kann es das nicht geben. 01:01:32.530 --> 01:01:35.070 Dazu gehört zum Beispiel TSP. 01:01:43.150 --> 01:01:45.170 Dafür folgende Betrachtung. 01:01:46.330 --> 01:01:47.510 Wir betrachten das Problem Pi. 01:01:48.730 --> 01:01:54.910 Und für eine Instanz I von Pi bezeichne ich I in zwei Strichen. 01:01:54.910 --> 01:01:59.910 Die Länge der Instanz, also die Größe der Instanz. 01:02:00.810 --> 01:02:05.090 Und Max I, die größte vorkommende Zahl. 01:02:06.090 --> 01:02:11.030 Und für ein Problem Pi und ein Polynom P, sei Pi und ein P das 01:02:11.030 --> 01:02:16.730 Teilproblem von Pi, in dem nur die Eingaben I mit größte vorkommende 01:02:16.730 --> 01:02:22.490 Zahl in der Instanz I ist kleiner gleich P von Länge von I vorkommen. 01:02:22.490 --> 01:02:26.630 Also Länge von I, ganz normale Eingabelänge von I. 01:02:27.330 --> 01:02:31.670 Und wir betrachten jetzt die Instanzen, für die die maximal 01:02:31.670 --> 01:02:37.090 vorkommende Zahl in der Instanz kleiner gleich Polynom in der 01:02:37.090 --> 01:02:39.430 Eingabelänge von I ist. 01:02:40.610 --> 01:02:44.190 Und so ein Entscheidungsproblem heißt stark NP-vollständig, wenn 01:02:44.190 --> 01:02:50.570 dieses Pi und ein P, also wenn es ein Polynom gibt, sodass das Pi und 01:02:50.570 --> 01:02:52.190 ein P NP-vollständig ist. 01:02:53.970 --> 01:03:02.850 Bei TSP kann man das nachweisen und man kann eben beweisen, ist Pi ein 01:03:02.850 --> 01:03:08.870 stark NP-vollständiges Problem und NP und gleich P, dann gibt es 01:03:08.870 --> 01:03:11.290 keinen pseudopolynomialen Algorithmus für Pi. 01:03:12.430 --> 01:03:13.690 Das ist nicht schwer. 01:03:14.950 --> 01:03:21.330 Okay, das war jetzt also schon mal ein Aspekt, Probleme innerhalb von 01:03:21.330 --> 01:03:27.970 NP -vollständig sind oder auch NP-schwere Probleme und kann man bei 01:03:27.970 --> 01:03:32.430 denen noch darin unterscheiden, wie schwer sie sind bezüglich 01:03:32.430 --> 01:03:33.570 bestimmter Aspekte. 01:03:34.030 --> 01:03:38.770 Und das war jetzt der Aspekt pseudopolynomiale Lösbarkeit. 01:03:38.770 --> 01:03:42.010 Ein anderer Aspekt, den ich eben schon angesprochen habe, ist 01:03:42.010 --> 01:03:50.750 Lösbarkeit in polynomial Zeit mit einem Algorithmus, der zwar keine 01:03:50.750 --> 01:03:57.290 Optimallösung liefert, aber eine Lösung, deren Qualität garantiert 01:03:57.290 --> 01:04:04.390 nicht wesentlich schlechter ist als die Qualität der Optimallösung. 01:04:04.390 --> 01:04:13.010 Also kann ich für so ein Problem wie TSP oder Knapsack oder 01:04:13.010 --> 01:04:18.570 Grafenfärben einen polynomialen Algorithmus angeben, der mir eine 01:04:18.570 --> 01:04:24.170 Lösung gibt, die zwar nicht optimal ist, für die ich aber beweisen 01:04:24.170 --> 01:04:31.990 kann, dass sie nicht deutlich von dem Wert der Optimallösung abweicht. 01:04:32.830 --> 01:04:36.850 Also wenn es jetzt etwa um die Anzahl der Farben geht, die ich 01:04:36.850 --> 01:04:41.190 brauche, um einen Graf zu färben, kann ich einen polynomialen 01:04:41.190 --> 01:04:45.910 Algorithmus angeben, der den Grafen färbt, zulässig färbt, wo die 01:04:45.910 --> 01:04:51.130 Anzahl der Farben, die gebraucht wird, nicht deutlich mehr ist, als 01:04:51.130 --> 01:04:55.230 die Anzahl der Farben im Optimalfall ausreichen. 01:04:55.230 --> 01:05:00.130 Entweder nicht mehr als doppelt so viele Farben oder nur zwei Farben 01:05:00.130 --> 01:05:00.450 mehr. 01:05:02.170 --> 01:05:05.230 Solche Algorithmen nennt man Approximationsalgorithmen. 01:05:09.010 --> 01:05:13.970 Und die Frage ist, wie misst man denn jetzt die Qualität der Lösung? 01:05:14.250 --> 01:05:18.870 Bei dem Färben habe ich gesagt, ein Beispiel wäre etwa die Lösung, die 01:05:18.870 --> 01:05:23.190 der Approximationsalgorithmus liefert, ist eine Anzahl von Farben, die 01:05:23.190 --> 01:05:26.190 höchstens doppelt so groß ist wie die Anzahl der Farben, die ich im 01:05:26.190 --> 01:05:27.790 Optimalfall brauche. 01:05:28.030 --> 01:05:34.850 Oder andere Möglichkeiten, eine Anzahl von Farben, als wenn nur drei 01:05:34.850 --> 01:05:37.490 mehr verwendet werden als im Optimalfall. 01:05:39.290 --> 01:05:45.190 Diese zweite Sorte von Garantie nennt man absolute Gütegarantie. 01:05:45.190 --> 01:05:47.090 Damit fangen wir also jetzt mal an. 01:05:47.170 --> 01:05:52.990 Das ist eigentlich so eine der ehrgeizigsten Sachen, dass man fordert, 01:05:53.130 --> 01:06:06.210 die Lösung weicht im Absolutwert nur um ein konstantes Ab vom 01:06:06.210 --> 01:06:07.110 Optimalwert. 01:06:08.310 --> 01:06:12.530 Also ich habe gegeben, ein Optimierungsproblem Pi und so ein absoluter 01:06:12.530 --> 01:06:16.910 Approximationsalgorithmus ist ein polynomialer Algorithmus A, der für 01:06:16.910 --> 01:06:24.550 jede Instanz zu Pi eine Lösung liefert mit Wert A von I, sodass die 01:06:24.550 --> 01:06:33.050 Differenz von Opt I und A von I kleinergleich einer konstanten K ist. 01:06:40.380 --> 01:06:44.980 So einen Algorithmus A, den nennt man Approximationsalgorithmus mit 01:06:44.980 --> 01:06:49.260 Differenzgarantie oder absoluter Approximationsalgorithmus. 01:06:49.840 --> 01:06:54.860 Wir nehmen hier bei dieser Differenz Opt I minus A von I den Betrag. 01:06:56.360 --> 01:07:03.620 Wenn jetzt das Optimierungsproblem Pi ein Maximierungsproblem ist, der 01:07:03.620 --> 01:07:07.460 Wert der Lösung soll möglichst groß sein, dann dürfte das A von I 01:07:07.460 --> 01:07:11.300 kleiner als Opt I sein, das heißt also das Ganze ist eine positive 01:07:11.300 --> 01:07:11.840 Zahl. 01:07:12.540 --> 01:07:17.060 Wenn es umgekehrt ist, das ist ein Minimierungsproblem, dann dürfte 01:07:17.060 --> 01:07:21.620 das A von I größer dem Opt I sein, dann ist das eine negative Zahl und 01:07:21.620 --> 01:07:22.400 das wollen wir nicht. 01:07:24.420 --> 01:07:27.740 Und deshalb schauen wir hier sozusagen den Betrag an. 01:07:29.800 --> 01:07:33.320 Die schlechte Nachricht ist, es gibt nur ganz wenige NP-schwere 01:07:33.320 --> 01:07:37.060 Optimierungsprobleme, für die es überhaupt einen solchen absoluten 01:07:37.060 --> 01:07:39.760 Approximationsalgorithmus gibt. 01:07:40.180 --> 01:07:45.640 Es gibt nur ganz wenige, aber es gibt eine ganze Reihe von Resultaten, 01:07:45.760 --> 01:07:50.480 die sagen, wenn P unter NP ist, dann kann es für folgendes NP-schwere 01:07:50.480 --> 01:07:53.180 Optimierungsproblem keinen solchen Algorithmus geben. 01:07:53.180 --> 01:07:57.480 Es gibt sogar ein allgemeines Resultat, dass für eine bestimmte Sorte 01:07:57.480 --> 01:08:05.520 von Optimierungsproblemen sowas nicht existieren kann unter der 01:08:05.520 --> 01:08:06.980 Voraussetzung P und gleich NP. 01:08:08.660 --> 01:08:11.680 Schauen wir uns das mal bei Knapsack an, was da los ist. 01:08:13.100 --> 01:08:16.400 Wir gucken jetzt eine allgemeinere Form von Knapsack an. 01:08:16.400 --> 01:08:19.340 Einziger Unterschied zu dem Knapsackproblem, wie wir es bisher 01:08:19.340 --> 01:08:26.600 betrachtet haben, ist, von jedem Gegenstand, jedem Element aus M kann 01:08:26.600 --> 01:08:30.540 der Weihnachtsmann beliebig viele mitnehmen. 01:08:31.300 --> 01:08:34.500 Also der ist im Warenhaus und die möglichen Geschenke, die sind 01:08:34.500 --> 01:08:37.360 natürlich jeweils mehrfach da. 01:08:40.880 --> 01:08:47.820 Dann ist also die Aufgabe, gib solche Anzahlen x1 bis xn an, sodass 01:08:47.820 --> 01:08:53.640 die Summe i gleich 0 bis n, xiw i kleiner gleich groß W und die Summe 01:08:53.640 --> 01:09:00.520 i gleich 1 bis n, das hier muss auch eine 1 sein, Summe i gleich 1 bis 01:09:00.520 --> 01:09:05.960 n, xiw i kleiner gleich groß W und Summe i gleich 1 bis n, xic i 01:09:05.960 --> 01:09:06.420 maximal. 01:09:08.180 --> 01:09:16.320 Also hier einziger Unterschied gegenüber der Beschreibung des bisher 01:09:16.320 --> 01:09:22.580 betrachteten Knapsackproblems ist, wir haben hier solche Anzahlen xi, 01:09:26.130 --> 01:09:29.690 die können 0 sein, was heißt, das entsprechende Element wird überhaupt 01:09:29.690 --> 01:09:33.870 nicht eingepackt, aber die können auch größer als 1 sein, also 5 etwa. 01:09:34.390 --> 01:09:37.730 Das heißt, von dem entsprechenden Element werden 5 Exemplare 01:09:37.730 --> 01:09:38.890 eingepackt. 01:09:40.530 --> 01:09:43.250 Also deshalb allgemeines Knapsackproblem, weil sie ein bisschen mehr 01:09:43.250 --> 01:09:44.310 an Möglichkeiten haben. 01:09:45.770 --> 01:09:51.670 Das Problem ist auch NP-schwer, das entsprechende Suchproblem, so wie 01:09:51.670 --> 01:09:52.670 es hier formuliert ist. 01:09:55.190 --> 01:10:01.890 Das ist nicht exakt das Optimierungsproblem zu der Variante des 01:10:01.890 --> 01:10:08.330 Knapsackentscheidungsproblems, das aus der Vorlesung steht, also das, 01:10:08.450 --> 01:10:10.490 was wir gezeigt haben, das ist NP-vollständig. 01:10:12.070 --> 01:10:16.510 Und was man jetzt zeigen kann ist, wenn p ungleich NP, dann gibt es 01:10:16.510 --> 01:10:20.650 keinen absoluten Approximationsalgorithmus A für dieses allgemeine 01:10:20.650 --> 01:10:21.390 Knapsackproblem. 01:10:21.850 --> 01:10:25.670 Also dann gibt es keinen polynomialen Algorithmus A, der zu einer 01:10:25.670 --> 01:10:30.610 Instanz des allgemeinen Knapsackproblems eine Lösung liefert, für die 01:10:30.610 --> 01:10:36.590 wir garantieren können, die Differenz, der Betrag der Differenz 01:10:36.590 --> 01:10:42.610 zwischen der Optimallösung und dieser Lösung ist kleiner gleich einer 01:10:42.610 --> 01:10:46.090 vorgegebenen Konstante K für alle Instanzen. 01:10:54.700 --> 01:10:58.540 Das ist jetzt so ein Resultat der negativen Art. 01:10:59.320 --> 01:11:01.280 Wie zeigt man das? 01:11:02.280 --> 01:11:10.260 Das zeigt man, indem man argumentiert, wenn es so einen Algorithmus 01:11:10.260 --> 01:11:15.440 gäbe, so einen absoluten Approximationsalgorithmus mit polynomialer 01:11:15.440 --> 01:11:21.820 Laufzeit, dann könnte ich Knapsack sogar in Polynomialzeit optimal 01:11:21.820 --> 01:11:22.300 lösen. 01:11:22.840 --> 01:11:27.880 Also ich reduziere praktisch das Lösen von Knapsack mit einem 01:11:27.880 --> 01:11:33.220 Approximationsalgorithmus mit absoluter Gütegarantie auf optimales 01:11:33.220 --> 01:11:34.440 Lösen von Knapsack. 01:11:35.760 --> 01:11:41.500 Und das wäre ein Widerspruch zu der Annahme p ungleich NP, weil ja 01:11:41.500 --> 01:11:44.420 Knapsack NP-vollständig ist. 01:11:47.460 --> 01:11:49.460 Wie geht der Widerspruchsbeweis? 01:11:49.700 --> 01:11:53.700 Wir schauen uns mal so einen absoluten Approximationsalgorithmus an, 01:11:54.220 --> 01:11:58.960 für das allgemeine Knapsacksproblem, der also insbesondere erfüllt, 01:11:59.760 --> 01:12:07.580 Wert dieses Algorithmus im Vergleich zum Optimalwert ist Differenz 01:12:07.580 --> 01:12:09.860 kleiner gleich K für alle Instanzen. 01:12:11.580 --> 01:12:16.220 Jetzt bauen wir daraus oder aus einer beliebigen Instanz für dieses 01:12:16.220 --> 01:12:22.260 Problem eine andere Instanz für Knapsack, die wir mit diesem 01:12:22.260 --> 01:12:24.800 Algorithmus A dann sogar optimal lösen können. 01:12:27.520 --> 01:12:28.700 Dann hätten wir unseren Widerspruch. 01:12:28.700 --> 01:12:35.980 Also sei unsere beliebige Instanz von Knapsack Menge m, Gewichte wie 01:12:35.980 --> 01:12:39.380 i, Werte c, i und Maximalgewicht w. 01:12:40.240 --> 01:12:42.560 Und jetzt betrachten wir folgende Instanz i'. 01:12:42.560 --> 01:12:45.580 Die Menge von Elementen ist dieselbe. 01:12:47.180 --> 01:12:49.240 Die Gewichte der Elemente bleiben gleich. 01:12:50.240 --> 01:12:52.580 Das Maximalgewicht bleibt gleich. 01:12:53.480 --> 01:12:58.100 Nur die Werte der Elemente sind anders. 01:12:58.280 --> 01:13:03.920 Und zwar ist das c i' gleich dem c i mal K plus 1. 01:13:04.460 --> 01:13:11.100 K ist diese Konstante aus der Gütegarantie für unseren 01:13:11.100 --> 01:13:12.760 Approximationsalgorithmus A. 01:13:13.680 --> 01:13:20.380 Diese Instanz i' sieht fast genauso aus wie die Instanz i, nur sind 01:13:20.380 --> 01:13:26.560 die Werte der Elemente nicht c i, sondern c i mal K plus 1. 01:13:28.000 --> 01:13:33.500 Damit ist Wert einer Optimallösung von i', gerade Wert einer 01:13:33.500 --> 01:13:35.700 Optimallösung von i mal K plus 1. 01:13:36.820 --> 01:13:40.480 Die Instanzen sind so eng miteinander verwandt, dass eine 01:13:40.480 --> 01:13:45.440 Optimallösung für die eine Instanz eine automatische Optimallösung für 01:13:45.440 --> 01:13:46.220 die andere gibt. 01:13:46.840 --> 01:13:50.240 Das Einzige ist, dass der Wert sich um den Faktor K plus 1 01:13:50.240 --> 01:13:51.840 unterscheidet. 01:13:54.480 --> 01:14:00.720 Unser Approximationsalgorithmus für i, da diese Garantie Opt i minus a 01:14:00.720 --> 01:14:05.320 i kleiner gleich K liefert, liefert jetzt was für i'? 01:14:06.740 --> 01:14:15.080 Zu i' liefert er eine Lösung x1 bis xn mit Wert i gleich 1 bis n x i c 01:14:15.080 --> 01:14:15.760 i'. 01:14:17.500 --> 01:14:24.540 Und für diesen Wert gilt Opt i' minus a i' ist kleiner gleich K. 01:14:25.240 --> 01:14:28.980 Denn ich kann das a ja auf i' genauso anwenden wie auf i. 01:14:36.780 --> 01:14:41.400 Diese Lösung induziert eine Lösung natürlich auch für unsere 01:14:41.400 --> 01:14:45.700 Ausgangsinstanz i, nämlich dieselben Elemente. 01:14:46.940 --> 01:14:53.980 Und der Wert dieser Lösung ist einfach L von i, Summe i gleich 1 bis 01:14:53.980 --> 01:14:55.360 n, x i c i. 01:14:57.440 --> 01:15:02.100 Das c i und das c i Strich, die unterscheiden sich aber nur um den 01:15:02.100 --> 01:15:04.160 Faktor K plus 1. 01:15:06.260 --> 01:15:11.660 Das heißt also, ich kann diese Garantie hier auch ausdrücken mithilfe 01:15:11.660 --> 01:15:12.700 von dem Li. 01:15:13.120 --> 01:15:18.580 Diese Garantie Opt von i' minus a von i' kleiner gleich K ist ja genau 01:15:18.580 --> 01:15:24.720 dasselbe wie K plus 1 mal Opt i minus K plus 1 mal L von i kleiner 01:15:24.720 --> 01:15:25.420 gleich K. 01:15:26.460 --> 01:15:32.440 Dividiere ich hier durch K plus 1, dann habe ich also Opt i minus L 01:15:32.440 --> 01:15:39.460 von i, der hat der Lösung den a i induziert, ist kleiner gleich K 01:15:39.460 --> 01:15:40.800 durch K plus 1. 01:15:41.920 --> 01:15:43.960 Und das ist echt kleiner 1. 01:15:45.440 --> 01:15:52.920 Und damit, dass hier nur ganzteilige Werte vorkommen können, als 01:15:52.920 --> 01:15:59.440 ganzteilige Werte, die wir ja hier in der Instanz haben, muss also Opt 01:15:59.440 --> 01:16:02.560 i minus L von i Null sein. 01:16:02.860 --> 01:16:06.420 Echt kleiner 1, es muss Null sein, also Opt i gleich L von i. 01:16:08.560 --> 01:16:12.880 Das heißt also, ich habe das a verwenden können, um für eine beliebige 01:16:12.880 --> 01:16:17.540 Instanz i sogar eine optimale Lösung anzugehen. 01:16:17.940 --> 01:16:23.280 Nehme ich einfach die Instanz i, umforme in die Instanz i', a auf i' 01:16:23.580 --> 01:16:29.580 anwende, die Lösung von i', dann nehme als Lösung von i. 01:16:32.670 --> 01:16:35.130 Das ist aber ein Widerspruch zu p ungleich N. 01:16:36.510 --> 01:16:43.230 Das heißt also, für Knapsack kann ich keinen Algorithmus mit absoluter 01:16:43.230 --> 01:16:44.290 Gütegarantie anwenden. 01:16:44.990 --> 01:16:48.730 Und wie gesagt, für viele andere Optimierungsprobleme auch nicht, es 01:16:48.730 --> 01:16:49.790 sei denn p gleich N. 01:16:51.030 --> 01:16:56.210 Da stellt sich die Frage, wenn ich schon so selten einen absoluten 01:16:56.210 --> 01:17:00.950 Approximationsalgorithmus finden kann, ist ja vielleicht meine 01:17:00.950 --> 01:17:04.130 Forderung, absolute Gütegarantie zu stark. 01:17:04.870 --> 01:17:07.090 Sollte ich dann vielleicht was anderes fordern? 01:17:09.590 --> 01:17:10.630 Könnte ich machen. 01:17:10.950 --> 01:17:16.280 Und zwar könnte fordern eine Approximation mit relativer Gütegarantie. 01:17:17.050 --> 01:17:17.810 Was heißt das? 01:17:18.230 --> 01:17:24.110 Das heißt, ich schaue mir den Quotient zwischen optimaler Lösung, also 01:17:24.110 --> 01:17:27.570 Wert einer optimalen Lösung und Wert, den mein 01:17:27.570 --> 01:17:32.470 Approximationsalgorithmus liefert, an und will eine Garantie für 01:17:32.470 --> 01:17:33.590 diesen Quotienten. 01:17:33.590 --> 01:17:38.250 Also genauer sei p ein Optimierungsproblem, ein polynomialer 01:17:38.250 --> 01:17:42.090 Algorithmus A, der für jede Instanz des Optimierungsproblems einen 01:17:42.090 --> 01:17:48.330 Wert a von i liefert, mit Ra von i kleiner gleich k, weil k größer 01:17:48.330 --> 01:17:54.150 gleich 1 eine Konstante ist und dieses Ra, gerade der Quotient aus a 01:17:54.150 --> 01:17:58.250 von i und opt von i, heißt Approximationsalgorithmus mit relativer 01:17:58.250 --> 01:17:59.070 Gütegarantie. 01:17:59.070 --> 01:18:01.650 Schauen wir uns den Quotienten nochmal an. 01:18:02.110 --> 01:18:05.990 Der Quotient, der wird gerade so gebildet, dass ein Wert kleiner, 01:18:06.790 --> 01:18:10.090 größer gleich 1 rauskommt. 01:18:10.230 --> 01:18:15.650 Das heißt, wenn p Minimierungsproblem ist, dann wird a von i durch opt 01:18:15.650 --> 01:18:16.470 von i genommen. 01:18:18.530 --> 01:18:21.590 Wenn das Problem ein Minimierungsproblem ist, dann können Sie 01:18:21.590 --> 01:18:25.210 erwarten, dass opt von i kleiner gleich a von i ist. 01:18:25.870 --> 01:18:28.890 Das heißt also, a von i durch opt von i größer gleich 1. 01:18:29.550 --> 01:18:32.930 Und wenn das p ein Maximierungsproblem ist, dann nehmen Sie halt 01:18:32.930 --> 01:18:36.450 umgekehrt opt von i durch a von i. 01:18:37.290 --> 01:18:41.630 Das heißt also, der Quotient Ra von i ist, je nachdem ob das Problem 01:18:41.630 --> 01:18:45.730 ein Maximierungs- oder Minimierungsproblem ist, so definiert, dass da 01:18:45.730 --> 01:18:48.070 auf jeden Fall was rauskommt, größer gleich 1. 01:18:49.950 --> 01:18:55.850 Man sagt dann auch, dass a heißt y-approximativ, wenn dieses Ra von i 01:18:55.850 --> 01:19:00.850 für alle i Probleminstanzen zu p kleiner gleich 1 plus y ist. 01:19:01.030 --> 01:19:03.810 Man guckt also nach, wie nah ist man denn an 1 dran. 01:19:04.270 --> 01:19:07.110 1 wäre es, wenn a von i gleich opt von i ist. 01:19:08.350 --> 01:19:12.190 Das ist nicht zu erwarten, dass so ein polynomialer Algorithmus für 01:19:12.190 --> 01:19:15.890 ein entwischweres Optimierungsproblem tatsächlich einen Wert liefert 01:19:15.890 --> 01:19:19.930 für jede Instanz, die gleich dem Optimalwert ist. 01:19:20.590 --> 01:19:24.930 Das heißt also, es ist nur, wenn es gut läuft, irgendwie nah dran und 01:19:24.930 --> 01:19:26.570 man schaut, wie nah ist man dran. 01:19:27.030 --> 01:19:30.510 Und dieses y würde einem sagen, wie nah man dran ist. 01:19:31.710 --> 01:19:36.170 Jetzt die Frage, gibt es solche Algorithmen etwa für Knapsack? 01:19:38.830 --> 01:19:39.990 Antwort ist ja. 01:19:43.550 --> 01:19:46.490 Das mache ich jetzt ein bisschen schneller, wir haben noch vier 01:19:46.490 --> 01:19:46.950 Minuten. 01:19:47.070 --> 01:19:49.490 In den vier Minuten kann ich die Idee kurz rüberbringen. 01:19:51.530 --> 01:19:55.230 Ich denke, eine nahliegende Vorgehensweise für den Weihnachtsmann 01:19:55.230 --> 01:20:03.430 wäre, dass er schaut, bei welchen Geschenken kriege ich denn die beste 01:20:03.430 --> 01:20:06.770 Relation zwischen Wert und Gewicht. 01:20:09.170 --> 01:20:13.530 Also im Moment sind als Weihnachtsgeschenke 2014 wohl diese 01:20:13.530 --> 01:20:16.530 Fitnessbänder besonders en vogue. 01:20:17.970 --> 01:20:20.950 Die wiegen nicht viel, ich weiß nicht genau, wie viel die kosten. 01:20:21.910 --> 01:20:25.630 Also er packt erstmal von der Sorte so viel wie möglich ein, zumindest 01:20:25.630 --> 01:20:28.950 wenn er in Saturn oder Mediemarkt ist und nicht gerade beim Juwelier, 01:20:29.190 --> 01:20:33.990 da kriegt er nämlich sicher ein besseres Verhältnis zwischen Wert und 01:20:33.990 --> 01:20:34.670 Gewicht. 01:20:34.670 --> 01:20:38.190 Er packt so viel wie möglich ein und wenn er dann so viel hat, dass 01:20:38.190 --> 01:20:43.610 kein einziges Band gewichtsmäßig mehr dazu passt, dann guckt er, was 01:20:43.610 --> 01:20:48.910 kann ich denn noch an Gegenständen, die eine nicht so günstige 01:20:48.910 --> 01:20:52.710 Relation zwischen Wert und Gewicht haben, dazu packen. 01:20:53.210 --> 01:20:54.710 Das ist so eine Kredivorgehensweise. 01:20:55.110 --> 01:20:57.770 Die Kredivorgehensweise, die würden wir folgendermaßen implementieren, 01:20:57.770 --> 01:21:03.710 man definiert diese Gewichtsdichten, Quotient aus Wert des Gegenstands 01:21:03.710 --> 01:21:09.270 und Gewichts, also Pi ist Ci durch Wi und sortiert dann die Elemente 01:21:09.270 --> 01:21:10.910 entsprechend diesem Quotient. 01:21:11.710 --> 01:21:15.630 Also sortiere nach Gewichtsdichten, zuerst das günstigste, dann das 01:21:15.630 --> 01:21:19.170 zweitgünstigste und so weiter und indiziere entsprechend um. 01:21:19.570 --> 01:21:22.510 Also das erste Element ist jetzt das mit der besten Gewichtsdichte, 01:21:22.910 --> 01:21:24.750 das zweite mit der zweitbesten und so weiter. 01:21:24.750 --> 01:21:26.230 Das geht in n log n. 01:21:27.130 --> 01:21:31.070 Und dann machen wir nichts anderes als folgendes, für i gleich 1 bis n 01:21:31.070 --> 01:21:37.150 setze ich Xi, die Anzahl, wie viele Elemente man von der Sorte i 01:21:37.150 --> 01:21:43.310 mitnimmt, gleich untere Gaussklammer, Groß W durch Wi und dann Groß W 01:21:43.310 --> 01:21:46.970 gleich W minus W durch Wi mal Wi. 01:21:46.970 --> 01:21:52.810 Und wie viel Gewicht habe ich noch frei, wenn ich also diese Xi vielen 01:21:52.810 --> 01:21:59.090 Exemplare von i mitgenommen habe. 01:22:00.770 --> 01:22:03.910 Und das ist klar, er guckt erstmal, wie viel von der ersten Sorte 01:22:03.910 --> 01:22:09.230 kriege ich rein, wenn kein weiteres mehr dazu, die Anzahl kriegt er, 01:22:09.370 --> 01:22:13.390 indem er Groß W durch Wi, die untere Gaussklammer nimmt. 01:22:13.910 --> 01:22:19.690 Wenn keins mehr dazu packt, dann guckt er, wie viel Gewicht habe ich 01:22:19.690 --> 01:22:23.150 noch frei und schaut dann bei dem zweiten Sorteelement, ob er da noch 01:22:23.150 --> 01:22:24.270 was dazu packen kann. 01:22:25.430 --> 01:22:26.890 Das ist sozusagen die Vorgehensweise. 01:22:29.110 --> 01:22:34.690 Und für diese Vorgehensweise kann man beweisen, dass sie eine relative 01:22:34.690 --> 01:22:37.090 Gütegarantie von 2 erfüllt. 01:22:38.130 --> 01:22:48.870 Das heißt, der Wert der Gegenstände, die auf die Art, im Geschenkesatz 01:22:48.870 --> 01:22:55.950 sagt es, Weihnachtsmann landen, ist mindestens halb so viel wie der 01:22:55.950 --> 01:22:58.270 Optimalwert, den er mitnehmen könnte. 01:22:59.410 --> 01:23:00.590 Mindestens halb so viel. 01:23:00.590 --> 01:23:08.710 Umgekehrt, im Optimalfall kann es höchstens doppelt so viel Wert, kann 01:23:08.710 --> 01:23:12.010 höchstens ein doppelt so großer Wert erzielt werden mit solchen 01:23:12.010 --> 01:23:15.670 Gegenständen, wenn man die Gewichtsbedingungen erfüllt. 01:23:19.380 --> 01:23:22.640 Und den Beweis, den führen wir das nächste Mal. 01:23:27.220 --> 01:23:30.280 Der ist nicht schwer, aber den können wir am Donnerstag machen. 01:23:30.920 --> 01:23:33.480 Und vielleicht das noch als Ankündigung. 01:23:33.880 --> 01:23:40.520 Die nächste Frage, die man dann natürlich stellen kann, ist, geht es 01:23:40.520 --> 01:23:41.660 denn vielleicht auch besser? 01:23:45.710 --> 01:23:46.690 Besser inwiefern? 01:23:47.150 --> 01:23:50.310 Kann der Kredi-Algorithmus vielleicht auch Besseres erzielen als das, 01:23:50.410 --> 01:23:51.710 was ich hier beweisen kann? 01:23:51.710 --> 01:23:55.050 Oder gibt es einen anderen Algorithmus, der vielleicht auch Besseres 01:23:55.050 --> 01:23:55.430 erzielt? 01:23:57.130 --> 01:24:00.290 Was man beweisen kann, ist, dass der Kredi-Algorithmus auch nichts 01:24:00.290 --> 01:24:01.290 Besseres erzielt. 01:24:01.790 --> 01:24:05.090 Also wenn ich diese Gütegarantie von zwei bewiesen habe, kann ich 01:24:05.090 --> 01:24:09.250 außerdem eine Instanz angeben, bei der klar ist, ich komme auch 01:24:09.250 --> 01:24:15.730 beliebig nah an diesen schlechtesten Fall heran, dass der Optimalwert 01:24:15.730 --> 01:24:20.170 der Lösung doppelt so groß ist wie der Wert der Lösung, den mein 01:24:20.170 --> 01:24:23.350 Approximation -Algorithmus, also Kredi, erzielt. 01:24:23.850 --> 01:24:26.550 Ansonsten, ob es insgesamt auch besser geht mit der anderen 01:24:26.550 --> 01:24:28.230 Vorgehensweise, das ist dann nochmal eine andere. 01:24:29.070 --> 01:24:30.290 So, das wäre es für heute.