WEBVTT 00:07.350 --> 00:11.150 Herzlich Willkommen, Willkommen zur Vorlesung. 00:13.330 --> 00:16.630 Willkommen zur Vorlesung Theoretisch Grundlagen der Informatik. 00:18.210 --> 00:22.170 Sie haben mich ja schon kennengelernt, ich vertrete heute wieder Frau 00:22.170 --> 00:22.690 Wagner. 00:24.630 --> 00:31.270 Und ich habe heute das Glück, die Aufgabe übertragen zu bekommen, 00:32.650 --> 00:35.590 eines der wichtigsten Konzepte dieser ganzen Vorlesung heute 00:35.590 --> 00:36.270 vorzustellen. 00:37.150 --> 00:39.270 Nämlich das der NP-Vollständigkeit. 00:40.230 --> 00:43.730 Und wenn Sie mich oder zumindest unsere Gruppe fragen, womit wir 00:43.730 --> 00:46.890 täglich so zu tun haben, dann ist NP-Vollständigkeit wahrscheinlich 00:46.890 --> 00:50.530 wirklich das Konzept der Vorlesung, mit dem wir am meisten zu tun 00:50.530 --> 00:50.870 haben. 00:52.610 --> 00:56.510 Deswegen stellen Sie bitte heute sicher, dass Sie verstehen, worum es 00:56.510 --> 00:59.550 geht und stellen Sie Fragen, wenn Sie welche haben. 01:01.130 --> 01:05.750 Alles basiert auf der nicht-deterministischen Turing-Maschine, die Sie 01:05.750 --> 01:07.570 letzte Vorlesung kennengelernt haben. 01:09.230 --> 01:13.650 Und wir betrachten das meistens oder eigentlich ausschließlich für den 01:13.650 --> 01:16.550 Fall von Entscheidungsproblemen und nicht von Formalentsprachen. 01:18.670 --> 01:22.610 Also Entscheidungsprobleme und nicht-deterministische Turing 01:22.610 --> 01:25.370 -Maschinen, die diese Entscheidungsprobleme lösen. 01:25.830 --> 01:28.950 Da haben Sie das Orakel-Modell kennengelernt, was in zwei Stufen 01:28.950 --> 01:29.190 läuft. 01:29.550 --> 01:33.670 Und hier ist nochmal die kurze Übersicht und mit einem Beispiel. 01:34.110 --> 01:40.110 Also, Eingabe ist ein Wort aus Sigma-Stern, was einfach nur eine 01:40.110 --> 01:43.250 Codierung einer Instanz des Entscheidungsproblems ist. 01:43.770 --> 01:48.350 Das heißt, wir sagen, dass die Instanz ist I, das Entscheidungsproblem 01:48.350 --> 01:55.090 ist P, und die Menge aller Instanzen ist D und P. Und die Orakel 01:55.090 --> 01:58.390 -Turing -Maschine wird jetzt diese Eingabe bearbeiten, um sie zu 01:58.390 --> 02:00.030 verifizieren oder abzulehnen. 02:00.610 --> 02:10.110 Und in der ersten Stufe wird ein Orakel berechnet, vor die Eingabe auf 02:10.110 --> 02:10.870 das Band geschrieben. 02:11.630 --> 02:14.710 Stellen Sie sich das so vor, das ist der Nicht-Determinismus. 02:15.670 --> 02:19.030 Stellen Sie sich das so vor wie bei endlichen Automaten, bei nicht 02:19.030 --> 02:20.550 -deterministischen endlichen Automaten. 02:20.630 --> 02:24.070 Da haben Sie manchmal die Entscheidungsmöglichkeit, wohin Sie gehen, 02:24.130 --> 02:24.950 wenn Sie ein Zeichen lesen. 02:25.770 --> 02:29.190 Und jedes Mal sagt das Orakel Ihnen, wohin Sie gehen. 02:30.130 --> 02:32.270 Und hier haben wir das einfach komplett getrennt. 02:32.350 --> 02:36.210 Wir haben gesagt, erst schreibt das Orakel alle Zufallsentscheidungen, 02:36.310 --> 02:38.890 die es treffen muss, vorne auf das Band sozusagen. 02:39.930 --> 02:43.630 Und dann wird mit diesen Entscheidungen, die dort getroffen wurden, 02:44.450 --> 02:46.950 die Maschine deterministisch abgearbeitet. 02:48.550 --> 02:51.230 Und wir interpretieren das so für den Fall eines 02:51.230 --> 02:56.170 Entscheidungsproblems, dass uns das Orakel da vorne einen 02:56.170 --> 02:58.130 Lösungsvorschlag hinschreibt. 02:59.290 --> 03:03.110 Es schlägt also vor, wie wir den Nicht-Determinismus nutzen sollten, 03:03.330 --> 03:05.110 um diese Eingabe zu akzeptieren. 03:07.920 --> 03:15.220 Also ein Lösungsbeispiel für die gegebene Instanz I wird auf das Band 03:15.220 --> 03:16.900 geschrieben, oder wir hoffen, dass das passiert. 03:17.100 --> 03:22.160 Wenn es denn eine Ja-Instanz ist, dass wir dann mit diesem Vorschlag 03:22.160 --> 03:25.020 zusammen auch die Instanz akzeptieren können. 03:25.160 --> 03:27.400 Das heißt, die Maschine in den akzeptierenden Endzustand bringen 03:27.400 --> 03:27.760 können. 03:29.020 --> 03:31.520 Denn in der zweiten Stufe, wenn das Orakel fertig ist mit dem 03:31.520 --> 03:34.260 Schreiben, dann ist nur noch deterministisch. 03:35.140 --> 03:36.620 Kein Nicht-Determinismus mehr. 03:36.920 --> 03:40.500 Nur noch deterministisch, aber der Lese-Schreibkopf der Turing 03:40.500 --> 03:43.140 -Maschine kann jetzt immer wieder in diesen Lösungsvorschlag gucken, 03:43.640 --> 03:45.620 und gucken, was es denn tun soll. 03:47.720 --> 03:50.660 Und der Lösungsvorschlag, also wir sagen für ein Entscheidungsproblem, 03:50.740 --> 03:54.140 der Lösungsvorschlag wird sozusagen überprüft, ob er denn stimmt. 03:54.740 --> 03:58.680 Ob es wirklich eine Lösung für diese Instanz ist, und wenn ja, dann 03:58.680 --> 04:01.700 akzeptieren wir, und wenn nein, dann lehnen wir ab. 04:03.100 --> 04:08.260 Und wir müssen diese zweite Stufe also so konzipieren, dass die 04:08.260 --> 04:13.120 einzige Möglichkeit, dass das Orakel uns mit dem Lösungsvorschlag dazu 04:13.120 --> 04:17.680 bringen kann, zu akzeptieren, die einzige Möglichkeit dafür muss sein, 04:17.780 --> 04:19.380 dass es wirklich eine Ja-Instanz ist. 04:21.640 --> 04:23.380 Also vielleicht machen wir das an einem Beispiel. 04:25.000 --> 04:26.820 Travelling Sales mein Problem, TSP. 04:27.280 --> 04:28.900 Das haben Sie schon kennengelernt. 04:30.220 --> 04:34.200 Da geht es darum, wir haben einen Graphen mit Knotenmenge V, das ist 04:34.200 --> 04:40.020 hier in blau gegeben, diese Instanz, und Kantenmenge E, und dann gibt 04:40.020 --> 04:44.100 es eine Kostenfunktion auf den Kanten mit einer Zahl K, wie lang 04:44.100 --> 04:45.400 unsere Tour sein soll. 04:46.240 --> 04:49.500 Das Entscheidungsproblem ist, gibt es eine Möglichkeit, durch den 04:49.500 --> 04:55.540 Graphen zu gehen, jeden Knoten genau einmal zu besuchen, jeder Schritt 04:55.540 --> 05:01.080 geht entlang einer Kante, und die Summe dieser Kantenkosten, ich 05:01.080 --> 05:05.000 zähle, die wir dort nehmen immer, soll insgesamt höchstens K sein. 05:05.680 --> 05:08.720 Das ist dieses handlungsreisende Problem, wir wollen durch die Städte 05:08.720 --> 05:11.100 gehen und möglichst geringe totale Distanz haben. 05:11.780 --> 05:13.920 Okay, das ist die Instanz. 05:15.000 --> 05:17.320 Wir fragen uns, existiert so eine Tour? 05:17.780 --> 05:20.760 Wenn so eine Tour existiert, dann ist es eine Ja-Instanz, wenn es 05:20.760 --> 05:23.200 keine Tour existiert, ist es eine Nein-Instanz. 05:24.120 --> 05:28.000 Also was sollte uns das Orakel jetzt für einen Tipp geben? 05:28.920 --> 05:33.960 Naja, das Orakel sagt uns, wie wir denn die Städte ablaufen sollen, 05:34.040 --> 05:36.380 wie wir die Knoten, in welcher Reihenfolge wir die besuchen sollen. 05:36.960 --> 05:41.200 Das heißt, das Orakel schreibt hier, was hier in Rot hervorgehoben 05:41.200 --> 05:45.180 ist, einen Lösungsvorschlag, das ist einfach eine Permutation der 05:45.180 --> 05:45.420 Knotenmengen. 05:48.260 --> 05:51.880 Zuerst zu dem Knoten, dann zu dem Knoten, dann zu dem Knoten, dann zu 05:51.880 --> 05:52.720 dem Knoten usw. 05:55.600 --> 06:00.680 Und wir machen jetzt die zweite Stufe so, dass wir nur noch 06:00.680 --> 06:04.880 überprüfen, ob denn das, was das Orakel da vorne hingeschrieben hat, 06:04.880 --> 06:09.840 wirklich eine zyklische Permutation ist, und ob die denn wirklich eine 06:09.840 --> 06:14.140 zulässige Permutation ist, also ob ich wirklich immer von x i zu x i 06:14.140 --> 06:18.020 plus 1 entlang einer Kante gehen darf, also weil die Kante in dem 06:18.020 --> 06:22.320 Graphen ist, und ob, wenn ich diese ganzen Kanten benutzen würde, und 06:22.320 --> 06:25.060 die ganzen Längen aufsummieren würde, das Ganze wirklich kleiner 06:25.060 --> 06:25.880 gleich K ist. 06:28.040 --> 06:32.580 Und wenn das alles stimmt, und das Orakel uns eine richtige Lösung 06:32.580 --> 06:37.020 dorthin geschrieben hat, dann überprüfen wir das deterministisch und 06:37.020 --> 06:37.940 sagen akzeptieren. 06:39.740 --> 06:42.440 Und sobald irgendwas komisch ist, wenn es irgendwie gar keine 06:42.440 --> 06:45.880 Knotenreihenfolge ist, oder irgendwie gar keine richtige Tour, oder 06:45.880 --> 06:50.500 die Länge zu lang ist, oder ein Knoten vergessen wurde, wenn das 06:50.500 --> 06:53.440 Orakel irgendwas hinschreibt, was keine Lösung ist, lehnen wir ab. 06:56.520 --> 07:03.040 Wir gehen dann davon aus, dass wir eine Instanz annehmen, wenn es eine 07:03.040 --> 07:05.740 mögliche akzeptierende Berechnung gibt. 07:05.940 --> 07:08.760 Das heißt, wenn es möglich ist, für das Orakel uns etwas 07:08.760 --> 07:10.160 hinzuschreiben, so dass wir annehmen. 07:13.280 --> 07:16.540 Und das haben wir jetzt natürlich so gemacht, dass wir nur annehmen 07:16.540 --> 07:19.160 könnten, wenn es wirklich eine Ja-Instanz ist. 07:19.220 --> 07:22.280 Wenn keine so eine Tour existiert, dann ist egal, was uns das Orakel 07:22.280 --> 07:26.080 da hinschreibt, wir werden immer ablehnen, was wir ja auch wollen für 07:26.080 --> 07:26.880 eine Nein-Instanz. 07:28.800 --> 07:30.880 So, das ist die Orakeltouring-Maschine. 07:32.340 --> 07:33.440 Fragen dazu? 07:35.740 --> 07:38.320 Dann ein paar Bemerkungen dazu. 07:40.100 --> 07:48.040 Formal kann das Orakel beliebiges Wort aus dem Bandalphabetstern auf 07:48.040 --> 07:48.900 dieses Band schreiben. 07:49.620 --> 07:54.180 Es gibt keine Anforderungen, wie lang das Wort sein soll, wie das 07:54.180 --> 07:56.340 zusammengesetzt sein soll, gar nichts. 07:56.480 --> 08:00.840 Das Orakel darf die Eingabe nicht ändern, das Orakel macht es einfach, 08:02.480 --> 08:03.140 wie es möchte. 08:05.640 --> 08:10.720 In der zweiten Überprüfungsphase wird dann geprüft, ob mit diesem 08:10.720 --> 08:14.220 Orakel, mit diesem Lösungsvorschlag des Orakels, die Instanz wirklich 08:14.220 --> 08:15.260 angenommen werden kann. 08:15.260 --> 08:19.140 Wenn ja, dann gehen wir in den akzeptierenden Endzustand J. 08:19.740 --> 08:23.620 Und wenn nein, wenn das irgendwie mithilfe dieses Dings nicht 08:23.620 --> 08:29.420 akzeptiert wird, dann gehen wir in den ablehnenden Endzustand Qn. 08:31.320 --> 08:36.040 Also, zu einer gegebenen Instanz hat so eine nicht-indemnistische 08:36.040 --> 08:39.500 Touring -Maschine unendlich viele mögliche Berechnungswege. 08:40.200 --> 08:44.820 Ein für jedes Orakel oder für jeden Lösungsvorschlag, das das Orakel 08:44.820 --> 08:45.580 da hinschreiben könnte. 08:46.460 --> 08:51.780 Und wenn mindestens einer von denen akzeptiert, dann sagen wir, die 08:51.780 --> 08:54.440 nicht -indemnistische Touring-Maschine akzeptiert die Eingabe. 08:55.480 --> 08:58.220 Und wenn alle von den unendlich vielen, also egal, was das Orakel 08:58.220 --> 09:01.300 hinschreibt, immer zum Ablehnen führt, dann sagen wir, die nicht 09:01.300 --> 09:04.500 -indemnistische Touring-Maschine akzeptiert die Eingabe nicht. 09:05.380 --> 09:06.740 Nicht in der Sprache der Maschine. 09:09.600 --> 09:11.840 Wir kümmern uns nicht darum, wie das Orakel auf diesen 09:11.840 --> 09:12.740 Lösungsvorschlag kommt. 09:12.980 --> 09:15.680 Wir gehen einfach so wie bei dem nicht-indemnistischen endlichen 09:15.680 --> 09:20.060 Automaten, wir gehen davon aus, dass der Automat das irgendwie weiß, 09:20.260 --> 09:21.420 die richtige Wahl zu treffen. 09:21.920 --> 09:22.620 Ja, Frage. 09:23.420 --> 09:25.380 Ja, also ein bisschen zur Notation. 09:25.500 --> 09:28.540 Die Frage war, was genau Orakel bezeichnet. 09:28.920 --> 09:31.360 Und ich benutze es glaube ich in beiderlei Hinsicht. 09:31.500 --> 09:36.040 Also zum einen ist es das Modul, sozusagen die Obrigkeit, die 09:36.040 --> 09:37.940 entscheidet, welches Wort geschrieben wird. 09:37.940 --> 09:42.900 Aber ich sage auch manchmal zu dem Lösungsvorschlag, was das Orakel da 09:42.900 --> 09:44.760 hinschreibt, sage ich, das ist das Orakel. 09:45.380 --> 09:49.560 Und dann sage ich sowas wie, für jedes Orakel gibt es eine Berechnung. 09:49.780 --> 09:53.940 Aber das ist so ein bisschen ein Graubereich von Notationen. 09:54.840 --> 09:54.860 Ja. 09:56.100 --> 10:00.100 Die unendliche Anzahl möglicher Berechnungen bezieht sich darauf, dass 10:00.100 --> 10:03.800 das Orakel einfach nur ein Wort aus Gamma Stern schreiben kann und 10:03.800 --> 10:05.700 davon gibt es natürlich unendlich viele Möglichkeiten. 10:06.300 --> 10:09.220 Es könnte das leere Wort schreiben, es könnte nur ein Zeichen machen, 10:09.340 --> 10:12.940 es könnte zwei Zeichen, es könnte 27 Zeichen, es könnte beliebig lang, 10:13.060 --> 10:14.760 Hauptsache endlich, da hinschreiben. 10:15.680 --> 10:21.820 Und für jedes Wort, was da hingeschrieben werden könnte, ist die 10:21.820 --> 10:24.560 zweite Stufe dann deterministisch und macht einen eindeutigen 10:24.560 --> 10:24.820 Berechnungsweg. 10:25.700 --> 10:28.640 Aber dadurch, dass es wahrscheinlich ein anderer Berechnungsweg wird, 10:28.820 --> 10:31.480 egal was das Orakel da hinschreibt, könnte es unendlich viele 10:31.480 --> 10:33.860 Berechnungen einer Eingabe geben. 10:34.640 --> 10:35.080 Okay. 10:37.140 --> 10:37.580 Gut. 10:39.020 --> 10:42.920 So, das ist ja jetzt irgendwie ganz schön. 10:43.080 --> 10:45.860 Also im Prinzip ist es so wie bei den endlichen Automaten, bloß dass 10:45.860 --> 10:48.640 wir den Nicht-Determinismus und den Determinismus irgendwie komplett 10:48.640 --> 10:49.220 getrennt haben. 10:49.320 --> 10:52.160 Wir haben sozusagen alle nicht-deterministischen Entscheidungen gleich 10:52.160 --> 10:57.100 an den Anfang getan und dann nur noch deterministisch abzuarbeiten. 10:58.340 --> 11:02.180 Jetzt haben Sie die Turing-Maschinen beim letzten Mal mit ihrer 11:02.180 --> 11:06.580 Zeitkomplexitätsfunktion, was sozusagen Laufzeit von Algorithmen 11:06.580 --> 11:10.040 entspricht, kennengelernt und das wollen wir jetzt auch für die nicht 11:10.040 --> 11:11.280 -deterministischen Turing-Maschinen. 11:12.500 --> 11:17.920 Also was heißt es denn, die Laufzeit einer nicht-deterministischen 11:17.920 --> 11:19.420 Turing -Maschine anzugeben? 11:19.420 --> 11:19.860 Okay. 11:20.700 --> 11:27.560 Also, wenn wir ein Wort X aus der Sprache der Turing-Maschine M haben, 11:27.920 --> 11:32.440 das heißt, das ist ein Wort, was akzeptiert wird von der Turing 11:32.440 --> 11:32.860 -Maschine. 11:33.080 --> 11:36.560 Das heißt, das ist ein Wort, für das es einen Lösungsvorschlag gibt, 11:37.040 --> 11:40.840 sodass in der zweiten Stufe es zum Akzeptieren führt. 11:42.320 --> 11:49.100 Dann ist die Zeit für dieses Wort, um es zu akzeptieren, die minimale 11:49.100 --> 11:53.040 Anzahl an Schritten, die zum akzeptierenden Endzustand führt. 11:53.300 --> 11:57.520 Es könnte ja sein, dass es mehrere Lösungsvorschläge gibt, die 11:57.520 --> 11:59.360 letztendlich zum Akzeptieren führen. 11:59.780 --> 12:02.720 Wir gucken uns sozusagen die kürzeste Möglichkeit an. 12:03.240 --> 12:05.360 Wie schnell kann ich das Wort akzeptieren? 12:07.940 --> 12:14.380 Wir sagen, die Schritte, die das Orakel braucht, um zu schreiben, das 12:14.380 --> 12:16.180 gucken wir uns nicht an. 12:16.740 --> 12:19.220 Das geht nur um die zweite Stufe, um den deterministischen Teil. 12:19.300 --> 12:21.060 Wie viele Schritte in der zweiten Stufe passieren. 12:22.640 --> 12:26.020 Das ist also die Zeit, die benötigt wird, um ein Wort zu akzeptieren. 12:26.620 --> 12:29.060 Und jetzt gucken wir uns die Zeitkomplexitätsfunktion an. 12:29.140 --> 12:32.760 Wir gucken uns wieder an Worte oder Eingaben der Länge n. 12:33.900 --> 12:37.120 Wie lang brauchen wir dort höchstens, um die zu akzeptieren? 12:38.700 --> 12:41.380 Also das ist jetzt eine Funktion, die hängt ab von n. 12:42.020 --> 12:46.480 Und die ist definiert als, gucken Sie sich erst die zweite Klammer an, 12:47.100 --> 12:54.240 das maximale m, sodass ein Wort mit Länge n in m Schritten akzeptiert 12:54.240 --> 12:54.480 wird. 12:56.060 --> 13:00.780 Also die kürzeste Möglichkeit, x zu akzeptieren, ist m Schritte und 13:00.780 --> 13:01.600 davon das Maximum. 13:02.700 --> 13:06.780 Und diese 1 hier vorne ist einfach nur dafür da, dass falls es 13:06.780 --> 13:12.440 überhaupt kein akzeptierendes Wort in der Sprache mit genau dieser 13:12.440 --> 13:16.480 Länge n gibt, dann haben wir hier hinten irgendwie eine leere Menge 13:16.480 --> 13:19.160 und theoretisch wäre das Maximum von einer leeren Menge irgendwie 13:19.160 --> 13:20.900 minusunendlich und das ist irgendwie doof. 13:21.440 --> 13:22.640 Deswegen schreiben wir da einfach 1 hin. 13:25.380 --> 13:26.340 Nichts komisches. 13:27.800 --> 13:31.980 Okay, also das ist nochmal zur Berechnung. 13:31.980 --> 13:34.820 Wenn wir diese Funktion haben, dann zur Berechnung. 13:35.600 --> 13:39.460 Akzeptieren einer Eingabe der Länge n, brauchen wir höchstens tm von n 13:39.460 --> 13:40.040 Schritte. 13:40.980 --> 13:45.340 Über die Sachen, die nicht angenommen werden, sagen wir gar nichts. 13:47.280 --> 13:50.540 Und das ist also eine Worst-Case-Abschätzung, weil wir uns für jede 13:50.540 --> 13:53.720 feste Eingabe gucken wir uns die kürzeste akzeptierende Berechnung an, 13:53.780 --> 13:57.580 wenn es eine Ja-Instanz ist und dann unter all denen gucken wir uns 13:57.580 --> 13:59.520 die schlimmste an mit der gegebenen Länge. 14:00.700 --> 14:05.140 Und diese hängt jetzt nur von der zweiten Teil ab, das habe ich schon 14:05.140 --> 14:05.460 gesagt. 14:05.620 --> 14:08.340 Die Schritte der Orakel-Phase. 14:08.340 --> 14:12.160 Achso, hier steht auch die Schritte der Orakel-Phase, aber es ändert 14:12.160 --> 14:14.600 nichts an der Zeitkomplexität. 14:15.960 --> 14:19.760 Und diese Zeitkomplexität ist einfach nur eins für den Fall, dass es 14:19.760 --> 14:22.780 gar keine Eingabe der Länge n gibt, die akzeptiert wird. 14:24.160 --> 14:27.540 So, jetzt kommen wir schon zur ersten Hälfte von diesem wichtigsten 14:27.540 --> 14:28.840 Konzept, von dem ich geredet habe. 14:29.520 --> 14:30.740 NP-Vollständigkeit. 14:31.340 --> 14:33.180 Und jetzt klären wir, was NP heißt. 14:35.740 --> 14:40.940 NP, das steht für nicht-deterministisch-polynomial. 14:41.700 --> 14:46.020 Also es geht um nicht-deterministische Turing-Maschinen, deren 14:46.020 --> 14:48.840 Zeitkomplexitätsfunktion polynomial ist. 14:49.840 --> 14:50.260 Okay. 14:51.640 --> 14:57.840 NP formal ist eine Menge von Sprachen oder Entscheidungsproblemen, 14:58.520 --> 15:03.340 sodass eine nicht-deterministische Turing-Maschine existiert zu dieser 15:03.340 --> 15:09.800 Sprache, deren Zeitkomplexitätsfunktion als Funktion von n beschränkt 15:09.800 --> 15:11.220 ist durch ein Polynom in n. 15:11.960 --> 15:12.580 Irgendeins. 15:12.880 --> 15:13.240 Egal. 15:13.400 --> 15:17.600 n², n hoch 17, n hoch 217, ist egal. 15:17.600 --> 15:18.640 Hauptsache polynomial. 15:20.600 --> 15:20.800 Okay. 15:22.140 --> 15:27.740 Also das ist eine Menge von Sprachen oder Entscheidungsproblemen. 15:27.780 --> 15:31.280 Das ist eine Menge von Problemen, die, wenn wir eine nicht 15:31.280 --> 15:34.620 -deterministische Turing-Maschine haben, schnell lösen können. 15:34.720 --> 15:36.880 Polynomial ist für uns immer schnell effizient. 15:38.000 --> 15:43.200 Es heißt insbesondere, dass diese Sprachen entscheidbar sind, weil 15:43.200 --> 15:46.880 eine nicht-deterministische Turing-Maschine existiert, die die Sprache 15:46.880 --> 15:47.360 entscheidet. 15:47.600 --> 15:50.940 Sie hat zusätzlich noch eine geringe Laufzeitfunktion, aber 15:50.940 --> 15:52.600 insbesondere sind die entscheidbar. 15:54.840 --> 16:01.300 Und informell, wenn wir gerade über Entscheidungsprobleme reden, sagen 16:01.300 --> 16:08.320 wir, ein Entscheidungsproblem liegt in np, wenn Lösungen schnell 16:08.320 --> 16:09.900 verifiziert werden können. 16:12.160 --> 16:17.680 Es geht nur darum, wenn uns jemand die Lösung verrät, so wie die 16:17.680 --> 16:21.040 Reihenfolge der Städte bei dem TSB-Problem, dann geht es nur noch 16:21.040 --> 16:23.860 darum, nicht die Reihenfolge zu finden, sondern nur noch zu gucken, ob 16:23.860 --> 16:25.960 die Reihenfolge wirklich die gute Reihenfolge ist. 16:27.060 --> 16:29.060 Und das muss in polynomialer Zeit laufen. 16:30.520 --> 16:32.700 Also es geht darum, Lösungen zu verifizieren. 16:34.840 --> 16:36.600 Warum ist das eine Ja-Instanz? 16:36.600 --> 16:40.560 Es gibt einen Tipp, woher der auch immer kommt, sodass ich dann 16:40.560 --> 16:43.860 schnell überprüfen kann, ja, mit dem Tipp sehe ich sofort, das ist 16:43.860 --> 16:44.420 eine Ja-Instanz. 16:44.560 --> 16:46.920 Sofort meint polynomial mit einer Turing-Maschine. 16:48.140 --> 16:48.320 Okay. 16:50.740 --> 16:53.080 Machen wir nochmal ein Beispiel für TSP. 16:53.720 --> 17:01.520 Also TSP, Travelling Salesman Problem, ist ein Problem in np, denn es 17:01.520 --> 17:04.020 gibt eine nicht deterministische Turing-Maschine, die das Problem 17:04.020 --> 17:07.620 entscheidet und deren Laufzeitkomplexitätsfunktion polynomial 17:07.620 --> 17:08.580 beschränkt ist. 17:08.980 --> 17:11.780 Nämlich, wir haben das schon, die Turing-Maschine haben wir schon 17:11.780 --> 17:14.960 besprochen, von einem gegebenen Graphen, einer gegebenen 17:14.960 --> 17:21.140 Kostenfunktion, gegebener Länge k, die erlaubt ist, machen wir die 17:21.140 --> 17:25.900 Endlichkontrolle so, dass wir das Orakel überprüfen, ob es eine 17:25.900 --> 17:31.440 richtige Tour ist, also wirklich durch den richtigen Graphen und die 17:31.440 --> 17:33.020 richtige Länge ist. 17:33.680 --> 17:34.760 Höchstens k ist. 17:35.300 --> 17:38.940 Also, wenn das Orakel uns erstmal hingeschrieben hat, x1 bis xn, 17:42.660 --> 17:49.120 dann überprüfen wir, ob unten die zwei Zeilen, ob aufeinanderfolgende 17:49.120 --> 17:53.640 Knoten xi, xi plus 1 wirklich durch eine Kante verbunden sind und ob, 17:53.760 --> 17:56.880 wenn wir aufsummieren, die ganzen Kostenwerte von diesen Kanten, ob 17:56.880 --> 17:57.880 das höchstens k ist. 17:58.380 --> 18:00.280 Und das kann man einfach tun. 18:01.140 --> 18:08.660 Das ist effizient machbar in O von fast linear, also O von Anzahl 18:08.660 --> 18:13.020 Knoten von dem Graphen mal Logarithmus von der Größenvorkommenden 18:13.020 --> 18:13.280 Zahl. 18:13.900 --> 18:16.640 Also, das ist linear in der Eingabegröße. 18:18.600 --> 18:20.120 Okay, insbesondere also Ponyomiel. 18:21.860 --> 18:22.660 Gut. 18:24.360 --> 18:24.980 So. 18:25.820 --> 18:31.660 Jetzt gibt es hier unten in rot die Klasse np, gerade für nicht 18:31.660 --> 18:34.000 -deterministisch -ponyomial, das ist einfach nochmal genau das 18:34.000 --> 18:34.400 gleiche. 18:34.760 --> 18:38.720 Und jetzt gibt es dazu eine korrespondierende Klasse, die einfach 18:38.720 --> 18:41.320 statt nicht-deterministisch, deterministisch tut. 18:42.620 --> 18:42.960 Okay. 18:43.920 --> 18:44.940 Das ist genau das gleiche. 18:45.440 --> 18:49.900 Das ist eine Klasse von Entscheidungsproblemen oder Sprachen, sodass 18:49.900 --> 18:54.220 es jetzt eine deterministische Turingmaschine gibt, die die Sprache 18:54.220 --> 18:57.480 entscheidet oder das Entscheidungsproblem entscheidet und deren 18:57.480 --> 19:00.680 Laufzeit -Komplexitätsfunktion durch ein Polynom beschränkt. 19:01.100 --> 19:04.820 Der Unterschied ist also, wir haben jetzt für die Klasse p kein 19:04.820 --> 19:07.800 Orakel, was uns hilft, sondern wir müssen es ganz alleine mit dem 19:07.800 --> 19:09.420 deterministischen Turingmaschine schaffen. 19:10.400 --> 19:11.580 Quasi genau so ist es. 19:11.660 --> 19:14.840 In der Klasse p müssen wir sozusagen die Lösung selbstständig finden. 19:16.140 --> 19:18.580 Also wenn wir jetzt wissen wollen, wenn wir zum Beispiel jetzt tsp 19:18.580 --> 19:23.960 nehmen und wir haben kein Orakel, dann bleibt uns anschaulich gesehen 19:23.960 --> 19:28.020 nichts anderes übrig, als irgendwie zu suchen, so eine Tour. 19:29.140 --> 19:32.000 Die Frage ist, schaffen wir das in polynomeller Zeit oder nicht. 19:33.320 --> 19:37.560 Okay, also oben die Klasse p in blau, das ist die Menge aller Sprachen 19:37.560 --> 19:39.840 oder Entscheidungsprobleme, für die es eine deterministische 19:39.840 --> 19:44.240 Turingmaschine gibt, die Zeitkomplexitätsfunktionen polynomal 19:44.240 --> 19:44.700 beschränkt. 19:46.160 --> 19:50.900 Also bei einer eingegebenen Instanz i von einem Entscheidungsproblem 19:50.900 --> 19:58.620 p, können wir eine Lösung, also ob eine Lösung existiert, ob es eine 19:58.620 --> 20:01.700 Ja -Instanz ist, können wir in polynomeller Zeit berechnen. 20:02.520 --> 20:05.780 Und bei np ist im Prinzip das gleiche, bloß dass wir die Lösung nicht 20:05.780 --> 20:10.780 berechnen müssen, sondern die Korrektheit einer Lösung muss nur 20:10.780 --> 20:11.720 überprüft werden können. 20:14.640 --> 20:20.240 Gut, das heißt, es ist so ein bisschen die Frage, ob deterministisch 20:20.240 --> 20:24.540 und nicht deterministisch so das gleiche können, aber Sie müssen hier 20:24.540 --> 20:26.700 aufpassen, es geht wirklich um die Laufzeit. 20:27.640 --> 20:33.280 Die Frage ist, kann ich, wenn ich nicht deterministisch in polynomaler 20:33.280 --> 20:36.520 Laufzeit das hinkriege, kann ich den Nicht-Determinismus loswerden, 20:36.660 --> 20:38.480 ohne die Laufzeit explodieren zu lassen. 20:39.340 --> 20:40.300 Immer noch polynomial. 20:41.060 --> 20:43.760 Das ist die große Frage, wahrscheinlich die größte Frage der 20:43.760 --> 20:45.060 theoretischen Informatik. 20:46.060 --> 20:48.200 Ist da tatsächlich ein Unterschied? 20:48.680 --> 20:49.720 Ist p gleich np? 20:51.100 --> 20:52.140 Die ist offen. 20:52.540 --> 20:53.420 Das wissen wir nicht. 20:53.620 --> 20:57.320 Wir wissen nicht, ob, sobald Lösungen einfach verifiziert werden 20:57.320 --> 21:00.600 können, automatisch Lösungen auch einfach gefunden werden. 21:01.320 --> 21:04.080 Also, das ist die größte Frage der theoretischen Informatik. 21:04.680 --> 21:05.620 Was wissen wir? 21:05.740 --> 21:09.800 Na ja, trivialerweise ist alles in p auch in np. 21:10.220 --> 21:13.000 Das ist einfach, wenn wir eine deterministische Turing-Maschine haben, 21:13.580 --> 21:16.040 können wir auch einfach das Orakel ignorieren. 21:17.920 --> 21:19.940 Die Frage ist, ob Gleichheit gilt. 21:20.020 --> 21:21.500 Die Vermutung ist eher nein. 21:24.160 --> 21:27.880 Leute arbeiten, man arbeitet eigentlich auch damit, dass die Antwort 21:27.880 --> 21:29.060 wahrscheinlich nein ist. 21:29.560 --> 21:35.360 Dass es Sachen gibt, Probleme gibt, die leicht verifiziert werden 21:35.360 --> 21:37.340 können, aber nicht leicht berechnet werden. 21:39.120 --> 21:44.080 Aber theoretisch wäre es noch möglich, dass Gleichheit gilt. 21:46.520 --> 21:50.360 Viele Sachen in unserer täglichen Welt basieren darauf, dass die 21:50.360 --> 21:53.660 Antwort hier wahrscheinlich nein ist, weil z.B. 21:56.020 --> 22:01.780 Codierung oder Verschlüsselung von Daten beruht zum Teil ein bisschen 22:01.780 --> 22:05.820 darauf, dass Sachen nicht leicht geknackt werden können, aber wenn ich 22:05.820 --> 22:08.820 denen einen Schlüssel gebe, kann man leicht aufschließen. 22:08.820 --> 22:13.120 Und wenn sich herausstellen würde, dass die beiden gleich sind, dann 22:13.120 --> 22:16.480 ist die Herstellung des Schlüssels genauso einfach, wie den Schlüssel 22:16.480 --> 22:17.980 zu verwenden. 22:18.600 --> 22:20.660 Das wäre in dem Sinne schlecht. 22:24.080 --> 22:29.700 Aber wie wollen wir jetzt zeigen, dass das eventuell nicht gleich ist? 22:30.020 --> 22:32.920 Dann müssten wir also zeigen, dass es etwas gibt, was in NP hier 22:32.920 --> 22:35.220 hinten liegt, aber nicht vorne in P liegt. 22:35.860 --> 22:39.160 Das heißt, es muss ein Problem sein, das ist irgendwie schwierig zu 22:39.160 --> 22:41.700 berechnen, obwohl es einfach zu verifizieren ist. 22:42.900 --> 22:48.980 Und dafür gucken wir uns sozusagen die schwersten Probleme in NP an. 22:49.320 --> 22:54.560 Und zwar die schwersten in NP heißt, die sind so schwierig wie alle 22:54.560 --> 22:56.140 anderen Probleme in NP. 22:57.600 --> 23:00.480 Und das ist der Begriff der NP-Vollständigkeit. 23:01.560 --> 23:04.280 Man kann sich darüber streiten, ob vollständig da das richtige Wort 23:04.280 --> 23:09.200 ist, aber NP-Vollständig heißt, das ist in NP und es ist so schwer wie 23:09.200 --> 23:10.260 alle anderen in NP. 23:10.700 --> 23:12.380 Das ist sozusagen... 23:12.380 --> 23:13.000 Ja, weiß ich nicht. 23:13.440 --> 23:15.840 Mir fällt auch nichts Besseres ein, aber das heißt halt NP 23:15.840 --> 23:16.460 -Vollständigkeit. 23:19.500 --> 23:20.960 Und was soll das heißen? 23:21.020 --> 23:23.480 Das ist so schwer wie alle anderen Probleme in NP. 23:24.720 --> 23:30.420 Das heißt insbesondere, entweder die sind so schwer, dass wir zeigen 23:30.420 --> 23:33.240 können, es gibt keine deterministische Turing-Maschine in Pudding 23:33.240 --> 23:34.900 -Merler -Zeit, dann sind wir fertig, 23:38.660 --> 23:43.780 oder für ein so schwerstes Problem finden wir dann doch eine 23:43.780 --> 23:46.680 deterministische Turing-Maschine in Pudding-Merler-Zeit. 23:46.860 --> 23:50.920 Okay, dann liegt das Problem schon mal in P, aber weil es am 23:50.920 --> 23:55.840 schwersten war, liegen alle von NP in P, dann hätten wir Gleichheit 23:55.840 --> 23:56.220 gezeigt. 23:58.680 --> 24:01.920 Also, was heißt es jetzt am schwersten? 24:01.940 --> 24:05.500 Wir müssen jetzt Probleme miteinander vergleichen und da gibt es jetzt 24:05.500 --> 24:07.420 dieses Konzept der polynomialen Transformation. 24:08.480 --> 24:11.860 Das ist eine Möglichkeit, Probleme miteinander zu vergleichen und zu 24:11.860 --> 24:15.000 sagen, das ist schwieriger oder mindestens so schwierig wie das. 24:16.680 --> 24:20.480 Gut, machen wir das zuerst für Sprachen und danach gleich nochmal für 24:20.480 --> 24:21.480 Entscheidungsprobleme. 24:21.540 --> 24:24.120 Also eine Sprache L1 und eine Sprache L2. 24:24.700 --> 24:26.380 Und was wir zeigen wollen, ist das hier. 24:26.720 --> 24:34.320 L1 ist polynomial transformierbar in L2. 24:34.840 --> 24:39.100 Und die Bedeutung ist, L2 ist mindestens so schwer wie L1. 24:39.220 --> 24:41.360 Sehen Sie das als ein kleiner Gleichzeichen. 24:42.400 --> 24:45.920 Also das, was hier auf der rechten Seite steht, ist das schwierigere 24:45.920 --> 24:49.540 oder nicht einfachere Problem oder Sprache. 24:50.280 --> 24:51.200 Gut, was heißt es jetzt? 24:51.240 --> 24:53.480 Wie kriege ich so eine Ungleichung hier hin zwischen den 24:53.480 --> 24:55.100 Schwierigkeitsgraden? 24:56.200 --> 24:59.500 Wir brauchen eine Transformation. 24:59.760 --> 25:05.620 Und zwar, wir transformieren die erste Sprache auf die zweite Sprache. 25:06.780 --> 25:12.680 Die Idee ist, ich möchte die zweite... 25:13.200 --> 25:14.840 Ja, doch, ist alles richtig. 25:15.020 --> 25:15.380 Entschuldigung. 25:16.240 --> 25:24.420 Ich möchte die erste Sprache lösen, indem ich einen Löser für die 25:24.420 --> 25:25.760 zweite Sprache benutze. 25:27.860 --> 25:28.340 Okay. 25:29.460 --> 25:34.720 Das heißt mir, also der Löser für die zweite Sprache ist stärker als 25:34.720 --> 25:38.460 der Löser für die erste Sprache, weil ich mit dem ja auch die erste 25:38.460 --> 25:39.720 Sprache dann lösen kann. 25:40.520 --> 25:43.940 Das heißt also insbesondere, einen Löser für die zweite Sprache zu 25:43.940 --> 25:44.920 finden, ist schwieriger. 25:45.340 --> 25:47.500 Die zweite Sprache ist ein schwierigeres Problem. 25:48.780 --> 25:51.580 Okay, das ist so die High-Level-Idee. 25:52.060 --> 25:56.620 Konkret heißt es, wir brauchen eine Funktion von Sigma-1-Stern nach 25:56.620 --> 26:03.440 Sigma -2-Stern, die also Instanzen oder Eingaben für die erste Sprache 26:03.440 --> 26:05.740 übersetzt in Eingaben in die zweite Sprache. 26:06.420 --> 26:10.140 Diese Übersetzung sollte jetzt nicht schwierig sein, die sollte 26:10.140 --> 26:13.580 polynomial -deterministisch von der Turing-Maschine gemacht werden. 26:15.460 --> 26:22.040 Und wenn das X aus Sigma-1-Stern in der Sprache L1 liegt, dann soll 26:22.040 --> 26:29.340 auch die abgeblendete Instanz in L2 liegen und umgekehrt. 26:29.440 --> 26:30.340 Das heißt, ich möchte... 26:32.220 --> 26:36.440 Stellen Sie sich vor, ich weiß noch nicht, ob X in L1 liegt, ich weiß 26:36.440 --> 26:37.460 nicht, wie ich das lösen kann. 26:38.460 --> 26:43.500 Die Idee ist, transformiere die Instanz X in eine Instanz f von X 26:44.220 --> 26:47.080 durch polynomial-deterministisch, das heißt wir sind theoretisch noch 26:47.080 --> 26:53.760 in dem Bereich p eventuell zu sein, löse dann, ob f von X in L2 ist, 26:54.600 --> 26:57.380 mit der Turing-Maschine für L2. 26:58.780 --> 27:04.160 Und wenn wir das hier gewährleisten, diese Äquivalenz, dann ist also f 27:04.160 --> 27:07.960 von X in L2 genau dann, wenn die ursprüngliche Instanz in L1 war. 27:08.680 --> 27:12.940 Das heißt, es reicht für uns zu gucken, ob wir L2 mit einer 27:12.940 --> 27:15.840 deterministischen polynomialen Turing-Maschine lösen. 27:16.960 --> 27:20.500 Also wenn jemand mal kommt und sagt, hier für L2 habe ich eine 27:20.500 --> 27:23.000 deterministische polynomiale Turing-Maschine, dann haben Sie 27:23.000 --> 27:26.840 automatisch eine deterministische polynomiale Turing-Maschine für L1. 27:28.240 --> 27:32.080 Sie beginnen mit L1, also mit einer Instanz von L1, stecken das in die 27:32.080 --> 27:35.660 Transformation, jetzt haben Sie eine Instanz von L2, benutzen diese 27:35.660 --> 27:40.040 Turing -Maschine für L2 und dadurch, dass beide Schritte, dieses 27:40.040 --> 27:43.360 Transformieren und die zweite Turing-Maschine, beide deterministisch 27:43.360 --> 27:46.360 und polynomial waren, ist das ganze Ding deterministisch und 27:46.360 --> 27:46.660 polynomial. 27:47.300 --> 27:49.700 Und das muss jetzt natürlich korrekt sein, das heißt, es darf nur 27:49.700 --> 27:55.080 annehmen, wenn das vorne wirklich in der Sprache war, also wenn die 27:55.080 --> 27:58.720 zweite Turing-Maschine Ja sagt, dann soll das auch wirklich in der 27:58.720 --> 28:02.440 Sprache gewesen sein und wenn die zweite Turing-Maschine Nein sagt, 28:02.620 --> 28:04.260 dann soll das auch in der Sprache gewesen sein. 28:05.700 --> 28:05.800 Okay. 28:06.740 --> 28:08.480 So, das ist polynomial transformieren. 28:10.980 --> 28:16.100 Wir transformieren auf das schwierigere Problem und sagen, wenn ich 28:16.100 --> 28:19.460 das schwierigere Problem lösen kann, kann ich mein Ursprungsproblem 28:19.460 --> 28:20.000 auch lösen. 28:20.860 --> 28:25.060 Jetzt heißt eine Sprache NP vollständig, am schwierigsten in der 28:25.060 --> 28:32.360 Klasse NP, wenn die Sprache erstmal in NP liegt und alle anderen 28:32.360 --> 28:37.740 Sprachen in NP polynomial transformiert werden können auf L. 28:40.120 --> 28:44.380 Also das ist mindestens so schwierig wie alle anderen Sprachen in NP. 28:46.780 --> 28:50.820 Das ist ja wohl ein gutes Konzept von am schwierigsten. 28:53.160 --> 28:54.820 Unklar, ob es sowas geben kann. 28:55.880 --> 28:56.620 Mehrere davon. 28:58.380 --> 28:58.900 Das ist es. 29:00.020 --> 29:02.080 So, jetzt machen wir das vielleicht nochmal ein bisschen für 29:02.080 --> 29:02.740 Entscheidungsprobleme. 29:05.200 --> 29:08.220 Für Entscheidungsprobleme und nicht für formale Sprachen wollen wir 29:08.220 --> 29:12.100 also Instanzen von dem ersten in Instanzen von dem zweiten abbilden. 29:12.280 --> 29:15.700 Also zum Beispiel Traveling Salesman Instanz auf irgendwas anderes. 29:17.040 --> 29:21.320 Das soll dataministisch und polynomial passieren und Ja-Instanzen von 29:21.320 --> 29:24.320 dem ersten Problem sollen auf Ja-Instanzen von dem zweiten Problem und 29:24.320 --> 29:27.940 Nein -Instanzen von dem ersten Problem sollen auf Nein-Instanzen von 29:27.940 --> 29:29.860 dem zweiten Problem angewendet werden. 29:30.200 --> 29:33.600 Und dann sagen wir, dass Problem P1 polynomial transformierbar in 29:33.600 --> 29:38.040 Problem P2 ist und ein Entscheidungsproblem heißt NP vollständig, wenn 29:38.040 --> 29:39.040 es in NP liegt. 29:40.020 --> 29:45.500 Man kann polynomial verifizieren und alle Entscheidungsprobleme in NP 29:45.500 --> 29:49.360 können polynomial transformiert werden auf unser Entscheidungsproblem. 29:52.220 --> 29:53.480 So, ein kleines Lemma. 29:55.400 --> 30:00.960 Wenn dieses mindestens so schwierig wie ist transitiv, also das heißt, 30:01.100 --> 30:06.040 wenn L1 also wenn L2 mindestens so schwierig ist wie L1 und L3 30:06.040 --> 30:10.240 mindestens so schwierig ist wie L2 dann ist auch L3 mindestens so 30:10.240 --> 30:13.220 schwierig wie L1 weil wir einfach diese Transformationen 30:13.860 --> 30:14.960 hintereinander stecken können. 30:16.320 --> 30:25.840 Wenn wir schon wissen, dass L1 NP vollständig ist alles kann schon auf 30:25.840 --> 30:30.400 L1 reduziert werden oder transformiert werden und ich jetzt L1 30:30.400 --> 30:38.200 transformieren kann auf L2 dann ist auch L2 mindestens so schwierig 30:38.200 --> 30:39.400 wie alles andere in NP. 30:39.800 --> 30:44.140 Das heißt, wenn L1 schon NP vollständig ist und ich reduziere von dem 30:44.140 --> 30:47.700 NP vollständigen auf ein unbekanntes Problem auf ein neues Problem 30:48.500 --> 30:51.180 dann ist auch das neue Problem NP vollständig. 30:51.280 --> 30:55.820 Also, um zu zeigen und das ist das, was wir jetzt ganz viel tun werden 30:55.820 --> 31:02.080 wir wollen wissen wann ist ein Problem effizient berechenbar also in P 31:02.080 --> 31:04.720 wann gibt es eine deterministische Turingmaschine die das in 31:04.720 --> 31:10.160 polynomialer Zeit tut und wann eventuell nicht und eventuell nicht 31:10.160 --> 31:13.800 heißt für uns NP vollständig das ist so schwer wenn wir das lösen 31:13.800 --> 31:16.080 könnten mit einer deterministischen Turingmaschine dann würden wir P 31:16.080 --> 31:17.100 gleich NP zeigen. 31:19.060 --> 31:21.960 Das heißt, um zu zeigen, dass ein Problem schwer ist und wir 31:21.960 --> 31:25.680 wahrscheinlich nicht diese deterministische Turingmaschine finden 31:25.680 --> 31:29.980 gehen wir wie folgt vor wir müssen erstmal zeigen das Problem liegt in 31:29.980 --> 31:33.120 NP das heißt, wir müssen eine nicht deterministische Turingmaschine 31:33.120 --> 31:38.760 finden und zweitens für ein bekanntes NP vollständiges Problem wir 31:38.760 --> 31:41.020 haben dann immer so einen Werkzeugkasten von NP vollständigen 31:41.020 --> 31:44.680 Problemen, die wir schon kennen wählen wir uns ein geeignetes aus und 31:44.680 --> 31:50.120 transformieren das auf unser neues Problem ja warum mehrere Probleme 31:50.120 --> 31:53.260 NP vollständig sein können und warum es nicht sozusagen eine Spitze 31:53.260 --> 31:58.220 vom Eisberg gibt mit einem aller schwierigsten Problem ja das liegt an 31:58.220 --> 32:02.720 diesem an dem Begriff Schwierigkeit Sie müssen das ein bisschen so 32:02.720 --> 32:06.660 sehen wie mindestens so schwierig wie es kann sein, dass Probleme 32:07.220 --> 32:11.740 gegenseitig aufeinander transformiert werden können also sehen sie es 32:11.740 --> 32:15.600 als kleiner gleich und nicht als echt kleiner und tatsächlich ist es 32:15.600 --> 32:18.720 so, dass alle NP vollständigen Probleme wir werden eine ganze Menge 32:18.720 --> 32:21.620 davon kennenlernen die sind alle gegenseitig aufeinander 32:21.620 --> 32:26.480 transformierbar die sind alle gleich schwer das alte Problem dass sie 32:26.480 --> 32:29.320 also ein neues Problem haben und sie haben ein altes NP vollständiges 32:29.320 --> 32:33.440 Problem auf das neue reduziert transformiert zeigen damit ihr neues 32:33.440 --> 32:37.500 Problem ist mindestens so schwierig also NP vollständig das alte 32:37.500 --> 32:44.320 bleibt immer noch NP vollständig sie werden ähm sie wissen ja schon 32:44.320 --> 32:47.680 von dem alten Problem dass alle Probleme in NP darauf transformierbar 32:47.680 --> 32:53.380 sind das heißt diese Rückrichtung haben sie quasi schon gezeigt wir 32:53.380 --> 32:59.180 werden heute tatsächlich diese fast unmögliche Aufgabe machen, dass 32:59.180 --> 33:04.120 wir alle Probleme in NP auf ein spezielles Problem reduzieren werden. 33:05.060 --> 33:10.440 So, also das ist wirklich der Weg, den Sie sich einprägen müssen, wenn 33:10.440 --> 33:13.320 Sie zeigen sollen, zeigen Sie, dass dieses Problem NP-vollständig ist. 33:13.340 --> 33:14.120 Immer zwei Schritte. 33:14.520 --> 33:17.400 Erster Schritt in NP, das ist üblicherweise einfach. 33:17.540 --> 33:22.120 Sie müssen nur sagen, wie gebe ich einen geeigneten Tipp und wie 33:22.120 --> 33:24.860 verifiziere ich den in Polynomialzeit. 33:25.260 --> 33:28.420 Das ist üblicherweise leicht, so wie mit der Traveling Salesman-Dings. 33:29.960 --> 33:33.460 Zweiter Schritt, nicht ganz so einfach, transformieren. 33:34.520 --> 33:38.880 Sie müssen Probleme ineinander, also ein geeignetes NP-vollständiges 33:38.880 --> 33:41.840 Problem finden und das auf ihr neues Problem transformieren. 33:42.380 --> 33:44.340 Da brauchen Sie einfach Erfahrung. 33:44.460 --> 33:47.360 Sie müssen das oft gesehen haben und oft gemacht haben, um ein Gefühl 33:47.360 --> 33:48.960 dafür zu kriegen, wie man sowas tut. 33:49.380 --> 33:51.740 Das ist wie entwerfen von Algorithmen. 33:56.020 --> 34:00.200 Diese ganze Methode funktioniert natürlich erst, wenn wir ein erstes 34:00.200 --> 34:04.840 NP -vollständiges Problem haben, was wir im Moment noch nicht haben. 34:05.720 --> 34:10.000 Das heißt, um ein erstes NP-vollständiges Problem zu machen, müssen 34:10.000 --> 34:15.180 wir alle Probleme in NP auf dieses Problem reduzieren und das ist das, 34:15.260 --> 34:17.560 was wir jetzt für den Rest der Vorlesung tun werden. 34:17.560 --> 34:22.020 Und dieses erste NP-vollständige Problem kann man auch wirklich sehen 34:22.020 --> 34:26.840 als das wichtigste NP-vollständige Problem und das ist das sogenannte 34:26.840 --> 34:29.800 Satisfiability Problem oder, wenn man es übersetzen möchte, 34:31.180 --> 34:31.760 Erfüllbarkeitsproblem. 34:32.220 --> 34:32.800 Sat. 34:33.160 --> 34:33.900 S -A-T. 34:34.680 --> 34:37.280 Also das ist ein Problem, das werden wir zeigen. 34:37.900 --> 34:41.220 Das ist mindestens so schwer wie alle Probleme in NP. 34:41.760 --> 34:43.020 Ein sehr schwieriges Problem. 34:45.340 --> 34:46.360 Es sieht wie folgt aus. 34:46.400 --> 34:47.600 Wie sieht eine Instanz aus? 34:47.820 --> 34:52.080 Eine Instanz ist eine Menge U von burschen Variablen. 34:52.220 --> 34:53.880 Das heißt, sie können entweder wahr oder falsch sein. 34:56.760 --> 35:02.440 Dann betrachten wir diese UIs entweder positiv oder negiert mit so 35:02.440 --> 35:05.860 einem Strich drüber und das heißt dann Literale. 35:06.920 --> 35:10.940 Also es gibt positive Literale und negative oder negierte Literale. 35:12.200 --> 35:16.460 Eine Wahrheitsbelegung ist einfach eine Funktion, die festlegt für 35:16.460 --> 35:19.800 jede Variable, ob sie jetzt wahr oder falsch ist. 35:20.800 --> 35:23.980 Und dann ist halt, wenn eine Variable wahr ist, dann ist ihr positives 35:23.980 --> 35:27.540 Literal wahr und ihr negiertes Literal ist dann entsprechend falsch. 35:27.720 --> 35:31.720 Wenn eine Variable auf falsch gesetzt ist, ist ihr positives Literal 35:31.720 --> 35:34.400 falsch und ihr negiertes Literal dadurch wahr. 35:36.340 --> 35:39.600 Also wirklich das Logische nicht macht diese Negierung. 35:41.440 --> 35:48.360 Und jetzt interessieren wir uns für Ausdrücke oder Veroderungen von 35:48.360 --> 35:51.440 solchen Sachen, von solchen Literalen. 35:51.960 --> 35:58.040 Also Y1 oder Y2 oder Y3 oder bis irgendwie Ys. 35:58.360 --> 35:59.620 Das ist so eine Veroderung 36:03.020 --> 36:03.900 von Literalen. 36:04.360 --> 36:09.840 Das heißt wir wollen, dass mindestens eins dieser Literale als wahr 36:09.840 --> 36:11.420 herauskommt. 36:11.600 --> 36:14.700 Also entweder ist es eine positive Variable und die ist auf wahr 36:14.700 --> 36:17.620 gesetzt oder es ist eine negierte Variable und die ist auf falsch 36:17.620 --> 36:18.300 gesetzt. 36:19.100 --> 36:20.380 Mindestens eins von denen. 36:20.580 --> 36:23.840 Es muss, wenn es ein Oder ist, reicht eine, meinetwegen alle, 36:23.840 --> 36:26.020 mindestens eins. 36:27.320 --> 36:30.560 So eine Veroderung von Literalen nennen wir eine Klausel. 36:32.040 --> 36:34.940 Wir sagen, wenn mindestens eins davon auf wahr gesetzt ist und dann 36:34.940 --> 36:37.180 eine Wahrheitsbelegung, dann ist diese Klausel erfüllt. 36:39.760 --> 36:42.520 Wenn alle davon falsch sind, also es gibt wirklich nur eine 36:42.520 --> 36:46.600 Kombination, die die Klausel nicht erfüllt, dann sagen wir die Klausel 36:46.600 --> 36:47.340 ist halt nicht erfüllt. 36:50.500 --> 36:54.440 Und jetzt wollen wir, wir haben aber nicht nur eine Klausel, sondern 36:54.440 --> 37:02.000 wir haben mehrere Klauseln, nämlich hier eine Menge C von Klauseln und 37:02.000 --> 37:06.860 die Frage ist, können wir die alle gleichzeitig erfüllen mit derselben 37:06.860 --> 37:07.560 Wahrheitsbelegung. 37:07.640 --> 37:11.260 Gibt es eine Wahrheitsbelegung, die jede einzelne Klausel in unserer 37:11.260 --> 37:11.920 Menge erfüllt. 37:14.280 --> 37:16.060 Hier unten ist ein Mini-Beispiel. 37:16.240 --> 37:20.100 Wir haben zwei Variablen u1, u2 und wir haben zwei Klauseln. 37:20.180 --> 37:23.560 Die erste Klausel ist u1 oder nicht u2. 37:25.880 --> 37:29.520 Und die zweite Klausel ist nicht u1 oder u2. 37:31.220 --> 37:34.860 Jetzt ist die Frage, kann man u1, u2 so auf wahr oder falsch setzen, 37:35.400 --> 37:38.600 dass beide diese Veroderungen gleichzeitig erfüllt sind. 37:38.600 --> 37:40.240 Und hier ist die Antwort ja. 37:40.640 --> 37:44.060 Zum Beispiel könnten wir u1 und u2 beide auf wahr setzen. 37:45.580 --> 37:48.720 Dann ist die erste Klausel erfüllt, weil sie sich darüber freut, dass 37:48.720 --> 37:52.380 u1 auf wahr gesetzt ist und die zweite Klausel ist erfüllt, weil u2 37:52.380 --> 37:53.280 auf wahr gesetzt ist. 37:56.000 --> 38:01.320 Die andere Wahrheitsbelegung ist, beide auf falsch zu setzen. 38:01.680 --> 38:03.360 Dann würde auch beide Klauseln erfüllen. 38:03.360 --> 38:08.660 Aber beide unterschiedliche Werte zu geben, würde hier nicht beide 38:08.660 --> 38:09.460 Klauseln erfüllen. 38:12.120 --> 38:18.000 Die Frage ist, diese Instanz, diese Menge von Variablen und diese 38:18.000 --> 38:25.540 Menge von Klauseln ist eine Ja-Instanz, wenn es möglich ist, die 38:25.540 --> 38:28.820 Variablen mit Wahrheitswerten zu belegen, sodass alle Klauseln 38:28.820 --> 38:29.820 gleichzeitig erfüllt sind. 38:31.420 --> 38:32.660 Das ist das Problem satt. 38:33.520 --> 38:35.700 Hier nochmal ein Beispiel von einer Ja-Instanz. 38:36.180 --> 38:38.600 Ein bisschen größer, fünf Variablen. 38:39.280 --> 38:39.900 Und was sind das? 38:40.000 --> 38:40.900 Drei Klauseln. 38:41.680 --> 38:43.940 Und das ist ziemlich einfach zu erfüllen. 38:44.040 --> 38:48.900 Zum Beispiel könnte ich c auf wahr setzen und d auf wahr setzen. 38:50.560 --> 38:53.880 Und dann wäre die Klausel hier in der Mitte schon automatisch durch 38:53.880 --> 38:56.900 die d erfüllt und a, b und e sind tatsächlich beliebig. 38:57.700 --> 39:00.560 Und hier unten ist es vielleicht sogar ein bisschen sinnvoller, sich 39:00.560 --> 39:02.120 meine Nein-Instanz anzugucken. 39:02.300 --> 39:04.700 Wir haben drei Variablen und vier Klauseln. 39:05.460 --> 39:09.900 Diese zweite Klausel hier, die hat nur ein Literal und die zwingt mir, 39:10.000 --> 39:12.740 damit sie erfüllt ist, dass a auf falsch gesetzt ist. 39:14.120 --> 39:17.460 Entsprechend die vierte Klausel zwingt mir, dass c auf falsch gesetzt 39:17.460 --> 39:17.740 wird. 39:19.020 --> 39:22.480 Wenn aber c auf falsch gesetzt wird, dann zwingt mir die dritte 39:22.480 --> 39:26.680 Klausel, die kann ich jetzt nicht mehr mit dem c erfüllen, dann muss 39:26.680 --> 39:30.240 ich die mit dem b erfüllen, also ich muss b auf falsch setzen. 39:31.460 --> 39:34.740 Also damit die letzten drei Klauseln erfüllt sind, müssen a, b und c 39:34.740 --> 39:35.640 alle falsch sein. 39:36.160 --> 39:39.540 Dann habe ich aber ein Problem mit der ersten Klausel, wenn es die 39:39.540 --> 39:40.000 nicht erfüllt. 39:41.660 --> 39:43.520 Das heißt, das ist eine Nein-Instanz. 39:43.740 --> 39:47.320 Da ist es unmöglich a, b und c so mit Wahrheitswerten zu belegen, dass 39:47.320 --> 39:48.340 alle Klauseln erfüllt sind. 39:48.820 --> 39:49.920 Das ist ein Satz-Problem. 39:50.920 --> 39:57.000 Und jetzt kommt der Satz und guck, Satz ist NP-vollständig. 39:58.440 --> 40:07.200 Wenn ich polynomiell deterministisch entscheiden könnte, ob diese 40:07.200 --> 40:11.600 Wahrheitsbelegung existiert, könnte ich alle Probleme in NP 40:11.600 --> 40:13.980 -polynomiell deterministisch lösen. 40:17.220 --> 40:21.600 Also, zur Erinnerung, das Problem ist NP-vollständig, wenn es in NP 40:21.600 --> 40:25.620 liegt und alle Probleme aus NP darauf reduziert werden können. 40:26.280 --> 40:27.540 Und das müssen wir jetzt beweisen. 40:29.480 --> 40:31.240 Der erste Teil ist wieder einfach. 40:32.140 --> 40:33.220 Satz liegt in NP. 40:33.400 --> 40:33.620 Warum? 40:33.940 --> 40:36.700 Naja, wir müssen eine nicht-deterministische Turing-Maschine, eine 40:36.700 --> 40:41.140 Orakel -Turing-Maschine, konstruieren, die in polynomieller Zeit eine 40:41.140 --> 40:42.460 Ja -Instanz verifiziert. 40:43.160 --> 40:44.260 Und was machen wir? 40:44.400 --> 40:47.640 Naja, das Orakel soll uns doch bitte einfach vorne aufs Band 40:47.640 --> 40:50.320 hinschreiben, welche Variablen wahr sind und welche falsch. 40:50.320 --> 40:53.900 Einfach die Wahrheitsbelegung geben. 40:55.800 --> 41:00.020 Und wir müssen dann jetzt überprüfen, in der zweiten Stufe, ob das 41:00.020 --> 41:03.500 wirklich eine Wahrheitsbelegung ist oder ob das überhaupt unseren 41:03.500 --> 41:07.240 vereinbarten Anforderungen, Codierung entspricht. 41:07.780 --> 41:11.800 Ob jede Variable wirklich genau einen Wert zugeordnet bekommen hat, 41:11.880 --> 41:12.700 wahr oder falsch. 41:13.360 --> 41:16.900 Und ob mit dieser Wahrheitsbelegung jede Klausel auch wirklich erfüllt 41:16.900 --> 41:17.120 ist. 41:18.000 --> 41:20.860 Und nur wenn das alles stimmt, dann sind wir davon überzeugt, okay, 41:21.000 --> 41:22.900 ja, das war eine Ja-Instanz und wir akzeptieren. 41:24.840 --> 41:27.840 Und das kann relativ einfach gemacht werden, also wenn I eine Instanz 41:27.840 --> 41:30.780 mit N Klauseln und M Variablen ist, und dann kann diese 41:30.780 --> 41:38.260 Wahrheitsbelegung T in M mal N größenordnungsmäßig überprüft werden, 41:38.340 --> 41:40.140 ob T wirklich alle Klauseln erfüllt. 41:42.660 --> 41:45.160 Gut, also das ist der einfache Teil und so einfach ist der 41:45.160 --> 41:45.980 üblicherweise immer. 41:47.860 --> 41:50.700 Jetzt kommt der schwierige Teil, diese Transformation. 41:51.740 --> 41:57.600 Wir müssen beliebiges Problem aus N P transformieren auf das SAT 41:57.600 --> 41:58.900 Problem. 42:02.280 --> 42:07.140 Und wir machen das, indem wir jetzt wieder Probleme für diesen Beweis, 42:07.340 --> 42:09.880 gucken wir uns das wieder als formale Sprachen an. 42:10.480 --> 42:13.260 Später, wenn sie Reduktionen machen, dann sind diese Probleme immer 42:13.260 --> 42:15.800 Entscheidungsprobleme und sie hantieren dann mit Graphen, die 42:15.800 --> 42:19.600 aufeinander abgebildet werden und nicht so viel mit Zeichen und so 42:19.600 --> 42:19.840 weiter. 42:20.160 --> 42:22.960 Aber für diesen einen Beweis, dann müssen wir wirklich über formale 42:22.960 --> 42:23.640 Sprachen reden. 42:24.360 --> 42:31.160 Das heißt, L SAT sei einfach ein geeignetes Codierungsschema für 42:31.160 --> 42:32.540 dieses Entscheidungsproblem. 42:33.840 --> 42:37.220 Also wie auch immer Sie die Klauseln und Variablen da codieren wollen, 42:37.400 --> 42:37.920 irgendwie. 42:40.280 --> 42:45.600 Und L ist jetzt auch eine formale Sprache in N P, für die es eine 42:45.600 --> 42:48.120 nicht -deterministische Turing-Maschine gibt, die diese Sprache 42:48.120 --> 42:50.160 entscheidet. 42:51.240 --> 42:54.080 Und jetzt wollen wir diese polynomiale Transformation machen. 42:55.500 --> 43:01.080 Also, wir nehmen uns eine beliebige Sprache aus L her. 43:01.360 --> 43:04.640 Und für jede feste Sprache aus L können wir eine neue Transformation 43:04.640 --> 43:05.080 machen. 43:06.560 --> 43:09.340 Später müssen Sie dann immer nur eine Transformation machen, weil Sie 43:09.340 --> 43:12.140 sich nur eine Sprache hernehmen, die schon N P vollständig ist und 43:12.140 --> 43:13.160 machen eine Transformation. 43:13.760 --> 43:17.060 Hier machen wir quasi unendlich viele Transformationen, für jede 43:17.060 --> 43:19.080 beliebige Sprache eine Transformation. 43:20.080 --> 43:21.500 Wird aber nicht so kompliziert. 43:24.500 --> 43:31.140 Der Plan ist, wir geben L, finden die Transformationen F und L, sodass 43:31.140 --> 43:38.620 jedes Wort X aus Sigma-Stern überführt wird in F11 von X, in ein neues 43:38.620 --> 43:41.480 Wort, durch eine deterministische Turing-Maschine, polynomial. 43:42.840 --> 43:48.240 Sodass unser ursprüngliches Wort, also diese Eingabe X, in der Sprache 43:48.240 --> 43:53.980 L liegt, genau dann, wenn das transformierte Wort in der Satz-Sprache 43:53.980 --> 43:54.300 liegt. 43:54.300 --> 43:59.220 Das heißt, wir wollen jetzt ein Wort überführen, oder die 43:59.220 --> 44:06.140 Transformation so machen, dass Eingaben, einfach 0,1 Strings 44:06.140 --> 44:10.040 sozusagen, überführt werden in Satz-Instanzen. 44:10.560 --> 44:13.320 In Variablen und Klauseln. 44:14.980 --> 44:22.060 Und zwar so, dass die Eingabe in der Sprache liegt, genau dann, wenn 44:22.060 --> 44:23.940 diese Satz-Instanz erfüllbar ist. 44:24.520 --> 44:25.980 Okay, das ist der Plan. 44:26.880 --> 44:31.760 Und was wir benutzen ist, für diese Transformation, dass, naja, die 44:31.760 --> 44:35.820 Sprache L liegt ja in NP, das ist alles was wir wissen über die 44:35.820 --> 44:36.240 Sprache. 44:36.240 --> 44:40.780 Das heißt, wir wissen, es gibt eine nicht-deterministische Turing 44:40.780 --> 44:44.300 -Maschine, die die Sprache in polymerer Zeit entscheidet. 44:45.240 --> 44:47.940 Und die nehmen wir uns her, so eine deterministische Turing-Maschine, 44:48.080 --> 44:51.400 da sehen wir jetzt, die hat endlich viele Zustände und 44:51.400 --> 44:53.660 Zustandsübergänge und alles mögliche. 44:54.140 --> 44:57.220 Und anhand dieser Turing-Maschine bauen wir jetzt die Formel. 44:58.680 --> 45:00.500 Okay, gut. 45:01.560 --> 45:05.700 Also, die Turing-Maschine M für die Sprache L, die wir nicht kennen, 45:05.900 --> 45:07.640 hat also alles mögliche. 45:07.940 --> 45:14.500 Endlich Zustandsmenge Q, Eingabe-Alphabet, ein Blank-Symbol, Band 45:14.500 --> 45:18.100 -Alphabet, ein Start-Zustand, eine Übergangsfunktion und einen 45:18.100 --> 45:21.180 akzeptierenden Endzustand und einen nicht akzeptierenden Endzustand. 45:22.180 --> 45:25.200 Und die Laufzeitfunktion von dieser Turing-Maschine ist durch ein 45:25.200 --> 45:31.320 Polynom beschränkt in N und OBDA ist es mindestens linear. 45:32.380 --> 45:39.160 Wenn wir jetzt eine Eingabe X haben für diese Turing-Maschine, dann 45:39.160 --> 45:44.920 könnte die entweder akzeptiert werden oder nicht. 45:46.300 --> 45:51.820 Und zwar eine akzeptierende Berechnung braucht höchstens P von N, 45:52.480 --> 45:54.260 wobei N die Länge von X ist. 45:54.420 --> 45:57.440 Ja, so ist ja gerade die Laufzeitkomplexitätsfunktion definiert. 45:58.640 --> 46:02.000 Und bei einer nicht akzeptierenden Berechnung möchte ich jetzt noch, 46:02.120 --> 46:07.720 eigentlich haben wir ja nichts darüber gesagt, für die Nein-Eingaben, 46:07.920 --> 46:09.500 was die Turing-Maschine tut. 46:09.500 --> 46:13.520 Aber ich möchte jetzt einfach, für meine Reduktion ist es wichtig, 46:13.820 --> 46:15.740 dass sie dann nicht super lange läuft. 46:16.620 --> 46:20.800 Und zwar wir sagen einfach, wir kennen ja dieses P von N, nach P von N 46:20.800 --> 46:22.400 plus 1 Schritten Abbruch. 46:24.580 --> 46:29.360 Oder anders, wir können einfach sagen, dass das Band auf dem das ganze 46:29.360 --> 46:32.300 Ding passiert von der Turing-Maschine nicht wirklich unendlich lang in 46:32.300 --> 46:35.260 beide Richtungen ist, sondern es geht höchstens P von N Schritte in 46:35.260 --> 46:37.080 die Richtung, P von N Schritte in die Richtung. 46:37.560 --> 46:42.080 Sodass schon überhaupt ans Ende des Bands zu laufen mehr Zeit braucht, 46:42.300 --> 46:43.700 als tatsächlich vorhanden ist. 46:44.960 --> 46:49.980 Das heißt, wir gucken uns jetzt diesen Bandabschnitt der Größe P von N 46:49.980 --> 46:51.380 an. 46:52.480 --> 46:58.420 Gut, das heißt, wenn wir jetzt eine Eingabe der Länge N haben, dann 46:58.420 --> 47:03.920 wird das jetzt irgendwie bearbeitet und beliebiger Zeitpunkt in der 47:03.920 --> 47:07.120 Bearbeitung ist eindeutig festgelegt durch. 47:07.600 --> 47:12.340 Was steht auf diesem endlichen Band zwischen Minus P von N und Plus P 47:12.340 --> 47:12.780 von N? 47:13.840 --> 47:15.620 Also an jeder Stelle, was steht da? 47:16.320 --> 47:18.940 In welchem Zustand befindet sich gerade die endliche Kontrolle? 47:20.540 --> 47:26.220 Und an welcher Position befindet sich der Lese- und Schreibkopf 47:26.220 --> 47:26.680 gerade? 47:28.240 --> 47:32.080 Das sind sozusagen Informationen, die kodieren, wie momentan die 47:32.080 --> 47:32.860 Berechnung aussieht. 47:33.700 --> 47:38.160 Und das will ich jetzt mit Klauseln und Variablen kodieren. 47:38.280 --> 47:40.820 Also mit Variablen will ich das jetzt erstmal kodieren. 47:41.560 --> 47:47.320 Ich führe jetzt eine ganze Menge Variablen ein, ganz viele, die dann 47:47.320 --> 47:49.320 Variablen meiner SAT-Instanz werden. 47:49.320 --> 47:56.120 Die Variablen sagen immer sowas wie, ist momentan der Lese-Schreibkopf 47:56.120 --> 47:58.120 an Stelle 5, ja oder nein? 47:59.040 --> 48:00.680 Das ist eine bursche Variable. 48:01.640 --> 48:09.880 Ist zum Zeitschritt 17 an Bandstelle Minus 13 ein A, ja oder nein? 48:11.240 --> 48:13.360 Also es werden ganz ganz viele Variablen. 48:15.900 --> 48:18.720 Dafür muss ich jetzt die ganzen Sachen ein bisschen benennen. 48:18.720 --> 48:22.740 Also die Zustände heißen Q0, das ist der Startzustand, Q1 und Q2 sind 48:22.740 --> 48:26.620 OBDA, diese Endzustände, und ansonsten gibt es noch Q3 bis QR. 48:27.340 --> 48:31.180 Die Symbole auf dem Bandalphabet sind vielleicht S0 für das Blank und 48:31.180 --> 48:33.300 S1 bis SL für die anderen. 48:34.660 --> 48:39.020 Und jetzt kommen diese ganzen Variablen, die ich einführe, Q, I, K. 48:40.140 --> 48:45.720 Die Bedeutung ist, zum Zeitpunkt I ist die endliche Kontrolle gerade 48:45.720 --> 48:46.540 im Zustand K. 48:49.440 --> 48:53.880 Also für jedes I, also die Zeitpunkte gehen von 0 bis P von N. 48:54.940 --> 48:57.820 Und die Zustände gibt es zwischen 0 und R. 48:58.580 --> 49:03.360 Das heißt, so viele Variablen, P von N plus 1 mal R plus 1, viele 49:03.360 --> 49:07.980 Variablen, die einfach nur sagen, zum Zeitpunkt I im Zustand K, ja 49:07.980 --> 49:08.420 oder nein. 49:10.640 --> 49:14.900 Entsprechend zum Zeitpunkt I ist der Lese- und Schreibkopf gerade an 49:14.900 --> 49:17.040 Position J des Bandes, ja oder nein. 49:17.200 --> 49:18.440 Das sind die HIJs. 49:20.140 --> 49:26.580 Und zum Zeitpunkt I ist an der Position J des Bandes momentan das 49:26.580 --> 49:29.440 Symbol SK des Alphabets drauf, ja oder nein. 49:29.880 --> 49:32.740 Das sind die SJIJKs. 49:34.720 --> 49:35.380 Okay? 49:36.500 --> 49:36.860 Gut. 49:37.760 --> 49:46.600 Das sind super viele Variablen, aber wichtig ist, R ist eine 49:46.600 --> 49:47.120 Konstante. 49:47.820 --> 49:51.680 Das ist ja eine Turing-Maschine für alle Eingaben, egal was N ist, R 49:51.680 --> 49:52.320 ist eine Konstante. 49:52.940 --> 49:54.180 17 vielleicht oder so. 49:55.460 --> 49:58.160 L ist eine Konstante, ist das Bande-Alphabet. 49:58.840 --> 50:01.360 Und alles andere ist polynomial in N. 50:01.360 --> 50:04.660 Das heißt, die Anzahl dieser Variablen ist polynomial in N. 50:05.900 --> 50:11.400 So, und jetzt können wir sozusagen die Berechnung der Turing-Maschine 50:11.400 --> 50:20.960 sehen, als zu jedem Zeitschritt gibt es so eine, oder ja, nee, eine 50:20.960 --> 50:25.180 komplette Berechnung der Turing-Maschine mit Zeitschritten, gibt mir 50:25.180 --> 50:28.080 eine Wahrheitsbelegung aller Variablen. 50:29.600 --> 50:30.100 Okay? 50:32.740 --> 50:36.720 Immer indem Sie einfach die Frage stellen, ist zum Zeitpunkt I an der 50:36.720 --> 50:40.340 Stelle J gerade Symbol SK, das ist entweder ja, also entweder ist das 50:40.340 --> 50:44.780 so oder nicht, bei der Berechnung dieser Turing-Maschine für diese 50:44.780 --> 50:46.080 gegebene Eingabe. 50:46.780 --> 50:49.480 Das heißt, Berechnungen aus der Turing-Maschine geben uns 50:49.480 --> 50:53.820 Variablenbelegungen und dann können wir zum Beispiel auch fragen, ist 50:53.820 --> 50:57.320 am Ende nach P von N Schritten die endliche Kontrolle in dem 50:57.320 --> 51:00.440 akzeptierenden Endzustand Qj, ja oder nein. 51:00.900 --> 51:03.880 Und das ist ja das, was uns interessiert, also ist das Wort in der 51:03.880 --> 51:04.620 Sprache oder nicht. 51:05.240 --> 51:06.620 Der Bandinhalt, was steht hier? 51:06.900 --> 51:07.780 Zum Zeitpunkt 0. 51:09.160 --> 51:12.480 Also, was ich gerade gesagt habe, wenn wir eine Berechnung haben, 51:12.780 --> 51:16.020 induziert uns das eine Wahrheitsbelegung, aber natürlich kann im 51:16.020 --> 51:20.380 Moment beliebige Wahrheitsbelegungen nicht, müssen nicht unbedingt zu 51:22.580 --> 51:24.500 Berechnungen der Turing-Maschine korrespondieren. 51:24.500 --> 51:28.040 Ich könnte zum Beispiel alles auf Wahr setzen, dann heißt es am 51:28.040 --> 51:30.900 gleichen Zeitpunkt an der gleichen Stelle stehen alle Symbole gerade 51:30.900 --> 51:31.520 da auf dem Band. 51:31.700 --> 51:32.520 Das ist natürlich Quatsch. 51:32.660 --> 51:34.020 Sowas müssen wir denn jetzt verhindern. 51:34.140 --> 51:38.980 Wir müssen so jetzt Klauseln einführen, sodass die einzigen 51:38.980 --> 51:44.220 Wahrheitsbelegungen, die alle Klauseln erfüllen, zu Berechnungen von 51:44.220 --> 51:45.480 der Turing-Maschine korrespondieren. 51:46.220 --> 51:50.440 Also, wir konstruieren die Transformation, wir haben die Variablen 51:50.440 --> 51:53.500 schon eingeführt, jetzt müssen wir noch die Klauseln einführen und 51:53.500 --> 51:58.240 jetzt muss es äquivalent sein, es gibt eine akzeptierende Berechnung 51:58.240 --> 52:03.580 der Turing-Maschine, muss äquivalent dazu sein, es gibt eine 52:03.580 --> 52:08.040 Wahrheitsbelegung dieser Variablen, die alle Klauseln erfüllt. 52:08.520 --> 52:14.120 Gut, und dann, wenn wir das geschafft haben, dann sind wir am Ziel. 52:14.120 --> 52:17.220 Dann können wir so fließen. 52:17.580 --> 52:22.880 Also, wenn die Eingabe in L war, dann existiert also, das ist genau 52:22.880 --> 52:25.740 dann, wenn es eine akzeptierende Berechnung der Turing-Maschine gibt, 52:25.860 --> 52:29.700 mit Orakel, es gibt eine Orakel-Belegung, sodass alles gut ist. 52:30.620 --> 52:34.860 Das heißt, es gibt eine akzeptierende Berechnung M bei der Eingabe X 52:34.860 --> 52:38.240 mit höchstens p von n Schritten und das Orakel hat auch Länge 52:38.240 --> 52:39.140 höchstens p von n. 52:39.820 --> 52:48.060 Das heißt, es gibt ein initiales Band, beschrieben, sodass dann die 52:48.060 --> 52:50.600 deterministische Kontrolle alles tut. 52:52.320 --> 52:55.580 Und das heißt dann, wenn wir das hingekriegt haben, es gibt eine 52:55.580 --> 53:01.660 Wahrheitsbelegung für unsere ganzen Variablen, die alle Klauseln 53:01.660 --> 53:01.980 erfüllen. 53:02.900 --> 53:05.360 Die Klauseln haben wir noch nicht gemacht, aber das ist der Plan. 53:07.000 --> 53:09.860 Dann haben wir das geschafft und das ist immer dieser Teil, den Sie in 53:09.860 --> 53:11.060 der Transformation machen wollen. 53:11.900 --> 53:16.680 X in der Ursprungssprache, genau dann, wenn das abgebildete Ding in 53:16.680 --> 53:19.380 der neuen Sprache, also f, L von X, insat. 53:21.140 --> 53:24.940 Für die Klauseln, da gibt es jetzt verschiedene Gruppen von Klauseln, 53:25.020 --> 53:26.740 die immer verschiedenste Sachen herstellen. 53:26.860 --> 53:28.460 Es gibt insgesamt sechs Gruppen. 53:28.960 --> 53:32.720 Die erste Gruppe ist dazu zuständig, dass zu jedem Zeitpunkt i die 53:32.720 --> 53:36.920 Endliche Kontrolle immer nur in einem Zustand sein kann und nicht in 53:36.920 --> 53:37.380 mehreren. 53:38.080 --> 53:39.280 Das muss sichergestellt werden. 53:40.060 --> 53:42.940 Die zweite Gruppe ist dafür da, dass der Lese-Schreibkopf immer nur an 53:42.940 --> 53:47.060 einer Position stehen darf, dass man nicht einfach, er steht an 53:47.060 --> 53:51.020 Position 7, ja, und an Position 9, ja, dass man das nicht gleichzeitig 53:51.020 --> 53:51.900 auf Ja setzen kann. 53:54.160 --> 53:58.680 Die dritte Gruppe ist, an jedem Zeitpunkt hat jede Stelle des Bandes 53:58.680 --> 54:02.500 immer nur ein Symbol, eventuell ein Blank, aber nicht mehrere Symbole 54:02.500 --> 54:04.140 gleichzeitig an dem Band. 54:04.920 --> 54:06.800 Das ist alles relativ einfach. 54:07.900 --> 54:13.620 Die vierte ist, dass am Anfang, also zum Zeitpunkt 0, sieht das Band 54:13.620 --> 54:19.880 so aus, dass auf den ersten N-Zellen wirklich die Eingabe steht. 54:21.240 --> 54:24.720 Dahinter blanks und davor sagen wir nicht. 54:25.420 --> 54:26.440 Da lassen wir es frei. 54:27.160 --> 54:30.880 Das ist sozusagen, das Orake entscheidet da, wie da die Variablen 54:30.880 --> 54:31.540 gesetzt werden. 54:34.900 --> 54:41.040 Die fünfte Gruppe ist, am Ende, nach P von N Schritten, sind wir im 54:41.040 --> 54:42.100 akzeptierenden Endzustand. 54:42.760 --> 54:43.520 Das ist auch einfach. 54:44.520 --> 54:49.100 Und das sechste ist tatsächlich das Herz der ganzen Dinge, dass wenn 54:49.100 --> 54:54.880 wir im Zeitpunkt I sind und die ganzen Variablen geben uns eine 54:54.880 --> 54:59.960 Konfiguration an von der Turing-Maschine, dann ist die Variablen, die 54:59.960 --> 55:04.820 zum Zeitpunkt I plus 1 korrespondieren, auch eine Konfiguration von 55:04.820 --> 55:08.820 der Turing-Maschine und das ist ein zulässiger Schritt gewesen. 55:09.780 --> 55:11.520 Das heißt, da darf sich nicht so viel ändern. 55:14.200 --> 55:16.040 Also, gehen wir die Gruppen durch. 55:16.180 --> 55:17.340 Klauselgruppe 1 nochmal. 55:17.640 --> 55:23.960 Das Ziel ist, zu jedem Zeitpunkt I soll die Maschine M in nur einem 55:23.960 --> 55:25.980 Zustand sein von der endlichen Kontrolle. 55:26.780 --> 55:29.580 Und das ist einfach, wenn Sie sich erinnern, wie die Variablen 55:29.580 --> 55:30.240 definiert waren. 55:30.500 --> 55:35.500 Also QI0 ist wahr, wenn zum Zeitpunkt I die endliche Kontrolle im 55:35.500 --> 55:36.540 Zustand Q0 ist. 55:39.400 --> 55:40.980 QIr ist wahr und so weiter. 55:41.280 --> 55:48.460 Also diese Klausel hier sagt, wir müssen entweder in Q0 sein oder in 55:48.460 --> 55:51.480 Q1 sein oder in Q2 sein oder in Qr sein. 55:51.640 --> 55:53.080 Mindestens eins davon muss wahr sein. 55:53.980 --> 55:56.280 Das ist schon mal einfach ausgeschlossen, dass alle falsch sind. 55:56.380 --> 55:58.040 Das wäre irgendwie in gar keinem Zustand. 55:59.540 --> 56:02.860 Jetzt müssen wir aber natürlich sagen, es darf nur eins von denen wahr 56:02.860 --> 56:03.160 sein. 56:04.120 --> 56:04.980 Und das machen wir so. 56:05.860 --> 56:08.880 Also das sagt, mindestens eins ist wahr und hier ist nicht mehr als 56:08.880 --> 56:09.480 eins ist wahr. 56:11.700 --> 56:16.040 I ist fest, I ist der Schritt, in dem wir gerade sind, der 56:16.040 --> 56:16.540 Zeitschritt. 56:16.940 --> 56:20.980 Und J und J' sind jetzt verschiedene Zustände, die sollen nicht beide 56:20.980 --> 56:21.740 falsch sein. 56:23.280 --> 56:28.640 Das heißt, die sollen nicht beide wahr sein. 56:29.280 --> 56:33.980 Entweder QIj soll falsch sein oder QIj' soll falsch sein. 56:34.600 --> 56:37.380 Das ist genau eine Klausel mit negierten Literalen. 56:40.020 --> 56:45.840 Wahrscheinlich sind die beide falsch, weil weder wir in Qj noch in Qj' 56:45.980 --> 56:46.280 sind. 56:46.540 --> 56:49.660 Die einzig verbotene Situation ist, wir sind gleichzeitig in Qj und in 56:49.660 --> 56:50.300 Qj'. 56:50.300 --> 56:51.660 Das ist am gleichen Zeitpunkt I. 56:51.960 --> 56:54.580 Das ist verboten und das würde nämlich diese Klausel hier nicht 56:54.580 --> 56:55.440 erfüllen. 56:55.500 --> 56:55.700 Gut. 56:56.640 --> 56:58.700 Das heißt, die Qs sehen jetzt alle gut aus. 56:58.980 --> 57:03.640 Zu jedem I ist genau eins von diesen QI0 bis QIr auch wahr und alle 57:03.640 --> 57:04.220 anderen sind falsch. 57:06.500 --> 57:09.140 Ähnlich ist es mit der Position des Lese-Schreibkopfes. 57:09.160 --> 57:14.640 Wir wollen, dass für jedes I und jede Bandposition, geben wir jetzt 57:14.640 --> 57:17.820 an, hier ist der Lese-Schreibkopf gerade oder halt nicht. 57:18.380 --> 57:21.100 Zuerst stellen wir sicher, dass er überhaupt irgendwo mindestens ist 57:21.100 --> 57:22.420 und nicht überall falsch steht. 57:22.620 --> 57:24.060 Das ist die gleiche erste Klausel. 57:24.060 --> 57:27.540 Und hier hinten ist wieder, er darf nicht gleichzeitig an zwei 57:27.540 --> 57:28.280 Positionen stehen. 57:28.500 --> 57:31.880 Also für jedes J und J', was verschieden ist, jetzt referenziertes 57:31.880 --> 57:36.960 Bandposition, muss entweder der Kopf am Zeitpunkt I nicht an Position 57:36.960 --> 57:39.440 J sein oder nicht an Position J'. 57:40.980 --> 57:42.020 Dritte Klauselgruppe. 57:42.020 --> 57:45.640 Zu jedem Zeitpunkt hat jede Stelle des Bandes genau ein Symbol. 57:46.020 --> 57:48.320 Also für alle I und für alle J. 57:48.480 --> 57:51.880 I ist jetzt der feste Zeitpunkt, J ist die feste Stelle des Bandes. 57:52.460 --> 57:55.540 Und jetzt der dritte Index ist, welches Bandsymbol könnte da stehen. 57:56.320 --> 57:59.440 Das erste heißt wieder, da steht schon mal mindestens ein Bandsymbol. 58:00.540 --> 58:04.940 Und das zweite ist, für verschiedene Bandsymbole, K und K', dürfen die 58:04.940 --> 58:06.180 nicht gleichzeitig da stehen. 58:07.040 --> 58:11.640 Also entweder steht da nicht K oder da steht nicht K'. 58:12.420 --> 58:12.980 Gut. 58:13.800 --> 58:16.580 Also jetzt sind die Variablen schon mal alle so gesetzt, dass für 58:16.580 --> 58:19.500 einen festen Zeitpunkt sieht das immer ordentlich aus. 58:19.500 --> 58:22.500 Die Endliche Kontrolle ist in genau einem Zustand. 58:22.960 --> 58:24.840 Der Lese-Schreibkopf ist an genau einer Stelle. 58:25.480 --> 58:29.100 An jeder Stelle des Bandes steht genau ein Symbol, eventuell ein 58:29.100 --> 58:29.360 Blink. 58:31.040 --> 58:32.120 Jetzt Anfangskonfiguration. 58:32.860 --> 58:37.420 Wir wollen, dass zum Zeitpunkt 0 die Endliche Kontrolle in Q0 ist. 58:37.700 --> 58:40.800 Da sagen wir einfach, das ist eine Klausel mit einer Variable. 58:41.440 --> 58:44.560 Die einzige Möglichkeit, diese Klausel zu erfüllen, ist diese Variable 58:44.560 --> 58:45.420 auf Wahr zu setzen. 58:46.240 --> 58:50.140 Der Lese-Schreibkopf soll zum Zeitpunkt 0 an Position 1 des Bandes 58:50.140 --> 58:50.400 sein. 58:50.540 --> 58:51.980 Das ist einfach wieder genau das gleiche. 58:52.040 --> 58:54.540 Eine Klausel mit einer Variable. 58:55.320 --> 58:59.740 In den ersten N-Zellen steht genau das Eingabewort. 59:01.020 --> 59:05.140 An der Stelle 0 steht ein Blink. 59:07.860 --> 59:11.260 An Stelle 1 steht das erste Symbol. 59:11.480 --> 59:13.540 An Stelle N steht das N-Symbol usw. 59:14.300 --> 59:16.360 Rechts der Eingabe stehen lauter Blinks. 59:16.520 --> 59:20.920 Von N plus 1 bis PN plus 1 steht immer das 0. 59:21.080 --> 59:21.380 Symbol. 59:21.500 --> 59:22.880 Das war als Blink definiert. 59:22.880 --> 59:28.160 Und links von dem ersten Blink haben wir keine Angaben gemacht, weil 59:28.160 --> 59:29.640 wir da keine Kontrolle darüber haben. 59:29.720 --> 59:30.640 Das macht ja das Orakel. 59:33.500 --> 59:37.060 Orakel schreibt da ja irgendwas hin und entsprechend erlauben wir hier 59:37.060 --> 59:39.160 die Variablen irgendwas zu sein. 59:39.320 --> 59:39.980 Wahr oder falsch. 59:40.400 --> 59:40.760 Wie auch immer. 59:42.280 --> 59:44.960 Fünfte Gruppe fast fertig ist auch noch eine einfache. 59:45.180 --> 59:48.640 Am Ende nach P von N Schritten haben wir akzeptiert. 59:48.640 --> 59:54.040 Das heißt einfach zum Zeitpunkt PN ist die endliche Kontrolle in 59:54.040 --> 59:55.360 diesem QJ Zustand. 59:55.540 --> 59:56.640 Das war der mit Index 1. 59:58.040 --> 01:00:02.680 Und jetzt kommt die sechste und schwierigste Gruppe. 01:00:03.700 --> 01:00:07.940 Von einem Zeitschritt zum nächsten soll das eine ordentliche 01:00:07.940 --> 01:00:10.680 Berechnung von dieser gegebenen Turing-Maschine sein. 01:00:10.680 --> 01:00:17.440 Also zum Zeitpunkt I sind wir in der Konfiguration und dann im 01:00:17.440 --> 01:00:21.680 Zeitpunkt I plus 1 zur nächsten und das soll genau einer 01:00:21.680 --> 01:00:24.020 Übergangsfunktion von Delta entsprechen. 01:00:24.740 --> 01:00:29.460 Das machen wir mit zwei Teilgruppen G61 und G62. 01:00:30.360 --> 01:00:37.220 Also G61 sorgt dafür, dass wenn zum Zeitpunkt I an Position J das 01:00:37.220 --> 01:00:44.600 Symbol K steht und der Leseschreibkopf gerade an Position J steht, da 01:00:44.600 --> 01:00:45.700 wo dieses K ist, 01:00:48.740 --> 01:00:53.940 dann hat M zum Zeitpunkt, wenn er dort nicht steht, oh Gott, wenn wir 01:00:53.940 --> 01:00:57.260 gerade über eine Bandposition reden, am Zeitpunkt I, wo der 01:00:57.260 --> 01:01:00.520 Leseschreibkopf nicht ist, dann soll danach immer noch das gleiche 01:01:00.520 --> 01:01:01.340 Ding auf dem Band stehen. 01:01:01.840 --> 01:01:03.100 Das macht G61. 01:01:06.380 --> 01:01:12.660 Und G62 ist jetzt, naja, das Band, wo der Leseschreibkopf steht, da 01:01:12.660 --> 01:01:14.240 darf es sich ändern. 01:01:14.420 --> 01:01:17.440 Da gucken wir dann in die Delta-Funktion nach, wie sich das ändert. 01:01:17.600 --> 01:01:19.180 Das muss also wirklich Delta entsprechen. 01:01:20.000 --> 01:01:21.640 Also, das erste. 01:01:25.080 --> 01:01:25.640 Wenn... 01:01:26.180 --> 01:01:31.140 Also, wir gucken uns das zuerst mit so einer logischen Formel an, das 01:01:31.140 --> 01:01:34.440 ist jetzt noch keine Veroderung von irgendwelchen Klauseln und machen 01:01:34.440 --> 01:01:35.900 danach eine Veroderung drauf. 01:01:37.220 --> 01:01:42.780 Also wenn zum Zeitpunkt I an Stelle J das Karte-Symbol auf dem Band 01:01:42.780 --> 01:01:49.980 steht, das heißt, wenn diese Variable hier wahr ist und der Kopf zum 01:01:49.980 --> 01:01:54.780 Zeitpunkt I nicht an Stelle J ist, also dieses Literal hier wahr ist, 01:01:54.940 --> 01:01:56.740 weil die Variable dazu falsch ist. 01:01:57.740 --> 01:02:03.060 Wenn das beides gilt, dann muss folgen, dass zum Zeitpunkt I plus 1 an 01:02:03.060 --> 01:02:05.700 Stelle J immer noch das Symbol K auf dem Band steht. 01:02:06.260 --> 01:02:08.480 Das kann sich nicht einfach ändern, obwohl der Kopf woanders ist. 01:02:09.180 --> 01:02:09.820 Okay. 01:02:12.480 --> 01:02:16.660 Und jetzt ist es einfach eine logische Umformung, wie man so eine 01:02:16.660 --> 01:02:22.480 Implikation logisch-äquivalent umformt in ein Oder. 01:02:22.760 --> 01:02:27.380 Und zwar macht man das, indem man die Negation von der Prämisse nimmt 01:02:27.380 --> 01:02:30.040 oder das Resultat. 01:02:31.100 --> 01:02:38.380 Also Sie stellen sich vor, entweder die Prämisse ist falsch, dann ist 01:02:38.380 --> 01:02:39.340 die Implikation richtig. 01:02:39.920 --> 01:02:42.420 Weil die Prämisse nicht erfüllt ist, dann ist uns egal, was los ist. 01:02:42.880 --> 01:02:46.460 Entweder die Prämisse ist falsch oder das Hinten ist wahr. 01:02:46.620 --> 01:02:49.240 Wenn das Hinten wahr ist, dann ist auf jeden Fall die Implikation auch 01:02:49.240 --> 01:02:50.720 wahr, egal was vorne steht. 01:02:51.320 --> 01:02:56.240 Das einzig Böse ist, vorne ist richtig und hinten ist falsch von so 01:02:56.240 --> 01:02:56.800 einer Implikation. 01:02:56.900 --> 01:02:58.960 Das ist eigentlich einzig Böse und das müssen wir ausschließen. 01:02:58.960 --> 01:03:02.820 Also sagen wir entweder vorne falsch oder hinten richtig. 01:03:03.620 --> 01:03:06.180 Und hinten richtig ist einfach nur SI plus 1JK. 01:03:07.200 --> 01:03:11.640 Und vorne falsch ist, naja, wenn man nennt es ein Und, negiert, dann 01:03:11.640 --> 01:03:14.860 wird da draußen Oder und die einzelnen Dinger negieren sich. 01:03:15.100 --> 01:03:21.620 Also es ist nicht der Fall, dass SIJK und nicht HIJ. 01:03:21.940 --> 01:03:26.160 Also ist äquivalent dazu, dass nicht SIJK oder HIJ. 01:03:26.160 --> 01:03:29.540 Gut, also so haben wir eine Klausel daraus gekriegt. 01:03:32.900 --> 01:03:35.420 Jetzt kommt Klauselgruppe 6.2. 01:03:36.160 --> 01:03:38.820 Dort wo der Leseschreibkopf ist, muss es jetzt ein ordentlicher 01:03:38.820 --> 01:03:39.820 Übergang sein. 01:03:40.620 --> 01:03:42.160 Also machen wir wieder... 01:03:43.000 --> 01:03:44.120 Wie gehen wir? 01:03:44.200 --> 01:03:46.660 Wir sind gerade irgendwie bei dem Übergang. 01:03:48.540 --> 01:03:50.480 Endliche Kontrolle ist in Zustand A. 01:03:51.100 --> 01:03:52.540 Wir lesen Zeichen U. 01:03:52.540 --> 01:03:58.360 Und unsere Turing-Maschine sagt, okay, dann gehe in Zustand B. 01:03:58.760 --> 01:04:00.100 Schreibe Zeichen V. 01:04:00.740 --> 01:04:02.580 Und gehe in Richtung D. 01:04:02.740 --> 01:04:08.200 Wobei D hier, also minus 101 für links stehen bleiben rechts. 01:04:09.900 --> 01:04:14.660 Und die Konstruktion heißt, also wenn wir, wenn der Kopf gerade an 01:04:14.660 --> 01:04:19.740 Zeitpunkt I an Stelle J ist und wir im Zustand mit der Endlichen 01:04:19.740 --> 01:04:25.560 Kontrolle A sind zum Zeitpunkt I und wir gerade das Zeichen U lesen, 01:04:25.660 --> 01:04:31.000 also zum Zeitpunkt I an Stelle J das Zeichen U steht, dann muss zum 01:04:31.000 --> 01:04:37.300 Zeitpunkt I plus 1 der Kopf an Stelle J plus D sein. 01:04:37.680 --> 01:04:40.880 Also wieder J, wenn D gleich 0 ist, oder halt links oder rechts. 01:04:40.880 --> 01:04:45.380 Und unter den gleichen Voraussetzungen muss danach zum Zeitpunkt I 01:04:45.380 --> 01:04:52.140 plus 1 der Zustand B sein und danach zum Zeitpunkt I plus 1 muss an 01:04:52.140 --> 01:04:54.460 Stelle J jetzt das faute Zeichen stehen. 01:04:55.560 --> 01:04:57.340 Das sind wieder so eine Implikation. 01:04:57.480 --> 01:05:00.880 Diese Implikation können wir wieder umschreiben als eine Veroderung 01:05:00.880 --> 01:05:05.100 von entweder das da vorne ist falsch oder das da hinten ist richtig 01:05:05.100 --> 01:05:09.740 und das da vorne falsch, das war eine Verundung, beim Negieren wird 01:05:09.740 --> 01:05:13.800 eine Veroderung draus, wobei alle Sachen in negierte Literale werden. 01:05:14.080 --> 01:05:16.720 Und wir erhalten diese drei Klauseln. 01:05:17.820 --> 01:05:20.220 Für einen Übergang, für einen Zeitpunkt. 01:05:23.080 --> 01:05:27.160 Und da es aber nur polynomiell viele Zeitpunkte gibt und nur konstant 01:05:27.160 --> 01:05:30.180 viele Übergänge, ist es also insgesamt polynomiell viele Klauseln. 01:05:31.780 --> 01:05:33.140 Aber verdammt viele. 01:05:33.140 --> 01:05:34.060 Gut. 01:05:36.020 --> 01:05:37.840 Zwischenbilanz, was tun wir hier eigentlich gerade? 01:05:38.700 --> 01:05:42.780 Wir zeigen hier eigentlich gerade, dass Satz ein sehr schwieriges 01:05:42.780 --> 01:05:48.880 Problem ist, nämlich NP vollständig, ein schwierigstes Problem in der 01:05:48.880 --> 01:05:49.480 Klasse NP. 01:05:50.860 --> 01:05:52.280 Wie wollen wir das gerade tun? 01:05:52.380 --> 01:05:56.740 Wir wollen dazu gerade eine feste beliebige Sprache L aus NP 01:05:56.740 --> 01:06:00.140 reduzieren polynomial auf Satz. 01:06:01.140 --> 01:06:02.700 Wie gehen wir dazu vor? 01:06:03.000 --> 01:06:07.820 Wir konstruieren diese polynomiale Abbildung, die beliebige Eingaben 01:06:07.820 --> 01:06:17.440 aus Sigma-Stern auf Eingaben von Satz transformiert, also auf Mengen 01:06:17.440 --> 01:06:18.960 von Variablen und Klauseln. 01:06:21.000 --> 01:06:26.400 Mit der Eigenschaft, dass wenn die Eingabe vorne in der Sprache liegt, 01:06:26.400 --> 01:06:29.580 dann haben wir das auf eine Klauselmenge abgebildet, die erfüllbar 01:06:29.580 --> 01:06:29.900 ist. 01:06:30.740 --> 01:06:33.680 Und wenn die Eingabe vorne nicht in der Sprache liegt, dann haben wir 01:06:33.680 --> 01:06:36.560 das auf eine Klauselmenge abgebildet, die nicht erfüllbar ist. 01:06:38.280 --> 01:06:42.680 Das heißt, zu entscheiden, ob die Eingabe in der Sprache liegt, können 01:06:42.680 --> 01:06:46.880 wir tun, indem wir das transformieren und dann entscheiden, ob die 01:06:46.880 --> 01:06:48.120 Klauselmenge erfüllbar ist. 01:06:48.960 --> 01:06:53.840 Das heißt, Satz zu lösen ist mindestens so schwierig, wie das 01:06:53.840 --> 01:06:57.320 ursprüngliche Problem zu lösen, ob die Eingabe in der Sprache ist. 01:06:59.920 --> 01:07:03.940 Wie haben wir das gemacht, diese Transformation von einer Eingabe auf 01:07:03.940 --> 01:07:04.680 eine Klauselmenge? 01:07:05.080 --> 01:07:08.680 Wir haben uns angeguckt, wie sieht denn die Turing-Maschine aus, zu 01:07:08.680 --> 01:07:09.980 der Sprache, die die löst. 01:07:11.600 --> 01:07:16.040 Wir haben die Laufzeit von der beschränkt durch ein Polynom, weil die 01:07:16.040 --> 01:07:17.500 Sprache ja in NP ist. 01:07:18.220 --> 01:07:23.260 Und wir haben uns ganz viele Variablen definiert, die uns kodieren 01:07:23.260 --> 01:07:28.780 diese Q-Variablen, in welchem Zustand die endliche Kontrolle zum 01:07:28.780 --> 01:07:30.200 Zeitpunkt J ist. 01:07:30.620 --> 01:07:34.220 Die H-Variablen, die uns kodieren, an welcher Position der 01:07:34.220 --> 01:07:36.220 Leseschreibkopf zum Zeitpunkt I steht. 01:07:36.620 --> 01:07:41.380 Und die S-Variablen, die uns kodieren zum Zeitpunkt I und an 01:07:41.380 --> 01:07:44.100 Bandstelle J, welches Zeichen da gerade auf dem Band steht. 01:07:46.160 --> 01:07:50.600 Und wir haben dann eine Klauselmenge C generiert aus sechs Gruppen, 01:07:50.600 --> 01:07:59.820 die dann sichergestellt haben, dass, wenn das Wort in der Sprache 01:07:59.820 --> 01:08:03.920 liegt, es dann, das wissen wir schon, dann gibt es eine akzeptierende 01:08:03.920 --> 01:08:08.400 Berechnung der Turing-Maschine, dass diese Berechnung überführt werden 01:08:08.400 --> 01:08:11.320 kann in eine Wahrheitsbelegung der Klausel, die alle Klauseln 01:08:11.320 --> 01:08:12.260 gleichzeitig erfüllt. 01:08:14.020 --> 01:08:17.460 Und wir haben das so gemacht, dass es auch in der Rückrichtung gilt, 01:08:17.460 --> 01:08:21.220 egal wie die Wahrheitsbelegung für die Klauseln aussieht, wenn die 01:08:21.220 --> 01:08:25.120 alle erfüllt, dann sieht die so aus wie eine Berechnung von der Turing 01:08:25.120 --> 01:08:25.420 -Maschine. 01:08:25.980 --> 01:08:29.300 Das ist die einzige Möglichkeit, diese ganzen Klauseln alle 01:08:29.300 --> 01:08:30.400 gleichzeitig zu erfüllen. 01:08:31.040 --> 01:08:33.480 Das muss so aussehen wie von der Turing-Maschine. 01:08:34.040 --> 01:08:39.620 Das heißt, wenn die Klauselmenge erfüllbar ist, dann gab es eine 01:08:39.620 --> 01:08:41.420 akzeptierende Berechnung für die Turing-Maschine. 01:08:41.580 --> 01:08:45.760 Das heißt, dann war das ursprüngliche Wort in der Sprache. 01:08:48.800 --> 01:08:50.780 So, also fast fertig. 01:08:50.940 --> 01:08:52.660 Noch einen Punkt möchte ich nochmal hervorheben. 01:08:52.860 --> 01:08:56.500 Das Ganze haben wir geschafft in polynomieller Zeit. 01:08:57.820 --> 01:08:59.180 Das ist ganz wichtig. 01:08:59.920 --> 01:09:02.820 Wir haben es polynomiell und deterministisch gemacht. 01:09:02.900 --> 01:09:04.880 Das war eine deterministische Konstruktion hier. 01:09:04.940 --> 01:09:09.100 Wir könnten den Computer anweisen, gegeben die Turing-Maschine und 01:09:09.100 --> 01:09:12.000 gegeben die Eingabe X, baue diese Klauseln. 01:09:13.340 --> 01:09:16.760 Das war ein ganz festgegebenes deterministisches Kochrezept. 01:09:16.760 --> 01:09:21.500 Und für dieses Bauen der Klauseln wird er nicht super viel Zeit 01:09:21.500 --> 01:09:21.920 brauchen. 01:09:22.120 --> 01:09:25.620 Nämlich nur polynomiell in der Größe von X. 01:09:27.160 --> 01:09:28.180 Warum ist das so? 01:09:28.460 --> 01:09:33.200 Weil wir irgendwie diese ganzen Variablen waren immer beschränkt durch 01:09:33.200 --> 01:09:35.040 Indizes, die höchstens P von N waren. 01:09:36.260 --> 01:09:37.660 Und P von N war ja ein Polynom. 01:09:39.500 --> 01:09:42.080 Das heißt, diese Transformation braucht nicht viel Zeit. 01:09:42.080 --> 01:09:46.660 Das heißt, wenn wir das einfach transformiert haben und jetzt einfach, 01:09:46.920 --> 01:09:50.580 satt lösen könnten, könnten wir einfach die ursprüngliche Sprache 01:09:50.580 --> 01:09:51.380 entscheiden. 01:09:53.740 --> 01:09:57.820 Es gibt noch ein paar Folien, die wirklich die Polynomialität nochmal 01:09:57.820 --> 01:09:58.460 überprüfen. 01:09:59.660 --> 01:10:03.700 Also, wir schätzen die Anzahl der Literale in den Klauselgruppen ab. 01:10:06.480 --> 01:10:08.560 Das war Klauselgruppe 1. 01:10:09.660 --> 01:10:12.020 Dann nochmal zur Wiederholung, wie die genau aussah. 01:10:12.160 --> 01:10:19.280 Und hier unten ist jetzt einfach nur abgeschätzt, wie viele Literale 01:10:19.280 --> 01:10:21.660 wir insgesamt in den ganzen Klauseln auftauchen haben. 01:10:21.860 --> 01:10:25.880 Also, wie lang unsere Formel in Klauselgruppe 1 insgesamt wird. 01:10:26.480 --> 01:10:29.800 Ich werde es nicht genau durchgehen, aber vielleicht gehe ich es für 01:10:29.800 --> 01:10:32.360 die erste Gruppe durch und dann für die nächsten fünf nicht mehr. 01:10:33.660 --> 01:10:36.560 Hier vorne haben wir insgesamt R plus 1. 01:10:37.580 --> 01:10:41.100 Das ist R plus 1 hier. 01:10:41.500 --> 01:10:48.420 Für jedes i, was von 0 bis pn läuft, also R plus 1 mal pn plus 1. 01:10:48.860 --> 01:10:50.120 Das ist für das da oben. 01:10:50.620 --> 01:10:52.180 Und hier unten haben wir immer 2. 01:10:53.440 --> 01:10:54.320 Das ist dieses 2. 01:10:54.720 --> 01:10:59.780 Für jedes i, was von 0 bis pn läuft, also mal pn plus 1. 01:11:00.160 --> 01:11:05.740 Und für jedes j und j' die beide zwischen 0 und r laufen, also beide 01:11:05.740 --> 01:11:08.460 haben R plus 1 Möglichkeiten, aber sind verschieden. 01:11:08.600 --> 01:11:11.340 Und das ist dann also R mal R plus 1 halbe Möglichkeit. 01:11:13.240 --> 01:11:14.580 Und das ist polynomiell. 01:11:14.900 --> 01:11:19.380 Also R ist eine Konstante und p ist ein Polynom. 01:11:20.640 --> 01:11:23.360 Und entsprechend kriegen wir das für Klauselgruppe 2 hin. 01:11:24.040 --> 01:11:27.820 Hier werden wir mal Polynome miteinander multiplizieren müssen. 01:11:28.040 --> 01:11:31.820 Also wenn das vorher ein quadratisches Polynom war, dann ist jetzt das 01:11:31.820 --> 01:11:35.480 insgesamt hoch 4, aber das bleibt polynomiell. 01:11:37.060 --> 01:11:40.260 Und hier hinten wird sogar 3 Polynome miteinander multipliziert, wenn 01:11:40.260 --> 01:11:41.000 ich das richtig sehe. 01:11:41.160 --> 01:11:44.820 Das heißt, es wird dann hoch 6, wenn p quadratisch war. 01:11:46.640 --> 01:11:52.060 Entsprechend Klauselgruppe 3, Klauselgruppe 4, Klauselgruppe 5, was 01:11:52.060 --> 01:11:54.440 nur eine Klausel mit einer Variablen hat. 01:11:55.860 --> 01:12:00.040 Klauselgruppe 6 1 und Klauselgruppe 6 2, die wir alle kennengelernt 01:12:00.040 --> 01:12:00.320 haben. 01:12:00.320 --> 01:12:03.640 Und wenn wir das alles zusammenfassen, dann sehen wir, dass alle 6 01:12:03.640 --> 01:12:04.960 Teile polynomiell sind. 01:12:05.140 --> 01:12:09.400 Das heißt, das ganze Ding ist polynomiell beschränkt. 01:12:09.720 --> 01:12:14.780 Wieder, wir benutzen R und L sind Konstanten und p von n ist ein 01:12:14.780 --> 01:12:15.160 Polynom. 01:12:16.540 --> 01:12:18.640 Also sind alle Größen polynomial. 01:12:18.880 --> 01:12:21.720 Die angegebene Funktion ist wirklich eine polynomiale Transformation 01:12:21.720 --> 01:12:24.600 von einer beliebigen Sprache in Satz. 01:12:24.620 --> 01:12:26.980 Wir haben gezeigt den Satz von Cook. 01:12:29.440 --> 01:12:32.560 Wahrscheinlich hatte ich heute nicht nur das Vergnügen, Ihnen das 01:12:32.560 --> 01:12:35.460 wichtigste Konzept der Vorlesung kennenzulernen, sondern auch noch das 01:12:35.460 --> 01:12:39.540 Vergnügen, Ihnen den kompliziertesten Beweis der Vorlesung zu zeigen. 01:12:40.220 --> 01:12:46.020 Der Satz von Cook ist aber eminent wichtig für die theoretische 01:12:46.020 --> 01:12:49.760 Informatik, weil darauf dieses ganze Konzept der NP-Vollständigkeit 01:12:49.760 --> 01:12:50.280 basiert. 01:12:50.720 --> 01:12:54.600 Jetzt haben wir einmal diese schwere Arbeit getan und haben ein 01:12:54.600 --> 01:12:58.620 Problem, was NP-Vollständig ist, identifiziert. 01:12:59.060 --> 01:13:03.560 Jetzt zu zeigen, dass folgende Probleme NP-Vollständig sind, ist dann 01:13:03.560 --> 01:13:04.100 einfacher. 01:13:04.440 --> 01:13:07.920 Jetzt haben wir schon mal sozusagen eine Basis, auf die wir aufbauen 01:13:07.920 --> 01:13:11.960 können und jetzt müssen wir nur noch von Satz auf irgendwas anderes 01:13:11.960 --> 01:13:12.500 reduzieren. 01:13:13.480 --> 01:13:15.980 Und jedes Mal, wenn wir das schaffen, haben wir ein neues NP 01:13:15.980 --> 01:13:19.560 -Vollständiges Problem identifiziert, was wir jetzt theoretisch wieder 01:13:19.560 --> 01:13:23.460 als Basis nehmen könnten für eine neue Reduktion oder wir basieren das 01:13:23.460 --> 01:13:25.620 wieder auf Satz und so weiter. 01:13:26.100 --> 01:13:32.860 Und so bauen wir uns dann so eine Menge von NP-Vollständigen 01:13:32.860 --> 01:13:35.760 Problemen, von denen wir schon wissen, dass die alle schwer sind. 01:13:36.200 --> 01:13:39.920 Und wenn Sie etwas Neues zeigen wollen, sehen Sie sich ein geeignetes 01:13:39.920 --> 01:13:40.780 daraus aus. 01:13:43.060 --> 01:13:46.760 Das ist nochmal die Vorlesung von heute im Rückblick. 01:13:46.900 --> 01:13:50.040 Ich will das nicht nochmal sagen, aber die Folien sehen Sie ja auch. 01:13:50.040 --> 01:13:53.120 Das war die Beweisidee und das haben wir gezeigt. 01:13:53.920 --> 01:13:59.280 Und beim nächsten Mal lernen Sie das dann in Aktion kennen, wie man so 01:13:59.280 --> 01:14:00.260 eine Reduktion macht. 01:14:00.520 --> 01:14:06.040 Und wirklich, machen Sie sich klar, was ist der Unterschied zwischen P 01:14:06.040 --> 01:14:07.140 und NP? 01:14:08.500 --> 01:14:11.760 Machen Sie sich klar, was ist der Sinn einer Transformation? 01:14:13.400 --> 01:14:14.460 Warum tun wir das? 01:14:15.200 --> 01:14:20.340 Es ist jetzt wahrscheinlich, wenn P ungleich NP ist, denn es ist nur 01:14:20.340 --> 01:14:23.240 so ein theoretisches Konstrukt, um diese Klassen zu trennen. 01:14:23.620 --> 01:14:30.640 Wenn sich aber herausstellen sollte, dass P gleich NP ist, weil 01:14:30.640 --> 01:14:35.620 irgendjemand für irgendein Problem, was NP-vollständig ist, dann meine 01:14:35.620 --> 01:14:40.240 deterministische Turing-Maschine in Polynomialzeit gebaut hat. 01:14:40.860 --> 01:14:46.660 Also zum Beispiel Satz mit einem Algorithmus in N hoch 17 löst. 01:14:47.740 --> 01:14:50.560 Dann wäre Satz in P auf einmal. 01:14:51.800 --> 01:14:56.500 Dann wäre alles, was in NP ist, automatisch in P. Dann würden wir aus 01:14:56.500 --> 01:15:01.440 diesem Algorithmus für Satz, würden wir Algorithmen in Polynomialzeit 01:15:01.440 --> 01:15:05.380 für alle Probleme in NP kriegen, indem wir sie erst durch, dann gucken 01:15:05.380 --> 01:15:08.440 wir, wie haben wir dann bewiesen, dass die auf Satz transformiert 01:15:08.440 --> 01:15:08.880 werden können. 01:15:08.880 --> 01:15:11.380 Wir schicken das erst durch diese Transformation von Satz von Cook, 01:15:11.440 --> 01:15:12.560 die wir gerade eben gemacht haben. 01:15:12.660 --> 01:15:14.280 Das geht in Polynomialzeit, keine Ahnung. 01:15:14.740 --> 01:15:15.560 Was habe ich jetzt gerade gesagt? 01:15:16.360 --> 01:15:18.700 N... egal. 01:15:20.920 --> 01:15:25.440 Lösen dann Satz in N hoch 17 und haben damit unser Problem in 01:15:25.440 --> 01:15:26.420 Polynomialzeit gelöst. 01:15:27.400 --> 01:15:32.760 Das heißt, diese Transformationen könnten potenziell sehr wichtig sein 01:15:32.760 --> 01:15:35.680 später, weil sie dann Teile von Algorithmen werden. 01:15:37.320 --> 01:15:41.700 Oder sehr wichtig für die Forschung und die Theorie, weil sie wirklich 01:15:41.700 --> 01:15:45.440 zeigen, dass es einen Unterschied gibt zwischen Lösungen verifizieren 01:15:45.440 --> 01:15:48.240 und Lösungen finden, in Polynomialzeit. 01:15:49.600 --> 01:15:50.800 Okay, damit entlasse ich Sie.