WEBVTT 00:06.980 --> 00:08.620 Schönen guten Tag zusammen. 00:09.720 --> 00:13.300 Ich begrüße Sie zur Vorlesung Theoretische Informatik. 00:14.540 --> 00:18.120 Wo waren wir letztes Mal stehen geblieben? 00:19.700 --> 00:23.540 Ja, wir sind mitten im Kapitel Komplexitätsklassen. 00:24.360 --> 00:28.400 Und wir haben das letzte Mal für mehrere Probleme gezeigt, dass sie 00:28.400 --> 00:29.600 entweder vollständig sind. 00:30.880 --> 00:35.000 Und heute geht es so weiter, dass wir für weitere Probleme zeigen, 00:35.000 --> 00:38.200 dass sie entweder vollständig sind, aber mit den NP 00:38.200 --> 00:41.980 -Vollständigkeitsbeweisen, das hat dann heute so langsam ein Ende. 00:42.880 --> 00:48.720 Wir werden dann danach in dem Kapitel noch zwei Richtungen 00:48.720 --> 00:49.840 weiterverfolgen. 00:51.280 --> 00:57.980 Die eine ist die Frage, gibt es neben den Klassen P und NP, denn 00:57.980 --> 01:05.120 weitere Komplexitätsklassen in diesem Umfeld P, NP, vor allem wenn P 01:05.120 --> 01:10.040 ungleich NP ist, wie liegt dann, wie sieht dann die Welt innerhalb von 01:10.040 --> 01:11.160 NP aus? 01:12.220 --> 01:17.580 Sind da nur die NP-Vollständigen Probleme und die Probleme aus P oder 01:17.580 --> 01:20.480 gibt es da möglicherweise noch andere Probleme? 01:21.960 --> 01:23.280 Dreckstrich, Sprachen. 01:24.320 --> 01:25.980 Das ist sozusagen so diese eine Richtung. 01:27.280 --> 01:31.780 Das beinhaltet auch so ein bisschen nochmal die Frage, wie handhaben 01:31.780 --> 01:38.500 wir denn Probleme, die nicht als Entscheidungsprobleme formuliert 01:38.500 --> 01:38.780 sind? 01:38.940 --> 01:40.200 Wie passen die sich ein? 01:40.540 --> 01:46.140 Wie nennen wir ein Problem, das kein Entscheidungsproblem ist, aber 01:46.140 --> 01:50.740 mindestens so schwer ist wie alle NP-Vollständigen 01:50.740 --> 01:52.620 Entscheidungsprobleme? 01:53.300 --> 01:57.240 Wie bringen wir das sozusagen in Relation zu diesen 01:57.240 --> 01:58.360 Entscheidungsproblemen? 01:58.360 --> 02:03.580 Und die andere Richtung ist die, mal ausgehend davon, dass P ungleich 02:03.580 --> 02:10.080 NP ist, was macht man denn nun mit den NP-Vollständigen Problemen, die 02:10.080 --> 02:15.400 man ja auch irgendwie mit effizienten Algorithmen, was auch immer 02:15.400 --> 02:19.080 jetzt effizient in dem Zusammenhang heißt, lösen will. 02:19.420 --> 02:25.880 Wir werden einen kleinen Exkurs machen in Richtung polynomiale 02:25.880 --> 02:32.840 Algorithmen für NP-Vollständige Probleme oder allgemeine Probleme, die 02:32.840 --> 02:36.880 mindestens so schwer sind wie NP-Vollständige Probleme. 02:37.440 --> 02:42.760 Polynomiale Algorithmen, die vielleicht nicht genau eine optimale 02:42.760 --> 02:48.400 Lösung für so ein Problem liefern, aber Lösungen liefern, die 02:48.400 --> 02:50.860 beweisbar gut sind. 02:50.860 --> 02:54.280 Das ist sozusagen die Richtung approximierender Algorithmen. 02:54.980 --> 03:00.020 Das ist sozusagen der erste Schritt, den man in den 60er, 70er Jahren 03:00.020 --> 03:04.060 gemacht hat, nachdem eben diese Theorie der NP-Vollständigkeit 03:04.060 --> 03:10.100 sozusagen da stand, Satz von Kuck bewiesen war und so weiter, war dann 03:10.100 --> 03:11.420 sozusagen der erste Ansatz. 03:11.540 --> 03:15.220 Und was machen wir denn jetzt mit NP-Vollständigen Problemen, dass man 03:15.220 --> 03:19.500 solche approximierenden Algorithmen entworfen hat beziehungsweise auch 03:19.500 --> 03:25.340 negativ Resultate bezüglich polynomieller Approximierbarkeit bewiesen 03:25.340 --> 03:25.600 hat. 03:26.180 --> 03:32.380 Und damit werden wir dann nächste Woche das Kapitel abschließen, das 03:32.380 --> 03:37.440 Kapitel Komplexitätsklassen und dann aber vor Weihnachten noch mit dem 03:37.440 --> 03:38.800 nächsten Kapitel anfangen. 03:39.360 --> 03:43.700 Das ist ein bisschen unglücklich, weil es wäre eigentlich ein guter 03:43.700 --> 03:46.620 Schnitt, sozusagen dann im nächsten Jahr mit dem nächsten Kapitel 03:46.620 --> 03:47.080 anzufangen. 03:47.080 --> 03:49.900 So war das auch in den vergangenen Jahren, wenn ich die Vorlesung 03:49.900 --> 03:50.400 gehalten habe. 03:50.500 --> 03:54.500 Aber dieses Jahr ist irgendwie das Vorlesungsende so früh, dass ich 03:54.500 --> 03:57.400 mir das nicht erlauben kann, dann bis nächstes Jahr zu warten mit dem 03:57.400 --> 03:58.080 Kapitel. 03:58.440 --> 04:01.700 So sieht es jetzt aus bis Weihnachten und insbesondere für heute. 04:01.900 --> 04:05.860 Also weitere NP-Vollständigkeitsbeweise und dann die Frage, wie sieht 04:05.860 --> 04:08.380 denn die Welt um P und NP aus? 04:08.780 --> 04:10.820 Weitere NP-Vollständigkeitsbeweise. 04:12.700 --> 04:17.820 Sie erinnern sich, das letzte Mal habe ich diesen Chart angemalt. 04:18.860 --> 04:24.880 Also wir haben als allererstes mit dem Satz von Cook den Beweis, dass 04:24.880 --> 04:27.720 Sat NP-Vollständig ist und dann haben wir eben eine polynomiale 04:27.720 --> 04:32.120 Transformation von Sat auf 3Sat gemacht, von 3Sat auf Klick, von 3Sat 04:32.120 --> 04:38.280 auf 3 Färbbarkeit von Graphen, von 3 Färbbarkeit von Graphen auf Exact 04:38.280 --> 04:42.220 Cover und auf die Art sind wir schon in verschiedene Problembereiche 04:42.220 --> 04:47.100 vorgestoßen, nämlich von Erfüllbarkeitsproblemen wie Sat und 3Sat, zu 04:47.100 --> 04:51.740 Graphenproblemen wie Klick und 3 Färben von Graphen, zu 04:51.740 --> 04:55.540 Mengenproblemen wie Exact Cover und heute geht es dann weiter zu 04:55.540 --> 04:57.040 weiteren Problemen. 04:57.160 --> 05:00.880 Wir werden dann weiter beweisen, dass ein Problem Subset Sam 05:07.640 --> 05:13.720 NP -Vollständig ist und von da aus ein Problem namens Partition. 05:21.160 --> 05:24.600 Und von da aus ein Problem namens Knapsack. 05:29.320 --> 05:30.400 Rucksack Problem. 05:35.570 --> 05:40.110 Diese polynomialen Transformationen führen wir durch, die sind nicht 05:40.110 --> 05:43.390 so technisch, nicht so schwierig wie die letzte, die wir letztes Mal 05:43.390 --> 05:43.730 hatten. 05:44.750 --> 05:48.290 Und bei Subset Sam, Partition und Knapsack sind wir nochmal bei einer 05:48.290 --> 05:50.790 anderen Art von Problemen. 05:52.850 --> 05:58.430 Problemen auf Mengen, wo man Mengen geeignet aufteilen muss oder aus 05:58.430 --> 06:01.150 einer Menge eine geeignete Teilmenge finden muss. 06:01.310 --> 06:02.430 Also so sieht das aus. 06:04.670 --> 06:08.310 Und danach werden wir, wie gesagt, ein bisschen thematisieren, wie die 06:08.310 --> 06:11.270 Welt um P&NP noch aussieht. 06:11.430 --> 06:12.990 Gleich auch schon eins vorneweg. 06:14.250 --> 06:18.550 Knapsack ist insofern interessant, als dass das unter den NP 06:18.550 --> 06:23.690 -Vollständigen Problemen irgendwie leichter erscheint als andere. 06:24.270 --> 06:28.450 Und was das heißt, das werden wir auch nochmal genauer in der nächsten 06:28.450 --> 06:29.100 Woche betrachten. 06:36.160 --> 06:37.880 Also zu heute. 06:41.950 --> 06:45.610 Also allererstes das Problem Subset Sam und der Beweis, dass Subset 06:45.610 --> 06:47.330 Sam NP-Vollständig ist. 06:47.810 --> 06:49.770 Subset Sam ist folgendermaßen definiert. 06:49.850 --> 06:53.670 Wir haben eine endliche Grundmenge gegeben und auf dieser Grundmenge 06:53.670 --> 06:57.670 eine Gewichtsfunktion, die jedem Element der Grundmenge ein Gewicht 06:57.670 --> 06:59.130 zuordnet. 06:59.350 --> 07:01.990 Und die Gewichte sind natürliche Zahlen. 07:02.650 --> 07:04.650 Und außerdem haben wir einen Parameter K. 07:04.970 --> 07:06.450 Das ist auch eine natürliche Zahl. 07:07.330 --> 07:11.930 Und die Frage ist jetzt, gibt es eine Teilmenge in unserer Grundmenge, 07:12.110 --> 07:17.710 sodass die Gewichte der Elemente dieser Teilmenge aufsummiert genau K 07:17.710 --> 07:18.210 ergibt. 07:19.090 --> 07:24.790 Also können wir hier Elemente aus M rausnehmen, sodass die Gewichte 07:24.790 --> 07:31.190 dieser Elemente aufsummiert genau diesen Parameter K trifft. 07:32.810 --> 07:36.210 Diese Elemente würden wir dann eben in diese Teilmenge M' stecken. 07:37.050 --> 07:38.570 Dieses Problem ist NP-Vollständig. 07:38.610 --> 07:40.630 Das sieht eigentlich ziemlich harmlos aus, würde ich sagen. 07:41.950 --> 07:43.690 Ist NP-Vollständig. 07:48.570 --> 07:50.110 Ein kleines Beispiel. 07:51.270 --> 07:54.630 Aber erst mal übliche Übungen. 07:54.850 --> 07:58.190 Als erstes zu zeigen, mein Problem ist in NP. 07:58.970 --> 08:02.370 Das kennen Sie mittlerweile in- und auswendig, was dafür zu tun ist. 08:02.470 --> 08:07.090 Dafür ist einfach zu tun, dass zu überprüfen, dass wenn Sie sozusagen 08:07.090 --> 08:11.230 so ein Zertifikat dafür haben, dass eine vorgegebene Instanz des 08:11.230 --> 08:14.970 Problems, eine Ja-Instanz ist, also eine Instanz, wo die richtige 08:14.970 --> 08:15.630 Antwort ist. 08:15.630 --> 08:19.430 Ja, in dem Fall, ja, es gibt eine Menge M', sodass die Gewichte der 08:19.430 --> 08:25.150 Elemente aus M' aufsummiert K ergibt, dass Sie dies mit polynomialem, 08:25.210 --> 08:27.650 nur polynomialem Aufwand verifizieren können. 08:28.250 --> 08:29.770 Und was wäre hier ein Zertifikat? 08:29.990 --> 08:32.830 Das wäre tatsächlich die Vorgegabe so einer Menge M'. 08:32.830 --> 08:36.710 Also ich gebe Ihnen einfach so eine Menge M', Teilmenge M' vor. 08:38.390 --> 08:39.770 Ich habe es jetzt sammelt. 08:39.910 --> 08:47.550 NP heißt, wir können für diese Menge M' mit polynomiellem Aufwand 08:47.550 --> 08:53.290 überprüfen, dass die Elemente, die Gewichte der Elemente, der Menge 08:53.290 --> 08:54.630 aufsummiert gerade K ergibt. 08:54.750 --> 08:55.210 Das ist klar. 08:55.390 --> 08:57.890 Dafür müssen Sie einfach diese Gewichte aufsummieren und nachgucken, 08:58.010 --> 08:58.610 ob das K ist. 08:58.910 --> 09:02.470 Das ist natürlich polynomial in der Größe des ganzen Problems. 09:02.470 --> 09:07.990 Gut, das ist immer, also das ist meistens, bisher war es immer so bei 09:07.990 --> 09:13.390 allen Beispielen, die wir hatten, von Problemen aus NP, leicht zu 09:15.040 --> 09:15.480 beweisen. 09:18.200 --> 09:24.140 Und jetzt eben der zweite Schritt, dass wir eine polynomiale 09:24.140 --> 09:28.100 Transformation von einem NP-vollständigen Problem auf Subset Sum 09:28.100 --> 09:28.900 angeben können. 09:29.000 --> 09:33.420 Und wir nehmen Exact Cover und geben eine polynomiale Transformation 09:33.420 --> 09:36.500 von Exact Cover zu Subset Sum an. 09:36.800 --> 09:41.820 Dafür müssen wir einfach eine Instanz von Exact Cover hernehmen und 09:41.820 --> 09:46.720 die mit polynomialem Aufwand überführen in eine Instanz von Subset 09:46.720 --> 09:52.000 Sum, sodass die Ja-Instanzen von Exact Cover genau auf die Ja 09:52.000 --> 09:54.500 -Instanzen von Subset Sum abgebildet werden. 09:54.660 --> 09:57.700 Also wir nehmen so eine Instanz von Exact Cover, die sieht so aus, sie 09:57.700 --> 09:59.620 besteht aus einer Grundmenge X. 09:59.620 --> 10:03.380 Der Einfachheit halber werden einfach die Elemente dieser Grundmenge 10:03.380 --> 10:09.340 durchnummeriert von 0 bis M-1 und eine Menge S, die besteht aus 10:09.340 --> 10:10.980 Teilmengen von X. 10:12.280 --> 10:18.640 Die Frage ist ja, gibt es jetzt so eine Teilmenge von S, S', sodass in 10:18.640 --> 10:24.300 den Mengen in S', jedes Element aus X genau einmal enthalten ist. 10:25.180 --> 10:31.160 Sodass also ganz X abgedeckt wird durch die Mengen aus S', heißt jedes 10:31.160 --> 10:34.980 Element aus X kommt in mindestens einer Menge aus S' vor. 10:36.060 --> 10:36.960 Und das ist Cover. 10:37.900 --> 10:41.300 Und das Cover soll exakt sein, das heißt, jedes Element aus X kommt 10:41.300 --> 10:44.420 auch nur in höchstens einer Menge aus S'. 10:45.060 --> 10:48.760 Also so eine Instanz nehmen wir her und daraus konstruieren wir jetzt 10:48.760 --> 10:50.760 also eine Subset Sum-Instanz. 10:50.860 --> 10:53.400 Eine Subset Sum-Instanz besteht aus einer Grundmenge, einer 10:53.400 --> 10:56.460 Gewichtspunktion W auf der Grundmenge und einem Parameter K. 10:57.500 --> 11:03.520 Und als Grundmenge nehmen wir dieses S, also das M ist eine Menge von 11:03.520 --> 11:06.860 Mengen, die Grundmenge ist S. 11:07.840 --> 11:15.580 Wir definieren so eine Anzahl X für jedes X, das in irgendeinem Y aus 11:15.580 --> 11:16.420 S vorkommt. 11:17.200 --> 11:21.760 Und Anzahl X soll einfach heißen, in wie vielen Mengen aus S kommt 11:21.760 --> 11:23.620 denn das Element X aus X vor. 11:26.460 --> 11:33.900 Und wir nennen P, definieren P als diese maximale Anzahl plus 1. 11:34.320 --> 11:41.040 Maximale Anzahl der Mengen, in der irgend so ein X aus X vorkommt, 11:41.300 --> 11:41.780 plus 1. 11:42.620 --> 11:47.480 Und jetzt definieren wir auf der Basis die Gewichtspunktion für unser 11:47.480 --> 11:50.460 Subset Sum-Problem. 11:51.060 --> 11:55.540 Und zwar folgendermaßen, also es muss jedem Element aus M ein Gewicht 11:55.540 --> 11:56.520 zugeordnet werden. 11:56.700 --> 12:01.660 Element aus M, das ist so eine Menge aus S, also Teilmenge von X. 12:02.460 --> 12:06.900 Und das Gewicht, das von so einer Menge Y zuordnen soll sein, Summe 12:06.900 --> 12:13.440 über die Elemente X aus Y, P, diese Zahl hoch X. 12:14.240 --> 12:15.380 Also ein Polynom. 12:16.700 --> 12:22.280 Und das K, dieser Parameter hier, das soll einfach die Summe über alle 12:22.280 --> 12:27.540 Elemente aus der Grundmenge von Exact Cover, also alle Elemente aus X, 12:27.640 --> 12:32.420 also X gleich 0 bis M minus 1, P, dieses P hoch X sein. 12:33.080 --> 12:35.680 Das sieht jetzt erstmal so ein bisschen gefährlich aus, was wir hier 12:35.680 --> 12:42.760 machen, weil wir hier so Potenzen bilden, wo diese X als Exponent 12:42.760 --> 12:43.880 vorkommen. 12:44.140 --> 12:47.620 Ich sage gleich eins vorneweg, wir werden nicht mit diesen Werten 12:47.620 --> 12:48.400 rechnen. 12:49.020 --> 12:52.360 Das heißt, die Polynomialität, wenn man das einfach erstmal so 12:52.360 --> 12:55.260 hinschreibt, von dieser Konstruktion, die ist klar. 12:55.440 --> 13:00.900 Solange wir hier nicht mit rechnen, es gibt da keine Gefahr, dass wir 13:00.900 --> 13:04.640 sozusagen exponentiell im Aufwand würden, exponentiell in der Größe 13:04.640 --> 13:05.460 dieser Instanz. 13:06.160 --> 13:08.420 So, jetzt müssen wir erstmal interpretieren, was diese 13:08.420 --> 13:11.000 Gewichtsfunktionen dieses K eigentlich... 13:13.680 --> 13:15.760 Das interpretieren wir folgendermaßen. 13:17.940 --> 13:24.560 Wir wollen sozusagen Mengenzugehörigkeit von solchen kleinen X 13:24.560 --> 13:26.660 darstellen. 13:28.220 --> 13:30.940 Ob so ein kleines X in der Menge Y ist. 13:31.200 --> 13:38.180 Und das stellen wir dar durch so ein Polynom, was man interpretieren 13:38.180 --> 13:43.480 kann als eine Zahl zur Basis P. Im Prinzip die Exponenten hier, sagt 13:43.480 --> 13:47.340 mir einfach, ob P hoch X für ein X vorkommt. 13:47.600 --> 13:52.540 Also für irgendein X aus X, P hoch X in dem W von Y vorkommt. 13:54.700 --> 13:57.900 Sagt mir einfach, ob das entsprechende X in dem Y ist. 13:59.740 --> 14:03.300 Das heißt also, Mengenzugehörigkeit stellen wir da als Zahlen zur 14:03.300 --> 14:06.880 Basis P und das kann man folgendermaßen einfach ganz einfach machen. 14:07.260 --> 14:12.680 Nehmen wir dieses W von Y für so eine Menge Y aus S, einfach als einen 14:12.680 --> 14:17.440 String von Nullen bis Einsen, der Länge M hinschreibt. 14:18.080 --> 14:25.040 M ist Kardinalität unserer Menge X, Groß X, wo diese kleinen X 14:25.040 --> 14:25.740 herkommen. 14:26.760 --> 14:31.100 Und da steht eben an der i-ten Stelle einfach nur eine 0 oder eine 1. 14:32.360 --> 14:40.980 Da steht eine 0, wenn das P hoch X für das konkrete X, das zu der 14:40.980 --> 14:46.280 Stelle gehört, hier in dem Polynom zu W von Y nicht vorkommt und da 14:46.280 --> 14:49.080 steht eine 1, wenn das P von X hier in dieser Summe vorkommt. 14:50.260 --> 14:54.760 Also andererseits, wir kodieren das W von Y einfach als so ein Vektor, 14:54.880 --> 15:00.040 der Länge M und an der i-ten Stelle steht genau dann Vektor, nochmal 15:00.040 --> 15:04.060 ein Vektor der Länge M, in dem nur Nullen oder Einsen stehen und an 15:04.060 --> 15:11.800 der i-ten Stelle steht genau dann eine 1, wenn das Element I aus X, 15:11.980 --> 15:15.020 aus 0 bis M minus 1, in Y vorkommt. 15:17.440 --> 15:25.040 So, und das K, das entspricht dann also einfach nur so einem Vektor 15:25.040 --> 15:27.460 der Länge M, wo an jeder Stelle 1 steht. 15:27.780 --> 15:33.300 Also für jedes X aus Groß X, also für X gleich 0 bis M minus 1, kommt 15:33.300 --> 15:36.820 ja P hoch X in dieser Summe zu K vor. 15:37.600 --> 15:42.920 Das heißt also, für jedes P von X hat man ein Koeffizient 1, oder das 15:42.920 --> 15:49.020 heißt also, K entspricht so einem String der Länge M, wo überall 15:49.020 --> 15:49.680 Einsen stehen. 15:56.330 --> 16:00.230 So, jetzt könnte man einfach mal rechnen mit den Gewichten, sich 16:00.230 --> 16:02.230 überlegen, was würde das denn heißen? 16:02.490 --> 16:05.590 Wie kann man das darstellen bei dieser String-Schreibweise? 16:05.590 --> 16:13.150 Ja, wenn man solche Gewichte W von Y und I und W von Y und J addieren 16:13.150 --> 16:17.770 würde, dann bekäme man einfach an den entsprechenden Stellen in dem 16:17.770 --> 16:26.530 String der Länge M eine Zahl, je nachdem, ob das entsprechende Element 16:26.530 --> 16:31.450 in keiner der beiden vorkommt, dann steht da eine 0, oder in genau 16:31.450 --> 16:34.110 einer der beiden vorkommt, dann steht da eine 1, oder in beiden 16:34.110 --> 16:35.730 vorkommt, dann steht da eine 2. 16:36.550 --> 16:42.230 Das heißt also, wenn wir für solche N, Y und I die W von Y und I 16:42.230 --> 16:47.670 aufsummieren würden, dann würde eben in dem entsprechenden String an 16:47.670 --> 16:53.930 einer bestimmten Stelle stehen, wie oft das entsprechende X insgesamt 16:53.930 --> 16:55.110 vorkommt in den Mengen. 16:55.330 --> 16:56.890 In wie vielen Mengen das vorkommt. 16:57.990 --> 16:59.650 So könnte man das interpretieren. 17:01.450 --> 17:13.430 Und wenn gerade K rauskommt, hier diese Summe, dann heißt das, in den 17:13.430 --> 17:18.670 entsprechenden Mengen kommt jedes der Elemente aus der Grundmenge X 17:18.670 --> 17:23.230 genau einmal, insgesamt in den Mengen kommt jedes Element genau einmal 17:23.230 --> 17:23.550 vor. 17:23.550 --> 17:28.250 Das heißt also, hier mit so einer Summe K zu treffen, heißt ich habe 17:28.250 --> 17:35.730 Mengen Y aus S Strich, die genau X überdecken. 17:36.190 --> 17:37.570 So können Sie das interpretieren. 17:38.810 --> 17:40.950 Schauen wir uns das hier mal am Beispiel an. 17:41.070 --> 17:42.770 Unsere Grundmenge wären 0 bis 6. 17:44.130 --> 17:48.390 Unsere Menge S, wir sind also jetzt bei einer Instanz von ExactCover, 17:48.510 --> 17:51.370 unsere Menge S besteht ja aus Teilmengen von X. 17:52.210 --> 17:54.590 Teilmenge Y1 wäre 0, 1, 2, 3. 17:54.950 --> 17:56.270 Y2 wäre 2, 5. 17:56.810 --> 17:58.190 Y3 wäre 3, 4, 5. 17:58.330 --> 18:00.170 Und Y4 wäre 4, 5, 6. 18:00.510 --> 18:05.370 Bei ExactCover würden wir jetzt also eine Teilmenge von S suchen, so 18:05.370 --> 18:11.070 dass über die Mengen in der Teilmenge X exakt überdeckt wird. 18:11.610 --> 18:18.410 So und jetzt haben wir hier das Anzahl X für X aus X definiert, als 18:18.410 --> 18:21.770 die Anzahl der Mengen aus S, in denen das entsprechende X vorkommt. 18:23.370 --> 18:29.130 Also Anzahl 0 ist die Anzahl der Mengen aus S, in denen 0 vorkommt. 18:29.210 --> 18:31.750 0 kommt nur in der ersten vor, also Anzahl 0 ist 1. 18:32.370 --> 18:36.690 Anzahl 1, Anzahl der Mengen hier, in denen 1 vorkommt. 18:36.790 --> 18:39.830 1 kommt nur in Y1 vor, also Anzahl 1 ist 1. 18:40.630 --> 18:45.330 2, Anzahl der Mengen in S, in denen 2 vorkommt. 18:45.330 --> 18:49.610 2 kommt in Y1 und Y2 vor, in den anderen beiden nicht. 18:50.010 --> 18:55.410 Also Anzahl 2 ist 2, Anzahl 3 ist 2, weil 3 kommt hier und hier vor. 18:55.830 --> 18:59.050 Anzahl 4 ist 2, weil 4 kommt hier und hier vor. 18:59.510 --> 19:04.370 Anzahl 5 ist 3, denn 5 kommt in der Menge Y2, Y3 und Y4 vor. 19:05.070 --> 19:06.050 Anzahl 6 ist 1. 19:07.130 --> 19:13.650 Das heißt also P, was das Maximum dieser Anzahl X plus 1 ist, ist 4. 19:13.650 --> 19:19.950 Weil maximales Vorkommen eines Elementes in Mengen vor aus S ist 3, 19:20.910 --> 19:24.290 wie 5, das heißt also P wird als 4 definiert. 19:25.370 --> 19:30.850 So und jetzt eben die Gewichte von Y1, Y2, Y3, Y4, gleich in der 19:30.850 --> 19:34.410 Interpretation, was die Gewichte ausdrücken. 19:34.970 --> 19:38.950 Also die Gewichte entsprechen einfach so einem Vektor der Länge M, 19:39.190 --> 19:40.870 also hier der Länge 7. 19:41.770 --> 19:50.350 Und an der i-ten Stelle steht, ob das Element I aus X in der 19:50.350 --> 19:53.930 entsprechenden Teilmenge YJ vorkommt. 19:54.470 --> 19:59.690 Also W1 entspricht dieser Menge und das machen wir von hinten nach 19:59.690 --> 20:00.070 vorne. 20:02.750 --> 20:06.230 Denn das kommt ja von diesem Polynom und ich habe gesagt, was hier ja 20:06.230 --> 20:11.530 eigentlich steht an der entsprechenden Stelle, ist der Koeffizient, 20:11.630 --> 20:13.490 das P von X. 20:16.170 --> 20:21.490 6 kommt nicht vor, 5 kommt nicht vor, 4 kommt nicht vor, 3 kommt vor, 20:21.690 --> 20:26.230 2 kommt vor, 1 kommt vor, 0 kommt vor in Y1. 20:26.810 --> 20:32.630 Deshalb ist W von Y1 entspricht diesem String hier 0, 0, 0, 1, 1, 1, 20:32.730 --> 20:32.930 1. 20:34.270 --> 20:40.910 Wir haben einmal P hoch 0 und einmal P hoch 1 und einmal P hoch 2 und 20:40.910 --> 20:44.590 einmal P hoch 3 und 0 mal P hoch 4 und 0 mal P hoch 5 und 0 mal P hoch 20:44.590 --> 20:44.890 6. 20:45.130 --> 20:47.030 So können Sie das hier interpretieren. 20:47.430 --> 20:51.610 Die 4 steht hier unten für, das ist die Basis unseres Polynoms. 20:53.310 --> 20:58.430 Bei Y2 haben wir wieder von hinten nach vorne, 0 kommt nicht vor, also 20:58.430 --> 21:03.850 hier eine 0, 1 kommt nicht vor, also hier eine 0, 2 kommt vor, also 21:03.850 --> 21:07.090 hier steht eine 1, 3 kommt nicht vor, also steht hier eine 0, 4 kommt 21:07.090 --> 21:11.430 nicht vor, also steht hier eine 0, 5 kommt vor, also steht hier eine 1 21:11.430 --> 21:12.650 und vorne steht wieder eine 0. 21:13.390 --> 21:18.170 Also das sind sozusagen die 0, 1 Vektoren, die Sie haben, für die 21:18.170 --> 21:25.650 Mengen Y, J aus S, die einem einfach sagen, kommt das entsprechende 21:25.650 --> 21:28.030 Element aus X in der Menge vor oder nicht. 21:28.610 --> 21:32.670 Und für K hätten wir einfach hier diesen Vektor, wo an jeder Stelle 21:32.670 --> 21:33.430 eine 1 steht. 21:41.770 --> 21:48.630 So, und jetzt unser Beweis, dass eine Ja-Instanz von XSectCover auf 21:48.630 --> 21:52.050 eine Ja-Instanz von ZZSAM abgebildet wird und umgekehrt. 21:52.310 --> 21:58.790 Also steht hier so, also Ja-Instanz von XSectCover, also unser XS ist 21:58.790 --> 21:59.350 lösbar. 21:59.350 --> 22:01.810 Ja, es gibt eine exakte Überdeckung. 22:02.850 --> 22:10.170 Zu zeigen, daraus folgt, die Instanz von ZZSAM MWK ist lösbar. 22:10.450 --> 22:17.510 Es gibt so eine Teilmenge von M, deren Gewicht gerade genau K ist. 22:18.550 --> 22:24.770 Sei also S' eine Lösung von XSectCover, also eine exakte Überdeckung 22:24.770 --> 22:25.830 von X, S. 22:26.530 --> 22:27.630 Was gilt dann? 22:27.750 --> 22:33.890 Ja, dann gilt, dass die Y aus S' aufsummiert über die Y aus S', diese 22:33.890 --> 22:40.070 W von Y, das ist ja nichts anderes als Summe über Y aus S', Summe X 22:40.070 --> 22:46.830 aus Y, P von P hoch X, genau X gleich 0 bis M minus 1, P von X ist. 22:47.030 --> 22:50.210 Jedes X kommt hier genau einmal vor in der Summe. 22:50.350 --> 22:51.570 Das ist genau diese Summe. 22:51.990 --> 22:54.490 Das ist genau das K, wie wir das K definiert haben. 22:54.490 --> 22:59.950 Also von da nach da ist offensichtlich, da jedes X genau einmal 22:59.950 --> 23:04.290 überdeckt wird, kommt hier also genau in der Summe K raus. 23:04.510 --> 23:11.950 Also S' ist auch gleichzeitig eine Lösung für unsere Instanz, die wir 23:11.950 --> 23:15.170 gebaut haben von XSectCover und umgekehrt genauso. 23:15.510 --> 23:20.430 Jetzt hätten wir also eine Menge S' aus M, aus unserer Grundmenge von 23:20.430 --> 23:27.790 ZZSAM und die sei eben eine geeignete Menge für die ZZSAM Instanz. 23:27.950 --> 23:28.630 Ja, was gilt dann? 23:28.690 --> 23:33.250 Ja gut, dann ist diese Summe Y aus S', wie von Y gerade dem K, was 23:33.250 --> 23:36.610 definiert ist als Summe X gleich 0 bis M minus 1, P hoch X. 23:37.210 --> 23:41.510 Und das heißt aber, jedes X aus X kommt genau in einem dieser Y aus S' 23:41.690 --> 23:41.910 vor. 23:42.030 --> 23:46.110 Das heißt also, genau diese Menge ist, die eine Lösung ist für ZZSAM, 23:46.110 --> 23:51.310 ist auch eine Lösung für die entsprechende XSectCover Instanz. 23:51.350 --> 23:53.130 Also das ist trivial jetzt sozusagen. 23:57.100 --> 23:59.880 Wir verifizieren ja Instanzen, werden genau auf ja Instanzen 23:59.880 --> 24:00.360 abgewiesen. 24:02.460 --> 24:04.100 Okay, wie geht es weiter? 24:04.240 --> 24:06.820 Ja, es geht jetzt so weiter, dass wir eben für ein weiteres Problem 24:06.820 --> 24:08.640 über Mengen zeigen, ist irgendwie vollständig. 24:08.980 --> 24:10.920 Da ist der Beweis jetzt ziemlich einfach. 24:12.420 --> 24:14.160 Das Problem heißt Partition. 24:14.160 --> 24:18.180 Wir haben gegeben eine endliche Grundmenge und Gewichte auf der 24:18.180 --> 24:18.880 Grundmenge. 24:19.160 --> 24:23.080 Funktion auf dieser Menge, also jedem Element der Menge wird wieder 24:23.080 --> 24:25.320 eine natürliche Zahl als Gewicht zugeordnet. 24:26.320 --> 24:31.560 Und wir fragen uns, gibt es eine Teilmenge der Grundmenge, Teilmenge 24:31.560 --> 24:37.360 M' aus M, so dass die Gewichte der Elemente aus M' aufsummiert, genau 24:37.360 --> 24:43.100 dasselbe ergibt, wie die Gewichte der Elemente, die nicht in M' sind. 24:43.100 --> 24:46.200 Also in M ohne M' sind, aufsummiert. 24:48.840 --> 24:53.280 Wenn wir das haben, dann heißt das insbesondere die Gewichte aus M'. 24:54.260 --> 24:59.560 Das Gesamtgewicht von M' ist genau Hälfte des Gesamtgewichts von M. 25:01.180 --> 25:06.960 Wir machen irgendwie eine Teilmenge finden in M, deren Gesamtgewicht 25:06.960 --> 25:10.280 genau die Hälfte des Gesamtgewichts von M darstellt. 25:11.580 --> 25:14.160 Das klingt auch wieder irgendwie ziemlich einfach. 25:14.380 --> 25:17.780 Ist aber NP vollständig und das kann man leicht zeigen. 25:18.840 --> 25:21.280 Erstmal, dieses Problem ist in NP. 25:22.460 --> 25:27.100 Wenn ich Ihnen jetzt einfach so eine Menge M' zuwerfe, Teilmenge aus 25:27.100 --> 25:32.040 M, können Sie leicht verifizieren, dass das Gesamtgewicht von dem M' 25:32.840 --> 25:35.560 genau die Hälfte des Gesamtgewichts von M ist. 25:37.340 --> 25:42.820 Und die polynomiale Transformation ist von Subsetsum. 25:43.020 --> 25:47.480 Also wir reduzieren Partition auf Subsetsum in anderen Worten. 25:47.780 --> 25:51.300 Das heißt, wir geben eine polynomiale Transformation an, die jeder 25:51.300 --> 25:55.660 Instanz von Subsetsum, der Instanz von Partition zuordnet, sodass die 25:55.660 --> 25:59.800 Ja -Instanzen von Subsetsum genau Ja-Instanzen von Partition 25:59.800 --> 26:00.660 zugeordnet werden. 26:01.080 --> 26:04.300 Dafür nehmen wir also eine Instanz von Subsetsum, die besteht aus 26:04.300 --> 26:08.640 einer Grundmenge M, einer Gewichtsfunktion W und so einem Parameter K. 26:08.840 --> 26:13.900 Bei Subsetsum wollten wir wissen, gibt es ein M' aus M, sodass die 26:13.900 --> 26:16.920 Gewichte aus M' aufsummiert genau das K treffen. 26:17.960 --> 26:20.860 Das ist ja fast dasselbe Problem wie Partition. 26:21.560 --> 26:24.180 Wie konstruieren wir die Partition-Instanz? 26:25.280 --> 26:28.980 Die Grundmenge ist M-Stern, die Gewichtsfunktion ist W-Stern, aber die 26:28.980 --> 26:31.600 unterscheiden sich beide gar nicht so sehr von dem hier. 26:31.600 --> 26:38.380 Wir berechnen erstmal die Summe der Gewichte aus M, der Elemente aus M 26:38.380 --> 26:44.820 und nehmen diese Summe plus 1 als N, also definieren das als N. 26:45.700 --> 26:50.360 Und M-Stern ist nichts anderes als diese Grundmenge M von Subsetsum 26:50.360 --> 26:52.860 plus zwei weitere Elemente B und C. 26:54.380 --> 26:58.740 Und die Gewichtsfunktion auf M-Stern ist so, die Gewichte der Elemente 26:58.740 --> 27:03.160 aus M kriegen ihre alten Gewichte, wie sie sie bei Subsetsum hatten. 27:03.520 --> 27:07.720 Also W-Stern von A ist W von A, wenn A in M war. 27:08.440 --> 27:12.780 Und für die zwei zusätzlichen Elemente, die wir hier zu M-Stern dazu 27:12.780 --> 27:17.280 gesteckt haben, B und C, wählen wir jetzt noch geeignete Gewichte. 27:17.480 --> 27:23.000 Und zwar definieren wir das Gewicht von B als N minus K. 27:23.180 --> 27:27.500 K ist dieser Parameter hier und N ist ja Gewichte der Elemente aus M 27:27.500 --> 27:28.640 aufsummiert plus 1. 27:28.640 --> 27:32.580 Und Gewicht von C definieren wir als K plus 1. 27:35.240 --> 27:39.640 Also wenn wir die beiden Gewichte B und C aufsummieren würden, dann 27:39.640 --> 27:43.240 bekämen wir wieder gerade das Gewicht von M raus. 27:44.820 --> 27:52.540 Also N ist Gewicht von M plus 1 minus K und K minus K und Gewicht von 27:52.540 --> 27:54.280 C ist K plus 1. 27:54.280 --> 27:57.520 Das heißt, wenn wir die beiden Gewichte aufsummieren würden, dann 27:57.520 --> 27:58.860 bekämen wir gerade diese Summe raus. 27:59.940 --> 28:05.140 Das sieht ja irgendwie praktisch aus, denn daraus folgt gleich unsere 28:05.140 --> 28:07.900 Behauptung, dass Jahrinstanzen in Jahrinstanzen abgebildet werden. 28:08.100 --> 28:11.500 Erstmal vorneweg, die Konstruktion ist natürlich polynomial. 28:13.040 --> 28:21.740 Wieso ist das so, dass eine Jahrinstanz von Subsetsum, Instanz M, W, K 28:21.740 --> 28:28.940 genau auf eine Jahrinstanz von Partition, Instanz M-Stern, W-Stern, 28:29.040 --> 28:30.540 abgebildet wird und umgekehrt? 28:30.700 --> 28:34.200 Also wieso ist M, W, K eine Jahrinstanz genau dann, wenn die 28:34.200 --> 28:37.520 entsprechende Instanz M-Stern, W-Stern eine Jahrinstanz ist? 28:37.980 --> 28:40.960 Na gut, das ist eine Jahrinstanz, wenn so ein M-Strich aus... 28:42.180 --> 28:45.240 Das hier ist eine Jahrinstanz, wenn es so ein M-Strich aus M-Stern 28:45.240 --> 28:49.760 gibt mit Gewichte aus M-Strich aufsummiert, ist es dasselbe wie die 28:49.760 --> 28:53.160 Gewichte aus M-Stern ohne M-Strich aufsummiert. 28:54.480 --> 28:59.940 Das ist aber nichts anderes, wie wir nehmen eine Teilmenge von M, 29:01.740 --> 29:04.680 deren Gewicht genau K ergibt. 29:06.040 --> 29:13.280 Denn, erstmal wenn wir so ein M-Strich aus M-Stern betrachten, für das 29:13.280 --> 29:19.720 gilt, das enthält gerade die Hälfte des Gewichtes von M-Stern, dann 29:19.720 --> 29:23.980 können die beiden Extra-Elemente B und C nicht beide auf derselben 29:23.980 --> 29:24.640 Seite liegen. 29:24.700 --> 29:26.500 Die können nicht beide in M-Strich sein. 29:26.600 --> 29:29.060 Die können auch nicht beide in M-Stern ohne M-Strich sein. 29:29.380 --> 29:32.380 Das ist einfach zu viel, weil die einfach zu viel Gesamtgewicht haben, 29:32.480 --> 29:33.260 die beiden zusammen. 29:34.300 --> 29:39.680 Wenn wir so eine Jahrinstanz von Partition betrachten, dann halten B 29:39.680 --> 29:42.720 und C nicht beide in der Lösung. 29:48.260 --> 29:55.920 Dann folgt, da ja für M-Strich gilt, dass die Summe der Gewichte der 29:55.920 --> 30:00.960 Elemente aus M-Strich bezüglich W-Stern gleich dasselbe wie die Summe 30:00.960 --> 30:06.260 der Gewichte der Elemente aus M-Stern ohne M-Strich bezüglich W-Stern 30:06.260 --> 30:09.640 ist, dass das Gewicht von M-Strich gerade N ist. 30:09.640 --> 30:13.620 Denn das M-Stern hat insgesamt gerade Gewicht 2N. 30:14.560 --> 30:18.820 So ist N definiert und das Gewicht von B und C definiert. 30:20.860 --> 30:25.520 Dann können wir aber gerade M-Strich ohne B hernehmen und haben damit 30:25.520 --> 30:32.080 unsere Menge M-2-Strich, die Lösung von Subset-Sum ist. 30:36.250 --> 30:40.790 Und bei der Rückrichtung ist genauso, wenn wir für Subset-Sum so ein M 30:40.790 --> 30:45.310 -Strich haben, dessen Gewicht K ist, dann brauchen wir einfach nur das 30:45.310 --> 30:49.750 B noch dazu zu stecken und haben dann eine Menge M-Strich, deren 30:49.750 --> 30:53.110 Gewicht gerade erfüllt. 30:54.250 --> 31:00.190 Gewicht von M-Strich ist gleich Gewicht von M-Stern ohne M-Strich. 31:02.170 --> 31:04.670 Gut, also das war jetzt auch ziemlich einfach. 31:07.190 --> 31:11.270 Und jetzt eben das letzte Problem, für das wir heute zeigen, dass es 31:11.270 --> 31:12.850 NP -Vollständig ist, Knapsack. 31:13.510 --> 31:18.190 Und jetzt dieser NP-Vollständigkeitsbeweis von Partition hatte vor 31:18.190 --> 31:21.530 allem den Zweck, dass wir sozusagen jetzt das richtige Problem haben, 31:21.590 --> 31:24.210 um für Knapsack zu beweisen, dass es NP-Vollständig ist. 31:24.750 --> 31:28.490 Und Knapsack ist, wie ich eben schon angekündigt habe, insofern ein 31:28.490 --> 31:31.710 interessantes Problem, als dass das unter den NP-Vollständigen 31:31.710 --> 31:37.330 Problemen eines ist, was irgendwie in gewisser Weise einfacher ist als 31:37.330 --> 31:37.930 andere. 31:38.910 --> 31:45.010 Denn, wie wir später sehen werden, kann man dafür einen Algorithmus 31:45.010 --> 31:48.720 entwerfen, der auf den ersten Blick polynomial aussieht. 31:50.050 --> 31:53.950 Wenn man genauer hinguckt, ist er nicht wirklich polynomial, weil die 31:53.950 --> 32:00.050 Gewichte, die in der Problemstellung vorkommen, in dem entsprechenden 32:00.050 --> 32:07.730 Lösungsalgorithmus nicht, wie wir es fordern, nur logarithmisch 32:07.730 --> 32:10.710 eingehen, sondern tatsächlich in ihrer Größe eingehen. 32:11.110 --> 32:16.490 Das ist dann wieder nicht mehr polynomial in dem, was wir als eine 32:16.490 --> 32:22.670 sinnvolle Codierung, Codierungslänge unserer Eingabeinstanzen ansehen, 32:22.670 --> 32:27.870 weil wir ja Gewichte, also solche Zahlenwerte, mit denen gerechnet 32:27.870 --> 32:33.310 wird, so dass die Länge logarithmisch ist. 32:33.690 --> 32:38.510 Da dürfen die Gewichte dann nicht als Ganzes in die Laufzeit eingehen. 32:39.050 --> 32:43.090 Aber solche Algorithmen, die nennt man pseudopolynomial, die sind also 32:43.090 --> 32:44.310 sozusagen fast polynomial. 32:45.090 --> 32:48.510 Und für Knapsack gibt es eben so einen pseudopolynomialen Algorithmus, 32:48.630 --> 32:51.810 also insofern spielt Knapsack unter den NP-Vollständigen Problemen, 32:51.810 --> 32:54.570 die wir hier kennenlernen, eine besondere Rolle. 32:55.650 --> 33:00.210 Knapsack ist aber auch interessant, weil das das typische Problem für 33:00.210 --> 33:01.190 Nikolaus ist. 33:01.630 --> 33:04.430 Das ist nämlich das Problem, das der Weihnachtsmann oder Nikolaus 33:04.430 --> 33:05.310 lösen muss. 33:05.910 --> 33:06.750 Denn worum geht's? 33:06.770 --> 33:08.550 Also Knapsack steht für Rucksack. 33:09.550 --> 33:15.550 Es geht darum, dass Nikolaus sozusagen seinen Rucksack mit Geschenken 33:15.550 --> 33:18.710 besonders geschickt wählt. 33:18.710 --> 33:24.290 Denn Knapsack ist definiert als gegeben eine Grundmenge M. 33:25.310 --> 33:27.570 Können Sie sich vorstellen als Menge von Geschenken. 33:29.270 --> 33:33.090 Die Elemente aus M haben einerseits ein Gewicht, entspricht also 33:33.090 --> 33:38.630 wirklich dem Gewicht von Dingen und andererseits Kosten oder einen 33:38.630 --> 33:39.050 Wert. 33:40.430 --> 33:47.090 Und dann haben wir noch so ein Maximalgewicht Groß W und so ein 33:47.090 --> 33:53.790 Parameter für einen Wert, den wir auf jeden Fall erzielen wollen, C. 33:54.330 --> 33:57.570 Also gegeben ist eine Grundmenge, eine Gewichtsfunktion auf der 33:57.570 --> 34:01.290 Grundmenge, eine Kostenfunktion oder Wertefunktion auf der Grundmenge 34:01.290 --> 34:05.810 und so ein Parameter Groß W und ein Parameter Groß C. 34:05.810 --> 34:12.310 Und die Frage ist, existiert eine Teilmenge M' aus M, sodass das 34:12.310 --> 34:17.910 Gesamtgewicht dieser Teilmenge M', also aufsummiert die Gewichte der 34:17.910 --> 34:23.170 Elemente A aus M', kleiner gleich Groß W ist. 34:24.350 --> 34:29.770 Und dass andererseits die Kosten der Elemente aus M' aufsummiert 34:29.770 --> 34:32.230 mindestens Groß C ist. 34:33.090 --> 34:36.190 Warum ist das das Problem, das der Nikolaus lösen muss? 34:36.610 --> 34:40.230 Naja, er soll unter den ganzen Geschenken einpacken, 34:43.550 --> 34:48.670 Teilmenge, die er noch tragen kann, deren Gesamtgewicht, also kleiner 34:48.670 --> 34:53.490 gleich dem Maximalgewicht ist, das er tragen kann, die aber möglichst 34:53.490 --> 34:54.430 wertvoll sind. 34:54.810 --> 35:01.290 Das heißt, deren Gesamtwert größer gleich so einem vorgegebenen Wert C 35:01.290 --> 35:01.690 ist. 35:01.690 --> 35:05.250 Wenn man das jetzt übersetzt in ein Optimierungsproblem, dann wäre das 35:05.250 --> 35:14.150 Optimierungsproblem, also maximiere den Wert Summe A aus M' C von A. 35:14.490 --> 35:18.810 Mache das möglichst groß unter der Nebenbedingung, dass das 35:18.810 --> 35:23.050 Gesamtgewicht dieser Menge von Elementen kleiner gleich dem 35:23.050 --> 35:27.150 Maximalgewicht ist, was der Nikolaus tragen kann. 35:27.150 --> 35:30.810 So, das Problem ist leider NP vollständig. 35:32.310 --> 35:35.270 Dass es in NP ist, ist offensichtlich. 35:35.750 --> 35:39.890 Ja, wir können wieder für so eine Menge M' leicht verifizieren, dass 35:39.890 --> 35:43.670 deren Gesamtgewicht kleiner gleich W ist und dass deren Gesamtwert 35:43.670 --> 35:45.890 größer gleich C ist. 35:46.710 --> 35:54.150 Und man kann sich leicht überlegen, dass sich Partition polynomial in 35:54.150 --> 35:56.190 Knapsack transformieren lässt. 35:56.190 --> 35:59.610 Nehmen uns einfach eine Instanz von Partition her. 35:59.830 --> 36:03.530 Die zugehörige Instanz von Knapsack sieht folgendermaßen aus. 36:03.590 --> 36:05.330 Wir nehmen dieselbe Menge M. 36:05.890 --> 36:08.550 Die Gewichtsfunktion ist leicht modifiziert. 36:09.390 --> 36:14.190 Wir definieren noch eine Kostenfunktion und wir müssen so ein W und so 36:14.190 --> 36:15.410 ein C definieren. 36:15.570 --> 36:18.430 Und die Gewichtsfunktion ist die, wir nehmen einfach für jedes Element 36:18.430 --> 36:26.150 als Gewichtsfunktion W' bezüglich Knapsack zweimal das Gewicht, das 36:26.150 --> 36:28.650 das Element bezüglich Partition hat. 36:29.390 --> 36:31.610 Und die Kostenfunktion ist genauso definiert. 36:31.710 --> 36:37.510 Die Kosten eines Elementes sind zweimal dem Gewicht des Elementes in 36:37.510 --> 36:39.090 der entsprechenden Partition Instanz. 36:39.930 --> 36:45.390 Und diese Threshold oder dieses Maximalgewicht W und die Minimalkosten 36:45.390 --> 36:46.910 C sind gleich gewählt. 36:47.050 --> 36:51.090 Das ist einfach die Gewichte der Elemente der Grundmenge aufsummiert. 36:52.990 --> 36:55.550 Gewichte bezüglich der Partition Instanz. 36:55.950 --> 37:00.090 Das kann man in Polynomialzeit konstruieren und es ist leicht 37:00.090 --> 37:05.470 einzusehen, dass so eine Instanz Mw eine Ja-Instanz für Partition ist, 37:05.790 --> 37:10.050 genau dann, wenn die konstruierte Instanz für Knapsack eine Ja-Instanz 37:10.050 --> 37:10.930 für Knapsack ist. 37:11.630 --> 37:13.130 Das machen wir jetzt nicht mehr zu Fuß. 37:13.970 --> 37:15.730 Offensichtlich können Sie es selber überlegen. 37:16.850 --> 37:17.490 Okay. 37:19.790 --> 37:24.490 So, damit werden wir mit unseren NP-Vollständigkeitsbeweisen für die 37:24.490 --> 37:25.510 Vorlesung durch. 37:25.750 --> 37:28.050 In der Übung werden Sie sicher noch einige führen. 37:29.530 --> 37:30.470 Was jetzt? 37:33.490 --> 37:39.070 Bisher haben wir nur definiert, wie die Klassen P und NP aussehen. 37:39.210 --> 37:43.350 Und jetzt, wie sieht die Welt um diese Klassen herum aus? 37:43.350 --> 37:48.290 Also die große Frage ist ja, ob P ungleich NP ist oder gleich. 37:52.390 --> 37:53.650 Ja, was haben wir gesehen? 37:53.730 --> 37:57.870 Wir haben für zwei NP-Vollständige Probleme gesehen, dass es eine 37:57.870 --> 38:00.910 polynomiale Transformation von dem einen auf das andere gibt. 38:02.250 --> 38:07.410 Erstmal in dem, per Beweis haben wir für immer für ein Problem, für 38:07.410 --> 38:11.430 das wir erst gezeigt haben, ist NP-Vollständig eines hergenommen, von 38:11.430 --> 38:14.350 dem wir wissen, dass es NP-Vollständig ist, eine polynomiale 38:14.350 --> 38:18.650 Transformation von diesem bekannten NP-Vollständigen zu dem neuen 38:18.650 --> 38:21.050 angegeben. 38:21.710 --> 38:26.110 Nachdem das passiert ist, wissen wir nach Definition von NP 38:26.110 --> 38:30.670 -Vollständigkeit, dass wir von diesem neuen NP-Vollständigen Problem 38:30.670 --> 38:34.410 auf jeden Fall eine polynomiale Transformation zu jedem anderen NP 38:34.410 --> 38:35.670 -Vollständigen Problem haben. 38:36.230 --> 38:40.210 Insofern ist, wenn wir zwei NP-Vollständige haben, das eine können wir 38:40.210 --> 38:42.710 in das andere überführen und umgekehrt. 38:42.830 --> 38:44.030 Durch eine Polynomiale. 38:45.170 --> 38:50.330 Das heißt also, bezüglich dieser polynomialen Transformierbarkeit sind 38:50.330 --> 38:53.330 alle NP-Vollständigen Probleme gleich schwer. 38:55.250 --> 39:01.670 Bezüglich anderem, was auch mit algorithmischer Effizienz, effizienter 39:01.670 --> 39:05.910 Lösbarkeit zu tun hat oder guter Lösbarkeit, sind die durchaus 39:05.910 --> 39:07.450 unterschiedlich schwer. 39:07.450 --> 39:10.750 So wie auch für Probleme aus P gilt. 39:12.070 --> 39:15.510 Das eine haben wir vielleicht einen Lösungsalgorithmus, der Linearzeit 39:15.510 --> 39:19.130 hat und beim anderen das Beste, was man erzielen kann, vielleicht nur 39:19.130 --> 39:19.630 kubisch. 39:21.190 --> 39:25.430 Obwohl alle Probleme, die in P liegen, sind trotzdem in gewisser Weise 39:25.430 --> 39:30.770 bezüglich algorithmischer, effizienter Lösbarkeit wieder 39:30.770 --> 39:31.590 unterschiedlich schwer. 39:31.790 --> 39:37.370 Und so haben wir natürlich in NP eben einerseits dieses NP 39:37.370 --> 39:40.910 -Vollständige Probleme sind bezüglich polynomialer Transformierbarkeit 39:40.910 --> 39:41.630 gleich schwer. 39:41.750 --> 39:46.090 Bezüglich anderem, was wir noch betrachten werden, können wir durchaus 39:46.090 --> 39:47.030 differenzieren. 39:49.410 --> 39:52.690 Das hat aber, dass sie bezüglich polynomialer Transformierbarkeit 39:52.690 --> 39:57.290 gleich schwer sind, Auswirkungen auf diese Frage, ob P gleich NP ist. 39:57.430 --> 40:00.550 Das sagt uns der folgende Satz. 40:00.570 --> 40:06.710 Denn wenn wir ein NP-Vollständiges Problem haben, und für dieses 40:06.710 --> 40:11.890 zeigen können, es liegt in P, dann haben wir automatisch P gleich NP 40:11.890 --> 40:12.570 bewiesen. 40:13.490 --> 40:17.110 Und andererseits, wenn wir für dieses zeigen können, es liegt nicht in 40:17.110 --> 40:21.690 P, dann haben wir automatisch bewiesen, dass sämtliche NP 40:21.690 --> 40:24.270 -Vollständigen Probleme nicht in P liegen. 40:26.930 --> 40:31.590 Wenn wir gleich nochmal genauer uns überlegen, wieso das so ist. 40:31.590 --> 40:36.270 Aber ich formuliere den Satz jetzt nochmal für Sprachen, denn wir 40:36.270 --> 40:39.930 werden die meisten Dinge, wie wir es bisher auch gemacht haben, wenn 40:39.930 --> 40:42.990 wir wirklich ans Beweisen gehen, eben für Sprachen beweisen. 40:43.290 --> 40:49.530 Also sei L eine NP-Vollständige Sprache, dann gelten zwei Dinge. 40:49.710 --> 40:53.450 Das erste, wenn L auch in P liegt, dann ist P gleich NP. 40:54.030 --> 40:57.290 Und zweitens, wenn L nicht in P liegt, dann gilt für jede NP 40:57.290 --> 41:00.950 -Vollständige Sprache L' dass sie auch nicht in P liegt. 41:03.710 --> 41:05.410 Beweis für den ersten Teil. 41:06.150 --> 41:11.950 Also L sei NP-Vollständig und L sei in P. Folgt P gleich NP. 41:12.150 --> 41:12.370 Wieso? 41:12.670 --> 41:16.090 Also nehmen wir mal so eine Sprache aus P her, die gleichzeitig NP 41:16.090 --> 41:17.010 -Vollständig ist. 41:18.590 --> 41:23.870 Weil die Sprache in P ist, existiert eine polynomiale deterministische 41:23.870 --> 41:27.510 Turing -Maschine, die die Sprache L entscheidet. 41:30.550 --> 41:38.730 Und jetzt sei L irgendeine andere Sprache aus NP. 41:39.110 --> 41:42.290 Um zu zeigen, dass P gleich NP ist, müssen wir für eine beliebige 41:42.290 --> 41:47.290 andere Sprache aus L' aus NP zeigen können, sie liegt auch in P. Dafür 41:47.290 --> 41:48.650 nehmen wir das L' hier. 41:50.410 --> 41:54.910 Weil L NP-Vollständig ist, können wir L' polynomial transformieren auf 41:54.910 --> 41:55.150 L. 41:56.130 --> 41:59.610 Dann können wir aber mit den beiden zusammen, den beiden Sachen 41:59.610 --> 42:02.990 zusammen, der polynomial deterministischen Turing-Maschine für L, 42:03.450 --> 42:10.810 zusammen mit der polynomialen Transformation L' auf L, auch eine 42:10.810 --> 42:14.730 polynomial deterministische Turing-Maschine für L' angeben. 42:17.270 --> 42:20.450 Polynomial deterministische Turing-Maschine für L', das heißt einfach, 42:20.570 --> 42:24.250 wir haben eine polynomial deterministische Turing-Maschine, um L' zu 42:24.250 --> 42:28.050 entscheiden, um für irgendeine Eingabe, irgendein Wort zu entscheiden, 42:28.290 --> 42:30.310 ist das Wort in L' oder nicht. 42:30.830 --> 42:31.910 Wie machen wir das? 42:33.150 --> 42:38.130 Wir bauen erstmal zu dem Wort aus, für das wir das entscheiden wollen, 42:38.510 --> 42:44.250 mit der polynomialen Transformation, die wir hier haben, ein Wort, für 42:44.250 --> 42:49.610 das wir dann mit der polynomial deterministischen Turing-Maschine für 42:49.610 --> 42:52.470 L' entscheiden, ob das Wort in L' ist. 42:54.590 --> 42:59.450 Da Worte aus L' genau auf die Worte aus L' abgebildet werden, können 42:59.450 --> 43:02.950 wir damit also auch für unseren Ausgangswort entscheiden, ob es in L' 43:03.170 --> 43:03.450 war. 43:04.330 --> 43:06.870 Und alles, was wir gemacht haben, war polynomial. 43:07.590 --> 43:11.370 Das heißt, wir haben dann damit, durch die Hintereinanderausführung 43:11.370 --> 43:15.230 der polynomialen Transformation und der polynomial deterministischen 43:15.230 --> 43:19.590 Turing -Maschine auch eine polynomial deterministische Turing-Maschine 43:19.590 --> 43:20.370 für L'. 43:20.770 --> 43:25.250 Das heißt also, für unsere beliebige Sprache L' aus NP haben wir 43:25.250 --> 43:30.270 gezeigt, sie ist in P. Damit haben wir die erste Behauptung des Satzes 43:30.270 --> 43:34.850 bewiesen, dass wenn wir eine NP-vollständige Sprache haben und für die 43:34.850 --> 43:39.430 zeigen können, sie ist in NP, dass dann P gleich NP ist. 43:40.950 --> 43:45.230 Für die zweite Aussage, dass wenn wir eine NP-vollständige Sprache 43:45.230 --> 43:50.230 haben und für die zeigen können, sie ist nicht in P, dass dann 43:50.230 --> 43:54.070 sämtliche NP-vollständigen Sprachen nicht in P sind. 43:55.330 --> 43:59.630 Schauen wir uns also so eine NP-vollständige Sprache L' an, die nicht 43:59.630 --> 44:00.290 in P ist. 44:01.950 --> 44:05.070 So, und jetzt gucken wir uns eine beliebige andere NP-vollständige 44:05.070 --> 44:11.810 Sprache L' an und nehmen mal an, die wäre aber in P. Dann folgt aber 44:11.810 --> 44:15.130 mit dem ersten Teil des Satzes, den wir gerade bewiesen haben, dass P 44:15.130 --> 44:16.190 gleich NP ist. 44:16.470 --> 44:20.230 Unter Benutzung von L' für die Aussage. 44:20.830 --> 44:25.390 Und dann hätten wir sofort den Widerspruch zu der Annahme, dass aber 44:25.390 --> 44:28.670 unsere NP-vollständige Ausgangssprache L' nicht in P ist. 44:29.790 --> 44:32.550 Das heißt also, der zweite Teil des Satzes, ich gehe nochmal zurück 44:32.550 --> 44:37.190 auf den Satz, dieser zweite Teil folgt unmittelbar aus dem ersten 44:37.190 --> 44:37.490 Teil. 44:38.690 --> 44:43.510 Das waren jetzt keine schwierigen Argumente, diesen Satz zu beweisen. 44:43.830 --> 44:46.390 Aber in dem Satz steckt sozusagen drin, 44:50.950 --> 44:56.390 die Bedeutung von NP-vollständigen Problemen für die Frage, ob P 44:56.990 --> 44:58.110 ungleich NP ist. 44:58.450 --> 45:04.830 Denn wenn Sie beweisen wollen, dass P gleich NP ist, müssten Sie 45:04.830 --> 45:10.210 einfach nur für ein NP-vollständiges Problem einen polynomialen 45:10.210 --> 45:11.190 Algorithmus angehen. 45:11.190 --> 45:14.610 Einfach einen polynomialen Algorithmus für drei Satz und dann ist 45:14.610 --> 45:15.630 schon alles erledigt. 45:16.810 --> 45:22.610 Andererseits, wenn Sie beweisen wollen, P ist ungleich NP, dann 45:22.610 --> 45:26.050 müssten Sie also für irgendein NP-vollständiges Problem zeigen, das 45:26.050 --> 45:29.430 kann nicht in polynomialzeitdeterministisch gelöst werden. 45:30.310 --> 45:34.010 Dann haben Sie automatisch, dass alle NP-vollständigen Probleme 45:34.010 --> 45:35.790 außerhalb von P liegen. 45:36.630 --> 45:38.810 Dann haben Sie automatisch die Differenzierung. 45:42.960 --> 45:45.820 So, Zusammenfassung jetzt erstmal für den Moment. 45:46.020 --> 45:48.960 Also wir haben die Klasse P, Klasse der deterministischen 45:48.960 --> 45:52.740 Entscheidungen, also Klasse der Entscheidungsprobleme, die sich mit 45:52.740 --> 45:57.160 einer deterministischen Turing-Maschine in polynomialer Zeit lösen 45:57.160 --> 46:00.460 lassen und die Klasse NP, die Klasse aller Entscheidungsprobleme, die 46:00.460 --> 46:04.140 sich mit einer nicht-deterministischen Turing-Maschine in polynomialer 46:04.140 --> 46:05.380 Zeit lösen lassen. 46:12.500 --> 46:15.600 Und noch mal informell ausgedrückt, so ein Problem, so ein 46:15.600 --> 46:17.580 Entscheidungsproblem gehört zur NP. 46:18.700 --> 46:25.280 Falls gilt, ist die Antwort bei Eingabe eines Beispiels oder einer 46:25.280 --> 46:32.460 Instanz von Pi ja, dann kann die Korrektheit dafür in polynomialer 46:32.460 --> 46:36.280 Zeit überprüft werden, die Korrektheit eines Zeugen, der das belegt. 46:38.480 --> 46:44.320 Und weiter, der Begriff der NP-Vollständigkeit basiert auf dem Begriff 46:44.320 --> 46:52.380 der polynomialen Transformation, also eine Sprache L1 kann polynomial 46:52.380 --> 46:57.440 in eine Sprache L2 transformiert werden, wenn man eine Funktion haben, 46:57.960 --> 47:03.880 die Worte über dem Alphabet von L1 auf Worte über dem Alphabet von L2 47:04.660 --> 47:06.360 abbildet und folgende Eigenschaften hat. 47:06.460 --> 47:09.380 Erstmal die Funktion lässt sich durch eine polynomiale 47:09.380 --> 47:12.540 deterministische Turing-Maschine berechnen und zweitens die Worte aus 47:12.540 --> 47:15.180 L1 werden genau auf Worte aus L2 abgebildet. 47:15.820 --> 47:19.000 Und NP-Vollständig heißt eben eine Sprache, wenn sie in NP ist und 47:19.000 --> 47:24.340 sich alle anderen Sprachen aus NP polynomiell transformieren lassen. 47:28.400 --> 47:33.560 Und wenn man jetzt also annehmt, das was die Mehrheit glaubt, dass P 47:33.560 --> 47:37.900 ungleich NP ist, dann gibt es also für ein NP-Vollständiges Problem 47:37.900 --> 47:40.700 kein polynomiales Lösungsverfahren. 47:40.940 --> 47:42.300 Das ist sozusagen der Knackpunkt. 47:44.040 --> 47:47.960 Wir haben den Satz von Cook bewiesen, dass Sat NP schwer ist und dann 47:47.960 --> 47:51.560 haben wir eine ganze Menge von polynomialen Transformationen oder 47:51.560 --> 47:55.140 Reduktionen durchgeführt von Sat auf Drei-Sat und so weiter. 47:58.000 --> 47:59.720 Wie geht die Story weiter? 48:00.520 --> 48:05.240 Also wie gesagt, wir haben jetzt nur NP und P und gibt es überhaupt in 48:05.240 --> 48:10.960 dieser Welt NP und da drin liegt P noch Probleme, die weder in P sind, 48:11.080 --> 48:12.300 noch NP-Vollständig sind. 48:15.420 --> 48:22.180 Nennen wir mal die Menge der NP-Vollständigen Probleme NPC, die 48:22.180 --> 48:28.680 Teilmenge aus NP NP-Vollständig sind, NP-Complete, NPC für NP 48:28.680 --> 48:29.220 -Complete. 48:29.980 --> 48:38.020 Dann können wir auch NP ohne P-Vereinigt NPC mal angucken. 48:38.680 --> 48:43.740 Also wir nehmen in NP, wir nehmen NP, nehmen die Probleme aus P raus 48:43.740 --> 48:46.200 und nehmen die NP-Vollständigen raus. 48:46.900 --> 48:48.540 Frage, bleibt da überhaupt was übrig? 48:50.200 --> 48:54.840 Wir nennen mal die Klasse der Probleme, die da übrig bleibt NP-I, I 48:54.840 --> 48:55.920 für Intermediate. 48:58.120 --> 49:02.020 So, das ist jetzt mal das allererste, was man sich fragen kann, bleibt 49:02.020 --> 49:03.320 da überhaupt was übrig? 49:03.960 --> 49:06.160 Gibt es Probleme in NP-I? 49:08.040 --> 49:11.800 Und dann ist noch ganz interessant, folgendes zu machen. 49:12.980 --> 49:18.900 Zu Sprachen oder Problemen aus P oder NP, die Komplementsprachen 49:18.900 --> 49:20.120 betrachten. 49:20.940 --> 49:22.780 Welche Komplementprobleme? 49:26.200 --> 49:31.400 Also, ich habe eine Sprache L in P, die lebt über dem Alphabet Sigma. 49:31.400 --> 49:37.180 Also die Worte aus L sind die Worte aus Sigma-Stern, die in L sind und 49:37.180 --> 49:41.600 die restlichen, das Komplement der Sprache, ist halt Sigma-Stern ohne 49:41.600 --> 49:41.920 L. 49:42.760 --> 49:46.920 Und diese Sprachen, die gucke ich jetzt mal an, zu Sprachen L aus P. 49:49.780 --> 49:52.940 Und die Klasse dieser Sprachen, die nenne ich CoP. 49:54.780 --> 50:01.280 Die Klasse der Komplementsprachen von Sprachen aus P. Ich mache hier 50:01.280 --> 50:02.460 extra langsam, weil 50:05.530 --> 50:09.110 es sich so naheliegend ist, hier was anderes zu vermuten. 50:09.890 --> 50:10.890 Ich sage nicht was. 50:12.210 --> 50:19.590 Also CoP ist die Menge der Komplementsprachen von Sprachen aus P. Und 50:19.590 --> 50:25.930 Komplementsprache ist einfach zu einer Sprache die Sprache der Wörter 50:27.010 --> 50:30.230 über dem entsprechenden Alphabet, die nicht in der Sprache ist. 50:31.750 --> 50:35.490 Und dasselbe kannst du natürlich auch für NP-Sprachen machen. 50:35.790 --> 50:40.590 Also CoNP ist die Klasse aller Sprachen, steht hier explizit Sigma 50:40.590 --> 50:45.130 -Stern ohne L, für L in Sigma-Stern und L in NP. 50:45.390 --> 50:49.150 Also die Komplementsprachen zu Sprachen aus NP. 50:49.410 --> 50:53.570 Das sieht jetzt harmlos aus, wir werden gleich aber sehen, dass die da 50:53.570 --> 50:57.930 vielleicht doch nicht so harmlos sind, die Sprachen, die da landen. 51:01.680 --> 51:03.540 Erstmal zu diesem ersten Teil. 51:04.660 --> 51:10.680 Es ist tatsächlich bewiesen worden 1975, dass falls P ungleich NP ist, 51:11.640 --> 51:14.180 NPI ungleich leer ist. 51:14.320 --> 51:19.080 Also dann gibt es innerhalb von NP noch Probleme, die weder NP sind, 51:19.180 --> 51:20.440 noch NP-vollständig sind. 51:23.880 --> 51:25.140 Beweisen wir hier nicht. 51:26.700 --> 51:37.240 So, das Bild ist so, also NP, da drin liegt P, da drin liegt NPC, also 51:37.240 --> 51:42.320 NPC die schwersten in NP, die NP-vollständig, NP-complete und nach 51:42.320 --> 51:46.600 diesem Satz von Lettner ist es so, also wenn wirklich P ungleich NP 51:46.600 --> 51:49.980 ist, also die hier wirklich hier außerhalb von P liegen, dann gibt es 51:49.980 --> 51:51.820 noch andere, da gibt es hier noch Probleme. 51:52.900 --> 51:55.620 Da gibt es, dann ist NPI ungleich leer. 51:58.200 --> 52:01.300 So und jetzt, wie ist das mit CoP und CoNP? 52:02.340 --> 52:06.120 Also erstmal, eins ist ja offensichtlich, die Menge der 52:06.120 --> 52:13.360 Komplementsprachen von Sprachen in P ist wieder P. Eine Sprache ist in 52:13.360 --> 52:16.640 P, wenn es eine deterministische Turing-Maschine gibt, die in 52:16.640 --> 52:18.920 Polynomialzeit diese Sprache entscheiden kann. 52:20.040 --> 52:23.940 Alles deterministisch, das heißt, die kann genauso mit genau demselben 52:24.960 --> 52:28.680 Mechanismus, genau derselben Turing-Maschine kann man dann in 52:28.680 --> 52:33.100 Polynomialzeit auch das Komplement der Sprache entscheiden. 52:33.840 --> 52:40.340 Sprache entscheiden heißt ja nur, ich gebe ein Wort ein und die 52:40.340 --> 52:44.160 deterministische Turing-Maschine sagt mir nach polynomialer Zeit, das 52:44.160 --> 52:46.740 Wort ist in der Sprache oder das Wort ist nicht in der Sprache. 52:47.620 --> 52:50.960 Damit wird die Sprache entschieden und damit wird auch deren 52:50.960 --> 52:52.040 Komplement entschieden. 52:52.860 --> 52:55.380 Also P und QP sind gleich. 52:56.360 --> 52:58.280 Was ist mit NP und QNP? 52:59.200 --> 53:02.900 Was ist das Komplement einer Sprache, die in NP liegt? 53:05.260 --> 53:10.840 Werden wir gleich sehen, dass das da nicht so klar ist, was das 53:10.840 --> 53:14.520 eigentlich heißt, das Komplement einer Sprache aus NP zu entscheiden. 53:17.220 --> 53:23.760 Aber wir haben zwar P gleich Q NP, aber wie ist das eigentlich mit NP 53:23.760 --> 53:24.560 und QNP? 53:24.780 --> 53:26.540 Sind NP und QNP auch gleich? 53:27.060 --> 53:28.120 Also die erste Frage. 53:28.900 --> 53:33.440 Wenn die nicht gleich wären, wenn NP und QNP verschieden sind, dann 53:33.440 --> 53:35.880 ist auch klar, dass P ungleich NP ist. 53:36.720 --> 53:41.180 Es kann nicht gleichzeitig NP ungleich QNP, aber P gleich QP sein. 53:43.100 --> 53:43.740 Egal. 53:46.240 --> 53:51.780 Wenn NP gleich QNP ist, kann man daraus nicht automatisch P gleich NP 53:51.780 --> 53:52.480 folgern. 53:53.760 --> 53:57.100 Also irgendwie so Fragezeichen, was würde daraus folgern? 53:58.340 --> 54:03.440 Also, wie schon gesagt, erstmal die große Vermutung ist, P ungleich 54:03.440 --> 54:03.820 NP. 54:05.420 --> 54:09.760 Ich kenne niemanden, der an P gleich NP glaubt. 54:11.440 --> 54:16.400 Und es vermuten auch mindestens so viele Leute, dass NP ungleich QNP 54:16.400 --> 54:16.740 ist. 54:16.740 --> 54:20.840 Das ist sozusagen eine weitreichendere Vermutung. 54:23.080 --> 54:27.020 So, und jetzt gucken wir uns mal tatsächlich QNP an. 54:27.540 --> 54:31.700 Also wir nehmen uns ein Problem aus NP vor, am besten sogar ein NP 54:31.700 --> 54:35.220 -Vollständiges, und schauen mal, was ist denn dessen 54:35.220 --> 54:36.560 Komplementproblem? 54:37.900 --> 54:41.080 Also beim Problem ist es ja so, wenn man das in Sprachen übersetzt, 54:41.640 --> 54:45.660 die Sprache zu einem Problem ist ja die Menge der Codierungen der Ja 54:45.660 --> 54:46.460 -Instanzen. 54:47.620 --> 54:50.340 Das heißt also, das Komplement des Problems ist die Menge der 54:50.340 --> 54:52.680 Codierungen der Nein-Instanzen. 54:53.160 --> 54:54.800 Jetzt gucken wir uns Travelling Salesman an. 54:54.900 --> 54:56.280 Travelling Salesman ist das Problem. 54:56.360 --> 54:58.300 Wir haben gegeben einen vollständigen Graph mit einer 54:58.900 --> 55:02.680 Kantengewichtsfunktion, und wir haben vorgegeben einen Parameter K, 55:02.860 --> 55:09.240 und die Frage ist, gibt es eine Tour über alle Knoten des Graph, wo 55:09.240 --> 55:12.380 die jeden Knoten des Graph genau einmal durchläuft, deren 55:13.480 --> 55:16.960 Gesamtgewicht kleiner gleich K ist. 55:18.420 --> 55:21.000 Ja-Instanz ist eben eine, wo es so was gibt. 55:24.180 --> 55:28.760 Komplement von den Ja-Instanzen sind all die Instanzen, wo es sowas 55:28.760 --> 55:29.720 nicht gibt. 55:30.620 --> 55:35.920 Das heißt also, QTSP ist gegeben, ein Graph, vollständiger Graph mit 55:35.920 --> 55:42.460 Kantengewichtsfunktion und Parameter K, gibt es keine Tour über der 55:42.460 --> 55:43.600 Länge kleiner gleich K. 55:45.140 --> 55:50.460 Und wenn Sie jetzt mal an polynomielle Entscheidbarkeit mit einer 55:51.020 --> 55:54.980 nichtdeterministischen Turing-Maschine denken und sich überlegen, gibt 55:54.980 --> 55:56.200 es sowas hierfür? 56:00.660 --> 56:03.560 Dann stehen Sie wahrscheinlich genau wie ich jetzt im Moment ratlos 56:03.560 --> 56:09.220 da, um sozusagen für TSP mit einer polynomialen Turing-Maschine eine 56:09.220 --> 56:14.520 Lösung zu generieren, also eine sozusagen eine Berechnung anzugeben, 56:16.100 --> 56:20.000 die eine Ja-Instanz entscheidet, müssen Sie einfach nur für eine 56:20.000 --> 56:24.760 Instanz, eine Ja-Instanz in Polynomialzeit für eine einfach 56:25.700 --> 56:28.860 vorgegebene Tour nachprüfen. 56:28.940 --> 56:30.580 Die Tour hat eine Länge kleiner gleich K. 56:32.000 --> 56:38.480 Jetzt für so eine Ja-Instanz von QTSP ein Beleg für, es gibt keine 56:38.480 --> 56:43.200 Tour der Länge kleiner gleich K in Polynomialzeit überprüfen. 56:49.280 --> 56:49.400 Jo. 56:52.060 --> 56:55.900 Also für ein vernünftiges Codierungsschema ist leicht nachzuweisen, ob 56:57.040 --> 57:03.460 sozusagen eine TSP-Instanz eine Ja-Instanz ist, aber für eine QTSP- 57:03.460 --> 57:07.600 Instanz zu entscheiden, ob es eine Ja-Instanz ist, wissen wir nicht. 57:09.860 --> 57:13.740 QTSP ist in QNP, weil TSP in NP ist. 57:17.220 --> 57:21.340 Wozu wir gerade achselzuckend festgestellt haben, wir wissen es nicht, 57:21.480 --> 57:24.800 war die Frage, ist QTSP auch in NP? 57:25.900 --> 57:27.560 Und die Vermutung ist eben, nein. 57:28.420 --> 57:31.940 Die Vermutung ist, diese NP-vollständigen Probleme, für die gilt, 57:32.040 --> 57:34.480 deren Komplementprobleme liegen nicht in NP. 57:41.170 --> 57:47.770 Jetzt gilt, wenn L NP vollständig ist und gleichzeitig in QNP, dann 57:47.770 --> 57:49.210 ist NP gleich QNP. 57:52.560 --> 57:54.460 Das können wir uns wieder leicht überlegen. 57:55.180 --> 58:00.140 Also sei L in QNP einerseits und NP vollständig andererseits. 58:00.460 --> 58:03.400 Wir haben eine NP-vollständige Sprache L, die in QNP liegt. 58:08.280 --> 58:13.000 Weil L in QNP liegt, existiert eine polynomiale, nicht 58:13.000 --> 58:17.820 deterministische Berechnung für das Komplement von L. 58:18.080 --> 58:18.980 Also für L-Komplement. 58:20.060 --> 58:25.020 Und andererseits, weil L NP vollständig ist, gilt für alle Sprachen L' 58:25.180 --> 58:25.820 aus NP. 58:26.240 --> 58:28.540 L' ist polynomial transformierbar auf L. 58:29.700 --> 58:33.380 Dann haben wir aber auch eine deterministische polynomiale 58:33.380 --> 58:36.520 Transformation von L'-Komplement zu L-Komplement. 58:36.700 --> 58:41.600 Denn das hier heißt ja einfach, wir haben so eine Funktion, die uns 58:43.680 --> 58:47.660 Instanzen, also Wörter über dem Alphabet von L' auf Wörter über dem 58:47.660 --> 58:53.240 Alphabet von L abbildet, sodass die Wörter aus L' genau auf Wörter auf 58:53.240 --> 58:54.280 L' abgebildet werden. 58:54.680 --> 58:59.280 Also Wörter, die in L'-Komplement sind, genau auf Wörter, die in L' 58:59.360 --> 59:00.400 -Komplement sind. 59:00.540 --> 59:04.980 Das heißt also, diese polynomiale Transformation von L' auf L', die 59:04.980 --> 59:09.020 können wir auch genauso verwenden als polynomiale Transformation von 59:09.020 --> 59:11.280 L' -Komplement auf L'-Komplement. 59:12.140 --> 59:12.700 So. 59:13.800 --> 59:17.920 Deshalb existiert also, wenn wir das kombinieren mit der polynomial 59:17.920 --> 59:22.140 nicht -deterministischen Berechnung für L'-Komplement, auch eine 59:22.140 --> 59:25.760 polynomiale nicht-deterministische Berechnung für L'-Komplement. 59:26.520 --> 59:28.160 So einen Schritt haben wir schon mal öfter gemacht. 59:28.380 --> 59:31.680 Also wenn wir haben, wir können das polynomial transformieren darauf 59:31.680 --> 59:36.140 und das ist in NP, dann ist auch das hier in NP. 59:37.120 --> 59:43.000 Was aber automatisch heißt, dass dann L'-Komplement Komplement, was ja 59:43.000 --> 59:45.300 L' ist, in QNP ist. 59:46.800 --> 59:48.620 Damit haben wir den Satz bewiesen. 59:48.800 --> 59:54.640 Also wenn wir für ein NP-vollständiges Problem zeigen können, es ist 59:54.640 --> 59:58.060 auch gleichzeitig in QNP, dann ist NP gleich QNP. 59:59.180 --> 01:00:01.360 Aber wie bei TSP 01:00:04.540 --> 01:00:08.400 gesehen, scheint das für so ein NP-vollständiges Problem nicht so 01:00:08.400 --> 01:00:09.380 offensichtlich zu sein. 01:00:09.620 --> 01:00:14.400 Zumindest bei TSP glauben wir eher, das ist nicht der Fall, dass QTSP 01:00:14.400 --> 01:00:15.760 in QNP ist. 01:00:16.640 --> 01:00:22.460 Mit der Vermutung, also dass NP ungleich QNP ist, folgt auch, dass der 01:00:22.460 --> 01:00:28.180 Durchschnitt zwischen QNP und der Klasse der NP-vollständigen Probleme 01:00:28.180 --> 01:00:29.580 leer ist. 01:00:29.580 --> 01:00:33.820 Also das hier folgt unmittelbar aus dem Satz, den wir gerade bewiesen 01:00:33.820 --> 01:00:34.140 haben. 01:00:36.420 --> 01:00:41.740 Und daraus kann man jetzt ableiten, eine Beziehung zwischen NP-QNP 01:00:41.740 --> 01:00:48.960 einerseits und NPI, nämlich, wenn ein Problem in NP und in QNP liegt, 01:00:49.580 --> 01:00:54.780 aber nicht in P, dann muss es in NPI sein. 01:00:55.760 --> 01:00:57.880 NP-vollständig kann es nach dem hier nicht sein. 01:00:59.220 --> 01:01:02.800 Das heißt also, für unsere NP-Intermediate, also die Probleme, die 01:01:02.800 --> 01:01:08.980 zwar in NP liegen, aber weder in P, noch NP-vollständig sind, von 01:01:08.980 --> 01:01:12.880 denen wir bisher jetzt noch kein einziges kennengelernt haben, die 01:01:12.880 --> 01:01:18.400 haben auch mit QNP zu tun, nämlich das scheinen genau die zu sein, die 01:01:18.400 --> 01:01:22.480 in NP-Schnitt QNP ohne P sind. 01:01:25.930 --> 01:01:31.230 So, und jetzt will ich Ihnen einen Kandidaten für NPI vorstellen. 01:01:32.210 --> 01:01:36.430 Dazu fangen wir jetzt mit einem schwierigeren Problem an, was NP 01:01:36.430 --> 01:01:39.710 -vollständig ist, nämlich dem Subgraf- Isomorphie-Problem. 01:01:40.490 --> 01:01:44.450 Sie haben gegeben einen großen Graf G und ich sag mal einen kleineren 01:01:44.450 --> 01:01:45.530 Graf H. 01:01:46.050 --> 01:01:51.130 Also G besteht aus der Knotenmenge V und der Kantenmenge E und H steht 01:01:51.130 --> 01:01:58.030 aus der Knotenmenge V' und der Kantenmenge E' und das V' ist kleiner 01:01:58.030 --> 01:01:59.210 als das V. 01:01:59.690 --> 01:02:01.830 In dem Sinne ist das ein kleinerer Graf. 01:02:03.570 --> 01:02:09.330 Und jetzt ist die Frage, gibt es in G einen Subgraf, der genauso 01:02:09.330 --> 01:02:10.310 aussieht wie H? 01:02:11.130 --> 01:02:16.750 Gibt es in G einen knoteninduzierten Subgraf, der isomorph ist zu? 01:02:17.650 --> 01:02:22.530 In anderen Worten, gibt es eine Teilmenge der Knotenmenge von G, die 01:02:22.530 --> 01:02:27.250 genauso viele Knoten enthält wie H, also Teilmenge U aus V 01:02:27.930 --> 01:02:33.390 Kardinalität von U ist gleich Kardinalität von V' und gibt es eine 01:02:33.390 --> 01:02:40.370 bijektive Abbildung von V' nach U, sodass für je zwei Knoten XY aus V' 01:02:40.690 --> 01:02:46.590 gilt, wenn XY durch eine Kante verbunden sind in H, dann sind die 01:02:46.590 --> 01:02:52.310 Bilder von XY durch eine Kante verbunden in G und umgekehrt. 01:02:52.610 --> 01:02:59.690 Also der durch U induzierte Teilgraf von G sieht genauso aus wie H. 01:03:07.270 --> 01:03:09.810 Das Problem ist NP-vollständig? 01:03:12.150 --> 01:03:13.210 Verweisen wir nicht. 01:03:14.770 --> 01:03:17.910 Und jetzt kann man das ein bisschen vereinfachen, indem man einfach 01:03:17.910 --> 01:03:19.650 sagt, G und H sind gleich groß. 01:03:20.910 --> 01:03:24.390 Dann ist die Frage, einfach, die sind G und H isomorph. 01:03:25.890 --> 01:03:32.250 Also gegeben G gleich V E und H gleich V' E' Flächigkeit V gleich 01:03:32.250 --> 01:03:33.530 Mächtigkeit V'. 01:03:34.200 --> 01:03:38.950 Existiert eine bijektive Abbildung von der Knotenmenge V' nach V, 01:03:39.310 --> 01:03:46.430 sodass Kanten aus H auf Kanten aus G abgebildet werden und umgekehrt. 01:03:46.750 --> 01:03:48.870 Also sind G und H isomorph. 01:03:49.090 --> 01:03:51.570 Sehen die eigentlich von der Struktur ja genau gleich aus. 01:03:53.130 --> 01:03:58.210 Und dieses Problem ist ein Kandidat für NPI. 01:03:58.510 --> 01:04:03.210 Das wurde dann später bewiesen, dass wenn P ungleich NP ist, dann ist 01:04:03.210 --> 01:04:04.630 ja NPI ungleich leer. 01:04:04.790 --> 01:04:06.570 Das ist dann Grafisomorphie in NPI. 01:04:10.670 --> 01:04:15.170 Und Grafisomorphie liegt tatsächlich in NP und QNP. 01:04:15.970 --> 01:04:20.410 Das ist offensichtlich, dass hier wieder das Komplementproblem 01:04:20.410 --> 01:04:21.210 dasselbe ist. 01:04:23.370 --> 01:04:24.410 Sind die isomorph? 01:04:24.990 --> 01:04:26.030 Sind die nicht isomorph? 01:04:29.170 --> 01:04:31.450 Also zwei Grafen gegeben. 01:04:31.930 --> 01:04:33.330 Frage, sind die isomorph? 01:04:33.530 --> 01:04:34.470 Das ist Grafisomorphie. 01:04:34.870 --> 01:04:37.630 Komplement von Grafisomorphie wäre zwei Grafen gegeben. 01:04:38.270 --> 01:04:39.930 Frage, sind die nicht isomorph? 01:04:43.130 --> 01:04:46.470 Also die Welt sieht wohl so aus. 01:04:46.550 --> 01:04:47.350 Hier habe ich NP. 01:04:47.910 --> 01:04:51.350 Hier habe ich P. Hier habe ich NP vollständig. 01:04:53.050 --> 01:04:54.850 Dann gibt es da NPI irgendwie. 01:04:55.150 --> 01:04:57.250 Und hier ist QNP. 01:04:59.170 --> 01:05:05.230 Also wir vermuten ja, QNP ist ungleich P. Auf jeden Fall liegt P im 01:05:05.230 --> 01:05:07.890 Durchschnitt von QNP und NP. 01:05:08.310 --> 01:05:10.670 Ja, der Durchschnitt von den beiden ist nicht leer, weil P liegt auf 01:05:10.670 --> 01:05:11.270 jeden Fall drin. 01:05:11.910 --> 01:05:14.510 Und da liegen also noch die NPI Probleme drin. 01:05:21.340 --> 01:05:24.200 Ich will Ihnen jetzt mal erst noch was zeigen. 01:05:31.060 --> 01:05:35.540 Es gibt eine schöne Webseite zu P versus NP. 01:05:36.940 --> 01:05:38.980 Da ist alles Mögliche aufgeführt. 01:05:40.840 --> 01:05:43.000 Brauchbare Literatur, wie 01:05:48.650 --> 01:05:52.070 Paper von Steven Kopp zu dem Thema. 01:05:52.810 --> 01:05:55.090 Wikipedia-Seiten und so weiter. 01:05:55.610 --> 01:06:01.050 Interessante Paper zum Beispiel von Christoph Papidimitriou über NP 01:06:01.050 --> 01:06:02.010 -Vollständigkeit. 01:06:02.390 --> 01:06:02.730 So ein bisschen. 01:06:04.630 --> 01:06:08.810 Okay, das sind schon mal interessante Literaturhinweise. 01:06:11.730 --> 01:06:17.570 Ein Paper, was zum Beispiel berichtet über eine Meinungsumfrage zu P 01:06:17.570 --> 01:06:18.370 versus NP. 01:06:19.270 --> 01:06:21.030 Wie viele glauben, P gleich NP? 01:06:21.170 --> 01:06:22.810 Wie viele glauben, P ist ungleich NP? 01:06:22.810 --> 01:06:22.990 Okay. 01:06:24.090 --> 01:06:25.770 Und hier Milestones. 01:06:27.710 --> 01:06:30.230 Das darf man nicht alles jetzt so ganz ernst nehmen. 01:06:30.350 --> 01:06:34.430 Ich habe Ihnen mal anfangs, als wir mit dem Kapitel angefangen haben, 01:06:34.510 --> 01:06:42.130 gesagt, so über die Historie, seit dem Satz von Cook, seit er bewiesen 01:06:42.130 --> 01:06:45.990 wurde, sind immer mal wieder Leute hingegangen und haben gesagt, ich 01:06:45.990 --> 01:06:47.750 habe jetzt bewiesen, P gleich NP. 01:06:48.870 --> 01:06:51.870 Und auch andere, die gesagt haben, ich habe jetzt bewiesen, P ungleich 01:06:51.870 --> 01:06:52.210 NP. 01:06:52.970 --> 01:06:56.010 Mittlerweile wissen wir, wie so ein Beweis laufen könnte. 01:06:56.150 --> 01:06:59.570 Für P gleich NP würde man einfach für ein NP-Vollständiges Problem 01:06:59.570 --> 01:07:02.750 zeigen, es gibt einen polynomialen Algorithmus. 01:07:02.990 --> 01:07:08.090 Also einfach für TSP oder Subgraphisomorphie einen polynomialen 01:07:08.090 --> 01:07:09.250 Algorithmus angeben. 01:07:10.290 --> 01:07:14.010 Um zu zeigen, P ungleich NP für irgendeins dieser NP-Vollständigen 01:07:14.010 --> 01:07:17.430 Probleme zeigen, es kann keinen polynomialen Algorithmus geben. 01:07:17.430 --> 01:07:22.850 Hier ist also aufgelistet eine ganze Menge von Veröffentlichungen, in 01:07:22.850 --> 01:07:29.410 Anführungszeichen, die equal or not equal, also Gleichheit oder 01:07:29.410 --> 01:07:33.310 Ungleichheit von P und NP beweisen. 01:07:34.090 --> 01:07:37.110 Da gibt es noch ein paar andere Sachen dazwischen, wie zum Beispiel 01:07:37.110 --> 01:07:41.450 der Versuch zu zeigen, das kann man nicht beweisen, ob P gleich NP 01:07:41.450 --> 01:07:42.770 oder P ungleich NP ist. 01:07:43.070 --> 01:07:45.170 Das ist ein unentscheidbares Problem. 01:07:46.570 --> 01:07:51.050 Zu all diesen Veröffentlichungen ist anzumerken, keine ist rigoros 01:07:51.050 --> 01:07:54.710 begutachtet und für okay befunden worden. 01:07:55.770 --> 01:08:00.210 Und da gibt es so ein paar Wiederholungstäter, die immer wieder 01:08:00.210 --> 01:08:01.830 beweisen, P ungleich NP. 01:08:02.430 --> 01:08:04.270 Nicht so richtig mit Erfolg. 01:08:06.270 --> 01:08:08.890 Also, wenn Sie mal ein bisschen Spaß haben wollen, gucken Sie sich das 01:08:08.890 --> 01:08:09.110 an. 01:08:09.230 --> 01:08:14.710 Ich selber habe im Laufe meines Lebens auch immer mal wieder Beweise 01:08:14.710 --> 01:08:19.150 für P gleich NP begutachten dürfen. 01:08:20.150 --> 01:08:22.810 Gut, dann versucht mal den Fehler zu finden. 01:08:23.330 --> 01:08:26.210 Dass der Algorithmus doch nicht polynomial ist. 01:08:26.810 --> 01:08:34.530 Ein ganz häufiger Weg P gleich NP zu beweisen ist einer, den wir erst 01:08:34.530 --> 01:08:39.790 dann ganz in der nächsten Vorlesung verstehen werden, nämlich für ein 01:08:39.790 --> 01:08:44.970 NP -vollständiges Problem ein sogenanntes lineares Programm anzugeben, 01:08:45.210 --> 01:08:50.990 das nur polynomiale Größe hat und dann hat man den polynomialen 01:08:50.990 --> 01:08:54.630 Algorithmus automatisch und da war dann immer das Problem, dass das 01:08:54.630 --> 01:08:58.330 dann, wenn man genauer hinguckt, doch nicht polynomial Größe hat. 01:08:59.170 --> 01:09:07.390 Also, das zu dem zur Historie von P ungleich NP und jetzt noch für die 01:09:07.390 --> 01:09:14.230 letzten 20 Minuten heute so ein kleiner Exkurs zu Problemen, die von 01:09:14.230 --> 01:09:16.470 ihrer Formulierung her eben nicht so aussehen wie 01:09:16.470 --> 01:09:19.450 Entscheidungsprobleme, denn wir werden ja dann später, spätestens wenn 01:09:19.450 --> 01:09:22.670 wir dann approximierende Algorithmen entwerfen, ja nicht 01:09:23.530 --> 01:09:27.230 Entscheidungsprobleme angucken, sondern Optimierungsprobleme wie TSP 01:09:27.230 --> 01:09:31.970 finde eine optimale Tour oder Suchprobleme, finde eine zulässige 01:09:31.970 --> 01:09:36.570 Lösung für ein Problem einer bestimmten Art oder finde alle Lösungen 01:09:36.570 --> 01:09:38.570 oder sag mir, wie viele Lösungen es gibt. 01:09:38.930 --> 01:09:44.810 Und einfach wie man diese sozusagen andockt an die Theorie der NP 01:09:44.810 --> 01:09:47.890 vollständigen Probleme, darum geht es jetzt hier. 01:09:48.330 --> 01:09:50.410 Also, Sie können auch betrachten Suchprobleme. 01:09:50.470 --> 01:09:51.570 Was ist ein Suchproblem? 01:09:53.110 --> 01:09:58.870 Suchproblem ist gegeben durch eine Menge von Probleminstanzen, die 01:09:58.870 --> 01:10:05.270 Menge nennen wir wieder DP und eine Menge von Lösungen, Menge der 01:10:05.270 --> 01:10:06.310 Lösungen SP. 01:10:06.930 --> 01:10:11.710 Und die Lösung eines Suchproblems ist eben einfach eine Lösung, eine 01:10:11.710 --> 01:10:16.230 zulässige Lösung anzugeben, wenn es eine gibt oder zu sagen, es gibt 01:10:16.230 --> 01:10:16.830 keine. 01:10:22.150 --> 01:10:27.130 TSP Suchproblem wäre zum Beispiel folgende Formulierung, wäre ein 01:10:27.130 --> 01:10:29.170 Suchproblem zur TSP. 01:10:29.610 --> 01:10:31.850 Sie haben hier einen vollständigen Graph gegeben und eine 01:10:31.850 --> 01:10:36.970 Kantengewichtsfunktion gibt mir eine optimale Tour an, eine Tour 01:10:36.970 --> 01:10:37.790 minimaler Länge. 01:10:39.230 --> 01:10:42.590 Es kann ja mehrere Touren minimaler Länge geben, gib mir eine davon. 01:10:44.630 --> 01:10:49.370 Oder aber Sie haben noch so einen Parameter K gegeben und jetzt gib 01:10:49.370 --> 01:10:53.670 mir eine Tour der Länge höchstens K, also deren Länge kleiner gleich K 01:10:53.670 --> 01:10:53.910 ist. 01:10:54.150 --> 01:10:57.430 Davon kann es ja auch mehrere geben und Sie wollen einfach aus dieser 01:10:57.430 --> 01:11:00.330 Menge der Touren der Länge kleiner gleich K eine haben. 01:11:00.430 --> 01:11:03.070 Das wäre eine Suchproblemvariante von TSP. 01:11:05.350 --> 01:11:07.770 Nettes Problem ist Hamilton-Kreis. 01:11:07.890 --> 01:11:09.930 Das hat so ein bisschen zu tun mit TSP. 01:11:10.610 --> 01:11:11.930 Gegeben ein Graph. 01:11:13.210 --> 01:11:18.930 Ein Hamilton-Kreis ist eine Tour durch den Graph, bei der jeder Knoten 01:11:18.930 --> 01:11:20.530 genau einmal durchlaufen wird. 01:11:21.410 --> 01:11:26.290 Das heißt also, eine Permutation der Knotenmenge so das gilt für zwei 01:11:26.290 --> 01:11:30.010 in der Permutation aufeinander folgende Knoten habe ich auch eine 01:11:30.010 --> 01:11:30.390 Kante. 01:11:32.190 --> 01:11:36.490 Wenn Sie einen beliebigen Graph gegeben haben, ist nicht klar, ob es 01:11:36.490 --> 01:11:38.370 so einen Hamilton-Kreis gibt. 01:11:39.250 --> 01:11:43.590 Also ein relevantes Problem für einen beliebigen Graphen zu 01:11:43.590 --> 01:11:45.510 entscheiden, gibt es einen Hamilton-Kreis? 01:11:46.670 --> 01:11:51.790 Das Problem ist NP-Vollständig und jetzt Versuchproblem dazu, wer gibt 01:11:51.790 --> 01:11:52.830 mir einen Hamilton-Kreis? 01:11:52.950 --> 01:11:56.650 Also nicht nur gegeben ein Graph beantworte mir die Frage, gibt es 01:11:56.650 --> 01:12:00.250 einen Hamilton-Kreis, sondern gegeben ein Graph, gibt mir einen 01:12:00.250 --> 01:12:02.130 Hamilton -Kreis, wenn es einen gibt. 01:12:04.670 --> 01:12:07.550 Und dann könnten Sie aber auch das Aufzählungsproblem dazu 01:12:07.550 --> 01:12:08.510 formulieren. 01:12:12.050 --> 01:12:15.350 Allgemeinaufzählungsproblem P, Sie haben wieder das Problem gegeben 01:12:15.350 --> 01:12:20.270 durch die Menge der Probleminstanzen und Sie haben die Menge aller 01:12:20.270 --> 01:12:25.050 zulässigen Lösungen gegeben und beim Aufzählungsproblem wollen Sie 01:12:25.050 --> 01:12:26.330 wissen, wie viele gibt es? 01:12:26.330 --> 01:12:27.570 Wie viele Lösungen gibt es? 01:12:28.570 --> 01:12:30.470 Das wäre jetzt bei Hamilton-Kreis. 01:12:30.730 --> 01:12:36.230 Sie haben den Graph gegeben und Sie interessieren sich dafür, wie viel 01:12:36.230 --> 01:12:37.530 Hamilton -Kreise es gibt. 01:12:38.110 --> 01:12:40.310 Es kann ja durchaus Unterschiede, mehrere geben. 01:12:41.690 --> 01:12:43.450 Das wäre ein Aufzählungsproblem. 01:12:44.970 --> 01:12:49.510 So, jetzt haben wir für diese Art von Problemen das Gefühl, dass sie 01:12:49.510 --> 01:12:52.490 mindestens so schwer sind, wie das entsprechende Entscheidungsproblem. 01:12:52.830 --> 01:12:56.130 Das also zum Beispiel das Aufzählungsproblem für Hamilton-Kreis oder 01:12:56.130 --> 01:12:59.670 das Suchproblem für Hamilton-Kreis mindestens so schwer ist, wie das 01:12:59.670 --> 01:13:01.550 Entscheidungsproblem für Hamilton-Kreis. 01:13:02.310 --> 01:13:05.790 Entscheidungsproblem kann man recht leicht beweisen, das ist NP 01:13:05.790 --> 01:13:06.610 -vollständig. 01:13:07.170 --> 01:13:09.770 Das heißt also, die anderen, das Suchproblem zu Hamilton-Kreis, das 01:13:09.770 --> 01:13:13.390 Aufzählungsproblem zu Hamilton-Kreis ist dann mindestens so schwer wie 01:13:13.390 --> 01:13:14.290 NP -vollständig. 01:13:15.330 --> 01:13:17.650 Und den Problemen können Sie jetzt noch nicht mal sagen, die sind in 01:13:17.650 --> 01:13:21.210 NP, weil die einfach von der Art, wie sie gestellt sind, da nicht 01:13:21.210 --> 01:13:21.790 reinpassen. 01:13:23.290 --> 01:13:27.330 Eins vorne weggenommen, das kommt in der nächsten Vorlesung, wenn man 01:13:27.330 --> 01:13:33.690 so ein Problem hat, was noch nicht mal in NP ist, von dem man das 01:13:33.690 --> 01:13:37.030 nicht beweisen kann, wo man es nicht weiß, von dem man aber zeigen 01:13:37.030 --> 01:13:42.830 kann, es ist mindestens so schwer, wie die NP-vollständigen Probleme. 01:13:44.650 --> 01:13:47.290 Dann sagt man bei so einem Problem, das ist NP-schwer. 01:13:47.670 --> 01:13:54.010 Wenn Sie den Begriff NP-schwer sehen in der Literatur, dann trifft das 01:13:54.010 --> 01:13:57.030 sozusagen diese Art von Problemen, die so schwer sind wie die NP 01:13:57.030 --> 01:13:59.910 -vollständigen, aber von denen man noch nicht mal weiß, ob sie in NP 01:13:59.910 --> 01:14:00.250 sind. 01:14:00.910 --> 01:14:04.090 Für NP-vollständige kann man natürlich auch sagen, sind NP-schwer. 01:14:04.290 --> 01:14:08.810 Das ist so das übliche Wort, dass man für Probleme, die erst gar nicht 01:14:08.810 --> 01:14:12.250 als Entscheidungsproblem formuliert sind, wie zum Beispiel das 01:14:12.250 --> 01:14:17.110 Optimierungsproblem von TSP, die aber mindestens so schwer sind, wo 01:14:17.110 --> 01:14:19.270 das Entscheidungsproblem NP-vollständig ist. 01:14:19.390 --> 01:14:22.110 Da sagt man zum Beispiel dann so, das ist ein NP-schweres Problem. 01:14:22.450 --> 01:14:27.370 So und formal sozusagen die Reduktion von so einem Problem, das ein 01:14:27.370 --> 01:14:33.190 Suchproblem ist, zu NP-vollständigen Problemen, dazu gibt es eben auch 01:14:33.190 --> 01:14:40.170 eine Definition und dazu definieren wir erstmal eine Relation, die 01:14:40.170 --> 01:14:44.570 jeder Instanz eines Suchproblems eine Lösung zuordnet. 01:14:44.570 --> 01:14:50.710 Und dann sagen wir, eine Funktion realisiert diese Relation, wenn sie 01:14:50.710 --> 01:14:56.130 einer Instanz, für die es eine Lösung gibt, eine zuordnet. 01:14:57.170 --> 01:14:58.830 Und ansonsten Y, 01:15:01.850 --> 01:15:05.090 ansonsten, also wenn die Instanz keine Lösung hat, der Y zuordnet. 01:15:06.390 --> 01:15:10.710 Dann wird damit die Relation R realisiert, nämlich für jedes X haben 01:15:10.710 --> 01:15:15.830 wir so ein Y, XY aus R, beziehungsweise wenn X keine Lösung Y 01:15:16.570 --> 01:15:19.310 existiert, dann ist das XY. 01:15:20.570 --> 01:15:25.230 Und wir sagen, ein Algorithmus löst das durch diese Relation 01:15:25.230 --> 01:15:31.770 beschriebene Suchproblem, wenn er eben diese, so eine Funktion 01:15:32.410 --> 01:15:35.450 berechnen kann, die Relation realisiert. 01:15:36.590 --> 01:15:44.510 Und um jetzt sozusagen solche Suchprobleme zu reduzieren auf entweder 01:15:44.510 --> 01:15:51.530 vollständige Probleme, benutzt man eine Oracle-Turing-Maschine, die 01:15:51.530 --> 01:15:53.890 aber was anderes ist als eine nicht-deterministische. 01:15:55.110 --> 01:15:58.310 Es ist jetzt ein bisschen blöd, dass sie Oracle-Turing-Maschine heißt, 01:15:58.450 --> 01:16:02.310 aber so heißt sie nur mal in der Literatur und die ist folgendermaßen 01:16:02.310 --> 01:16:04.950 definiert, das ist eine deterministische Turing-Maschine, die 01:16:04.950 --> 01:16:08.230 äquivalent ist zu dem Modell der deterministischen Turing-Maschine, 01:16:08.230 --> 01:16:12.110 das wir bisher betrachtet haben, aber die hat halt noch so ein Oracle 01:16:12.110 --> 01:16:18.150 -Modul und das Oracle-Modul ist so eine Funktion, die also einem Wort 01:16:19.370 --> 01:16:23.510 über dem Eingabealphabet, ein anderes Wort über dem Eingabealphabet 01:16:23.510 --> 01:16:24.370 zuordnet. 01:16:25.070 --> 01:16:28.030 Also eine Oracle-Turing-Maschine ist eine deterministische Turing 01:16:28.030 --> 01:16:32.750 -Maschine, die hat zusätzlich ein ausgezeichnetes Oracle-Band und zu 01:16:32.750 --> 01:16:35.910 den üblichen Zuständen, die man so kennt bei einer deterministischen 01:16:35.910 --> 01:16:39.750 Turing -Maschine, hat sie noch zwei Zustände, QF und QA. 01:16:40.190 --> 01:16:46.330 QF steht für Fragezustand, QA steht für Antwortzustand und QF und QA 01:16:46.330 --> 01:16:48.370 gehören hier zu diesem Oracle-Band. 01:16:48.870 --> 01:16:54.890 Die Arbeitsweise ist eben die, solange wir nicht in QF kommen, 01:16:55.730 --> 01:16:58.950 arbeitet die Turing-Maschine ganz normal wie eine deterministische 01:16:58.950 --> 01:17:05.730 Turing -Maschine und wenn wir nach QF kommen und wird nachgeguckt, wo 01:17:05.730 --> 01:17:11.210 steht der Kopf, der zum Oracle-Band gehört. 01:17:11.550 --> 01:17:18.470 Wenn der Kopf auf Position I des Oracle-Band steht und an der Stelle 1 01:17:18.470 --> 01:17:25.090 bis I Wort Y steht, dann macht die Oracle-Turing-Maschine folgendes, 01:17:27.210 --> 01:17:34.610 wenn das Y, also wirklich ein Wort über dem Eingabealphabet ist, dann 01:17:34.610 --> 01:17:40.810 löscht es das Wort in einem Schritt und schreibt das Bild des Wortes 01:17:40.810 --> 01:17:45.590 unter dieser Funktion G aufs Band. 01:17:47.910 --> 01:17:52.350 Und dann ist der Folgezustand QA, der Antwortzustand, der sagt so, das 01:17:52.350 --> 01:17:54.330 ist jetzt die Antwort auf die Frage. 01:17:57.090 --> 01:18:00.250 Wie gesagt, die Oracle-Turing-Maschine ist was anderes als eine nicht 01:18:00.250 --> 01:18:03.230 -deterministische Turing-Maschine, denn die macht immer dasselbe. 01:18:03.510 --> 01:18:09.850 Die macht in so einer Situation, auf dem Oracle-Band steht Y und ich 01:18:09.850 --> 01:18:14.290 bin in den Zustand QF gekommen, immer dasselbe, nämlich sie schreibt G 01:18:14.290 --> 01:18:17.450 von Y über das Y drüber. 01:18:18.530 --> 01:18:22.030 Insofern ist das was anderes als dieses in Anführungszeichen Oracle, 01:18:22.170 --> 01:18:26.370 das wir uns bei der nicht-deterministischen Turing-Maschine als 01:18:26.370 --> 01:18:28.550 Veranschaulichung vorgestellt haben. 01:18:29.010 --> 01:18:32.690 Und dann kann man eine Turing-Reduktion definieren. 01:18:33.350 --> 01:18:38.210 Wir haben zwei Relationen gegeben über eine Eingabealphabet Sigma und 01:18:38.210 --> 01:18:42.030 eine Turing-Reduktion von der einen Relation auf die andere. 01:18:42.630 --> 01:18:46.110 Einfach, sie stellen sich als Relation jetzt unter Relation so ein 01:18:46.110 --> 01:18:47.030 Suchproblem vor. 01:18:47.430 --> 01:18:53.710 Suchproblem, eine Relation ordnet eine Eingabe, eine Ausgabe vor, das 01:18:53.710 --> 01:18:55.730 ist genau das Lösen eines Suchproblems. 01:18:55.910 --> 01:19:00.250 So, und jetzt wird also eins auf das andere überführt durch eine 01:19:00.250 --> 01:19:06.030 Oracle -Turing-Maschine M, deren Oracle gerade R' realisiert und die 01:19:06.030 --> 01:19:10.270 selbst in polynomialer Zeit die Funktion berechnet, die R realisiert. 01:19:14.170 --> 01:19:19.370 Dann haben sie, falls R' in polynomialer Zeit realisierbar ist und R 01:19:20.350 --> 01:19:25.510 polynomial Turing transformierbar auf R', dass auch R' in polynomialer 01:19:25.510 --> 01:19:27.150 Zeit realisierbar ist. 01:19:27.290 --> 01:19:30.850 Sie haben jetzt sowas wie eine polynomiale Transformation zwischen NP 01:19:30.850 --> 01:19:33.430 -vollständigen Problemen, zwischen solchen Suchproblemen. 01:19:35.470 --> 01:19:37.790 Und da haben sie auch wieder Transitivität. 01:19:40.980 --> 01:19:45.700 Und dann nennen wir eben ein Suchproblem Pi, NP schwer, falls es eine 01:19:45.700 --> 01:19:49.740 NP -vollständige Sprache gibt, die sich Turing transformieren lässt 01:19:49.740 --> 01:19:53.120 auf die Sprache zu Pi. 01:19:54.700 --> 01:19:58.120 Also ich bin da jetzt ein bisschen schnell rübergegangen, obwohl das 01:19:58.120 --> 01:20:00.740 vielleicht nicht so ganz leicht zu verdauen ist. 01:20:01.140 --> 01:20:03.920 Was ich Ihnen damit zeigen will, ist einfach, dass man sozusagen 01:20:04.620 --> 01:20:07.760 Probleme, die nicht als Entscheidungsprobleme formuliert sind, 01:20:08.180 --> 01:20:11.180 sozusagen anschließen kann an unsere NP-vollständigen Probleme. 01:20:11.320 --> 01:20:14.620 Da gibt es eben auch ein Mechanismus, um zu zeigen, so ein Problem ist 01:20:14.620 --> 01:20:17.940 mindestens so schwer wie ein NP-vollständiges Problem, nämlich über 01:20:17.940 --> 01:20:18.620 Turing -Reduzierbarkeit. 01:20:21.900 --> 01:20:27.540 Und TSP-Suchproblem ist eben NP schwer, weil man das TSP-Suchproblem 01:20:27.540 --> 01:20:32.880 in der Variante 1, wie wir es eh haben, eben hat sozusagen mit so 01:20:32.880 --> 01:20:37.220 einer Turing-Reduktion auf das TSP-Entscheidungsproblem reduzieren. 01:20:42.020 --> 01:20:46.240 Beweiskitze, also ich betrachte sozusagen das Entscheidungsproblem zu 01:20:46.240 --> 01:20:52.140 TSP und ich betrachte das Suchproblem zu TSP und die zu den beiden 01:20:52.860 --> 01:20:56.680 zugehörigen Relationen zum Entscheidungsproblem. 01:20:56.860 --> 01:21:01.040 Die zugehörige Relation sieht einfach so aus, eine Instanz wird Ja 01:21:01.040 --> 01:21:02.300 oder Nein zugeordnet. 01:21:03.560 --> 01:21:11.440 Also, für die x Ja-Instanzen von TSP-Entscheidungsproblemen wird x J, 01:21:11.600 --> 01:21:12.760 J für Ja zugeordnet. 01:21:13.620 --> 01:21:18.960 Die Relation zum Suchproblem ist eine Instanz, das TSP-Problem wird 01:21:18.960 --> 01:21:20.480 eine Lösung, eine Tour zugeordnet. 01:21:20.920 --> 01:21:29.780 Die Relation zum Suchproblem ist so eine x x Instanz, das TSP-Problem 01:21:29.780 --> 01:21:32.360 wird eine Y, Y Lösung zugeordnet. 01:21:33.280 --> 01:21:37.560 So, und dann kann man das eine Turing reduzieren auf das andere oder 01:21:37.560 --> 01:21:41.640 eine Turing-Transformation von der Relation zum Entscheidungsproblem 01:21:41.640 --> 01:21:44.380 auf die Relation zum Suchproblem vornehmen. 01:21:45.280 --> 01:21:50.460 Dafür müssen wir so eine Oracle-Turing- Oracle ist einfach so eine 01:21:50.460 --> 01:21:53.580 Funktion, die ein Wort aus Sigma-Stern an Wort aus Sigma-Stern 01:21:54.260 --> 01:22:00.280 abbildet und die realisiert eben die Relation zum Suchproblem und die 01:22:00.280 --> 01:22:04.080 arbeitet jetzt folgendermaßen für eine Eingabe, schreibe die Eingabe 01:22:04.080 --> 01:22:09.580 auf das Oracle-Band und gehe in den Fragezustand über, weise dann das 01:22:09.580 --> 01:22:16.840 Oracle an, in einem Schritt das Bild des Oracles unter der Funktion Q, 01:22:17.500 --> 01:22:22.640 unter der Funktion Omega hinzuschreiben und gehe dann in den Zustand 01:22:22.640 --> 01:22:27.280 QA über und dann wird einfach überprüft, ob Omega von W eine Tour der 01:22:27.280 --> 01:22:28.940 Länge kleiner gleich K kodiert. 01:22:29.700 --> 01:22:34.900 Falls ja, lösche das Band und schreibe Ja, andernfalls lösche einfach 01:22:34.900 --> 01:22:42.720 das Band und dann realisiert die gegebene Turing-Maschine Turing 01:22:42.720 --> 01:22:46.780 -Maschine realisiert die Relation zum Entscheidungsproblem und hat 01:22:46.780 --> 01:22:49.340 eine polynomial beschränkte Laufzeit. 01:22:53.380 --> 01:22:59.380 Wie gesagt, diese letzte Viertelstunde war Exkurs in der Welt, also in 01:22:59.380 --> 01:23:03.640 der Übung, nicht mehr weiter vertiefen werden, also es war jetzt nur 01:23:03.640 --> 01:23:07.940 noch so ein bisschen Add-on, um zu sehen, das geht noch weiter und 01:23:07.940 --> 01:23:12.900 auch eben Schwierigkeit von Problemen und insbesondere Probleme, die 01:23:12.900 --> 01:23:16.460 nicht wie Entscheidungsprobleme aussehen, da irgendwie in den Kontext 01:23:16.460 --> 01:23:20.580 zur NPV-Ständigkeit zu bringen, das hat eine saubere Grundlage. 01:23:22.740 --> 01:23:24.160 Okay, das wäre es für heute.