WEBVTT 00:09.490 --> 00:14.210 Heute beschäftigen wir uns mit NP-vollständigen Problemen. 00:15.050 --> 00:18.850 Ich will noch mal ganz kurz wiederholen, was wir das letzte Mal 00:18.850 --> 00:20.390 gelernt haben. 00:20.770 --> 00:23.970 Wir haben ja das letzte Mal mit dem sehr wichtigen Kapitel 00:23.970 --> 00:29.370 Komplexitätsklassen begonnen und da ging es um Folgendes. 00:35.670 --> 00:40.090 Wir wollen Probleme oder Sprachen entsprechend ihrer Komplexität 00:40.090 --> 00:42.230 klassifizieren. 00:42.610 --> 00:44.550 Deshalb Komplexitätsklassen. 00:51.000 --> 00:54.360 Und die wichtigen Klassen, die wir kennengelernt haben, sind P und NP 00:54.360 --> 00:56.380 und die werden uns auch weiter beschäftigen. 00:56.800 --> 00:59.820 Aber erst mal, was man braucht als Vorarbeit, noch mal ganz kurz 00:59.820 --> 01:00.800 zusammengefasst. 01:01.340 --> 01:06.420 Die erste Sache ist, wir sprechen hier immer über Sprachen, 01:06.420 --> 01:14.760 Entscheidbarkeit von Sprachen, Lösbarkeit innerhalb einer bestimmten 01:14.760 --> 01:20.940 Laufzeit, Entscheidbarkeit innerhalb einer bestimmten Laufzeit von 01:20.940 --> 01:21.400 Sprachen. 01:21.500 --> 01:25.580 Interessiert sind wir aber jetzt gerade in diesem Kapitel eigentlich 01:25.580 --> 01:28.860 daran, wie effizient sich ein Problem lösen lässt. 01:28.980 --> 01:32.000 Und deshalb müssen wir als allererstes die Verbindung herstellen 01:32.000 --> 01:34.620 zwischen Problemen und Sprachen. 01:34.700 --> 01:38.860 Das haben wir das letzte Mal gemacht und wir haben als allererstes 01:38.860 --> 01:47.810 immer Entscheidungsprobleme formuliert. 01:48.050 --> 01:51.670 Das heißt, ein Problem in der Formulierung, wie wir es hier 01:51.670 --> 01:55.150 betrachten, ist so ein Problem, das ist so eine Frage, die ist so 01:55.150 --> 01:59.270 formuliert, dass die richtige Lösung ja oder nein ist. 02:00.170 --> 02:03.790 Wie man daraus dann eine tatsächliche Lösung für das Problem bekommen 02:03.790 --> 02:06.070 kann, damit haben wir uns das letzte Mal schon beschäftigt. 02:06.370 --> 02:09.370 Also wir beschäftigen uns mit Entscheidungsproblemen, aber die 02:09.370 --> 02:13.390 Definitionen werden alle auf Basis von Sprachen gemacht. 02:13.550 --> 02:20.110 Also diese Verbindung, Entscheidungsproblem Pi, Sprache L müssen wir 02:20.110 --> 02:20.730 herstellen. 02:21.230 --> 02:25.250 Die Verbindung wird hergestellt erst mal, indem wir jede Instanz von I 02:25.250 --> 02:26.970 geeignet kodieren. 02:27.630 --> 02:29.450 Also über so ein Kodierungsschema 02:34.270 --> 02:36.370 S. 02:37.190 --> 02:39.490 Wir haben uns darüber unterhalten, was sind vernünftige 02:39.490 --> 02:43.010 Kodierungsschemata und was sind für uns sozusagen gleichwertige 02:43.650 --> 02:44.130 Kodierungsschemata. 02:44.770 --> 02:47.390 Und da muss man nur in Erinnerung behalten, polynomial, 02:51.090 --> 02:54.450 das eine lässt sich nur mit poly-, oder lässt sich mit höchstens 02:54.450 --> 02:59.790 polynomialen Overhead an Länge in das andere überführen. 02:59.930 --> 03:01.670 Also polynomial ist da das Schlagwort. 03:02.130 --> 03:04.230 Insofern, also wenn man sich einmal klargemacht hat, was ist ein 03:04.230 --> 03:07.410 vernünftiges Kodierungsschema, dann können wir jetzt einfach annehmen, 03:07.970 --> 03:09.450 wir betrachten ein solches. 03:10.070 --> 03:12.870 So und dann ist aber jetzt immer noch nicht, habe ich immer noch nicht 03:12.870 --> 03:17.950 gesagt, was ist denn die Sprache, die bezüglich des Kodierungsschema S 03:17.950 --> 03:19.490 zu Pi gehört. 03:19.590 --> 03:21.330 Und die Sprache, das ist 03:24.810 --> 03:34.240 gerade die Menge der Kodierungen von Ja-Instanzen. 03:50.740 --> 03:54.080 Also wenn wir die Verbindung herstellen, Entscheidungsproblem Sprache, 03:56.440 --> 04:00.400 heißt das konkret zu einer Instanz für das Entscheidungsproblem, 04:00.800 --> 04:02.980 kriegen wir über das Kodierungsschema ein Wort. 04:03.800 --> 04:07.000 Und die Sprache, die jetzt zu dem Entscheidungsproblem gehört, das 04:07.000 --> 04:10.920 sind gerade die Worte, die Kodierungen von Ja-Instanzen sind. 04:11.320 --> 04:12.600 Das ist mal das allererste. 04:15.500 --> 04:22.940 So und dann haben wir uns mit nicht-deterministischen Turing-Maschinen 04:22.940 --> 04:24.480 insbesondere beschäftigt. 04:26.180 --> 04:27.720 Also Turing-Maschinen. 04:38.810 --> 04:43.170 Gut, die deterministische Turing-Maschine, die kennen wir zur Genüge. 04:50.130 --> 04:54.650 Die Frage ist, wie arbeitet eine nicht-deterministische Turing 04:54.650 --> 04:55.130 -Maschine? 05:08.610 --> 05:12.910 Und das Modell, das wir hier betrachten, ist eines, wo der Nicht 05:12.910 --> 05:18.830 -Determinismus in Form einer ersten Stufe, einer zweistufigen 05:18.830 --> 05:21.630 Berechnung daherkommt, einem sogenannten Orakel. 05:31.900 --> 05:32.900 Erste Stufe, 05:36.500 --> 05:46.250 Orakel, das ist nicht-deterministisch. 05:47.230 --> 05:52.110 Und die zweite Stufe, eine normale deterministische 05:55.720 --> 05:56.400 Berechnung. 05:57.280 --> 06:01.380 Wie kann man sich diese erste Stufe, diese nicht-deterministische 06:01.380 --> 06:02.860 Berechnung vorstellen? 06:03.380 --> 06:06.100 Man kann sich vorstellen, dass einfach in nicht-deterministischer 06:06.100 --> 06:10.080 Weise, also nicht klar vorbestimmter Weise, irgendetwas aufs Band 06:10.080 --> 06:10.860 geschrieben wird. 06:12.020 --> 06:17.440 Da kennen wir Konvention, links neben die Eingabe geschrieben wird. 06:18.540 --> 06:21.640 Das kann für eine und dieselbe Eingabe, also bei verschiedenen 06:21.640 --> 06:24.500 Berechnungen, auch verschiedenes sein. 06:24.760 --> 06:27.920 Während bei einer deterministischen Berechnung natürlich bei einer und 06:27.920 --> 06:30.400 derselben Eingabe immer dasselbe passiert. 06:31.540 --> 06:34.680 In dieser ersten Stufe einer nicht-deterministischen Berechnung wird 06:34.680 --> 06:37.000 also einfach irgendwas neben die Eingabe geschrieben. 06:38.620 --> 06:43.800 Und danach folgt eine ganz normale deterministische Berechnung, wo 06:43.800 --> 06:50.240 also die Eingabe und diese Orakel, das in der ersten Stufe links 06:50.240 --> 06:53.980 daneben geschrieben wurde, angeschaut wird, irgendwas damit gemacht 06:53.980 --> 06:54.400 wird. 06:54.760 --> 07:00.940 Sozusagen Abfolge von Übergängen, die klar deterministisch bestimmt 07:00.940 --> 07:01.260 sind. 07:04.570 --> 07:07.410 Bei so einer nicht-deterministischen Turing-Maschine muss man noch 07:07.410 --> 07:10.330 mehr als bei einer deterministischen Turing-Maschine auch dazu sagen, 07:11.210 --> 07:16.570 wann denn jetzt eine Eingabe akzeptiert wird und was eigentlich die 07:16.570 --> 07:22.350 Zeitkomplexität einer nicht-deterministischen Turing-Maschine ist. 07:24.010 --> 07:27.670 Also wir achten weiter, die nicht-deterministische Turing-Maschine 07:29.900 --> 07:45.090 akzeptiert eine Eingabe X genau dann, wenn es mindestens eine 07:45.090 --> 07:46.790 akzeptierende Berechnung gibt. 07:46.970 --> 07:50.470 Also mindestens eine Berechnung gibt, die bei dieser Eingabe im 07:50.470 --> 07:53.150 akzeptierenden Endzustand Qj ändert. 08:21.180 --> 08:23.400 Eine Berechnung, das reicht. 08:25.400 --> 08:27.000 Und die akzeptiert 08:31.060 --> 08:37.560 Sprache L, wenn 08:43.020 --> 08:49.990 W aus L akzeptiert werden. 08:52.290 --> 08:54.310 Genau die W aus L akzeptiert werden. 08:55.870 --> 08:58.130 Und was nehmen wir jetzt als Laufzeit? 09:17.400 --> 09:22.720 Wenn wir eine konkrete Eingabe X betrachten, dann kann ja diesmal 09:22.720 --> 09:23.480 jenes passieren. 09:24.820 --> 09:27.780 Und wir betrachten jetzt als die Laufzeit, die die Turing-Maschine 09:27.780 --> 09:32.700 braucht, für ihre Berechnung bei der Eingabe X sozusagen den besten 09:32.700 --> 09:34.600 Fall, die beste Berechnung. 10:02.950 --> 10:06.410 Also von all den Berechnungen, die die Turing-Maschine durchführen 10:06.410 --> 10:11.190 kann bei Eingabe X, von einem ganz festen X, nehmen wir die kürzeste. 10:11.870 --> 10:15.530 Die gibt uns an so viele Schritte, das ist die Zeit für die Eingabe X. 10:16.270 --> 10:18.890 Was heißt das dann insgesamt für die Laufzeitfunktion 10:23.810 --> 10:27.870 einer nicht deterministischen Turing-Maschine? 10:30.570 --> 10:31.230 M. 10:32.350 --> 10:40.170 Laufzeitfunktion, das ist ja eine Funktion, die gehört zu M und die 10:40.170 --> 10:45.770 gibt für jede Eingabe Länge N sozusagen eine Anzahl von 10:45.770 --> 10:46.830 Berechnungsschritten. 10:47.950 --> 10:51.130 Da werden jetzt alle Eingaben der Länge N angeguckt. 10:51.490 --> 10:55.110 Für jede Eingabe der Länge N, was ist denn die Zeit, die gebraucht 10:55.110 --> 10:55.330 wird? 10:55.410 --> 10:59.030 Für die einzelne Eingabe ist das die kürzeste Berechnung, aber unter 10:59.030 --> 11:03.110 all diesen Zeiten dann die längste, der worst case. 11:23.450 --> 11:28.110 Für ein konkretes X der Länge N wissen wir, das ist die Zeit, die 11:28.110 --> 11:28.950 kürzeste Berechnung. 11:31.610 --> 11:38.870 Wenn wir jetzt den Funktionswert der Laufzeitfunktion angeben wollen 11:38.870 --> 11:42.530 zu N, dann gucken wir alle Eingaben der Länge N an, jeweils dafür die 11:42.530 --> 11:44.270 Zeit und davon den worst case. 11:47.910 --> 11:53.510 Wenn man diese Vorarbeit geleistet hat, dann kann man P und NP 11:53.510 --> 11:56.570 definieren, also P hätte man schon vorher definieren können, aber NP 11:56.570 --> 11:58.230 kann man jetzt definieren. 12:04.220 --> 12:07.400 Ich wollte jetzt ein besonders schönes P malen. 12:08.700 --> 12:23.850 Sprachen, für die es eine deterministische Turing-Maschine 12:28.770 --> 12:40.590 gibt, die genau diese Sprache entscheiden kann und deren 12:40.590 --> 12:46.130 Zeitkomplexität oder Laufzeitfunktion polynomial beschränkt ist. 12:47.650 --> 12:49.090 Und NP, 12:54.490 --> 12:57.350 da sieht die Definition fast genauso aus. 12:57.490 --> 13:01.410 Das einzige statt deterministisch steht da nicht deterministisch. 13:02.190 --> 13:13.050 Da liegen alle Sprachen drin, für die es eine polynomiale nicht 13:13.050 --> 13:22.420 deterministische Turing-Maschine gibt. 13:24.890 --> 13:34.150 Und jetzt ist die Frage, wie kann ich mir vorstellen, was da passiert 13:34.150 --> 13:38.050 oder was das heißt, es gibt für eine Sprache eine nicht 13:38.050 --> 13:40.750 deterministische polynomiale Turing-Maschine. 13:42.010 --> 13:45.230 Es gibt eine Turing-Maschine, die ist nicht deterministisch, die hat 13:45.230 --> 13:49.850 eine polynomiale Laufzeitkomplexität, um diese Sprache zu entscheiden. 13:50.670 --> 13:52.270 Und wie entscheidet sie die Sprache? 13:52.430 --> 13:56.710 Indem sie zumindest eine Berechnung angibt, für jedes Wort aus der 13:56.710 --> 14:02.530 Sprache, die im akzeptierenden Endzustand landet und natürlich nur 14:02.530 --> 14:05.410 polynomiale Zeit braucht. 14:05.670 --> 14:07.470 Und was heißt eine Berechnung angeben? 14:07.990 --> 14:11.330 Das heißt so eine Möglichkeit, dass sie irgendwas zusätzlich aufs Band 14:11.330 --> 14:16.330 schreibt und dann in der deterministischen Überprüfung der Eingabe und 14:16.330 --> 14:20.050 dem, was sie aufs Band geschrieben hat, dann dazu kommt, ja die 14:20.050 --> 14:23.270 Eingabe ist aus der Sprache oder eben ist nicht aus der Sprache. 14:24.190 --> 14:27.070 So, das hört sich bei Sprachen so ein bisschen abstrakt an. 14:27.170 --> 14:32.630 Was heißt das denn jetzt, ein zusätzliches Wort auf dem Band neben der 14:32.630 --> 14:36.930 Eingabe bei der Überprüfung irgendwie verwenden zu können? 14:38.510 --> 14:43.070 Leichter kann man sich das vorstellen bei den entsprechenden 14:43.070 --> 14:46.590 Problemen, Entscheidungsproblemen, die hinter den Sprachen liegen. 14:47.170 --> 14:49.870 So ein Entscheidungsproblem ist ein ganz konkretes Problem und das 14:49.870 --> 14:51.970 Beispiel, das wir hatten, ist Travelling Salesman. 14:52.670 --> 14:56.650 Da ist also bei einer konkreten Instanz, einer konkreten Eingabe, ein 14:56.650 --> 15:03.950 Graph gegeben mit Kantenlängen und irgendein Wert, irgendein 15:03.950 --> 15:04.630 Längewert. 15:06.090 --> 15:10.870 Und die Frage ist, gibt es in dem Graph eine Rundtour, die jeden 15:10.870 --> 15:14.110 Knoten genau einmal durchläuft und die eine Länge kleiner gleich dem 15:14.110 --> 15:15.330 vorgegebenen Wert hat. 15:16.250 --> 15:19.130 Und wenn das jetzt eine nicht deterministische Touringmaschine in 15:19.130 --> 15:23.130 polynomialer Zeit entscheiden kann, was bedeutet das? 15:23.910 --> 15:27.390 Das bedeutet, es gibt eine nicht deterministische Touringmaschine, die 15:27.390 --> 15:38.930 zumindest für jede einzelne Instanz von Travelling Salesman, wo die 15:38.930 --> 15:44.710 richtige Antwort ja ist, wirklich was angeben kann, was mir hilft, 15:45.210 --> 15:49.230 innerhalb polynomialer Zeit dieses Ja als Antwort zu geben. 15:51.130 --> 15:55.370 Und das, was da sozusagen zusätzlich als Hilfestellung angegeben wird, 15:55.470 --> 15:58.590 das kann man sich einfach vorstellen als einen Lösungsvorschlag. 16:01.130 --> 16:02.430 Also Travelling Salesman, 16:05.550 --> 16:12.230 kann man sich jetzt einen Lösungsvorschlag haben, also für eine 16:12.230 --> 16:14.250 Instanz, wo die richtige Antwort Ja ist. 16:15.210 --> 16:19.430 Tatsächlich eine Rundreise, deren Länge kleiner gleich dem 16:19.430 --> 16:20.810 vorgegebenen Wert ist. 16:21.870 --> 16:24.910 Dann kann das natürlich in polynomialer Zeit dann noch überprüft 16:24.910 --> 16:25.250 werden. 16:26.950 --> 16:29.970 Das heißt, es gibt dann wirklich so eine polynomialbeschränkte 16:29.970 --> 16:35.830 Berechnung, wo der erste Teil einfach Vorgabe dieses Lösungsvorschlags 16:35.830 --> 16:36.170 ist. 16:36.950 --> 16:40.270 Ein Lösungsvorschlag ist in der Länge auch nur polynomialbeschränkt, 16:40.330 --> 16:41.750 in der Größe des ganzen Graph. 16:42.450 --> 16:45.550 Also sozusagen dieses Orakel hinzuschreiben, das kostet auch nur 16:45.550 --> 16:46.490 Polynomialzeit. 16:47.350 --> 16:53.110 Und dann zu überprüfen, ist dieser Lösungsvorschlag tatsächlich eine 16:53.110 --> 16:56.290 Tour der Länge kleiner gleich dem vorgegebenen Wert. 16:56.890 --> 17:01.170 Das kann man sich leicht überlegen, geht natürlich auch in der 17:01.170 --> 17:05.390 Laufzeit die Polynomial in der Größe der Eingabelänge der Instanz, 17:05.490 --> 17:09.630 also Größe des Graphen und Längen hervorkommen. 17:11.950 --> 17:15.890 Das heißt also nicht deterministisch polynomial lösen von einem 17:15.890 --> 17:21.710 Entscheidungsproblem heißt eigentlich nicht mehr als verifizieren 17:21.710 --> 17:25.470 können, ob ein Lösungsvorschlag tatsächlich eine Lösung ist. 17:29.780 --> 17:33.880 Die Mächtigkeit hinter der nicht deterministischen Turingmaschine 17:33.880 --> 17:37.300 liegt darin, dass sie eben so einen Lösungsvorschlag einfach so 17:37.300 --> 17:41.300 kostenlos geben kann. 17:41.600 --> 17:45.060 Mit einem Aufwand, der gerade nur so groß ist, wie den 17:45.060 --> 17:46.780 Lösungsvorschlag hinzuschreiben. 17:48.140 --> 17:53.760 Und die große Frage ist jetzt, wie verhalten sich diese Klassen P und 17:53.760 --> 17:54.800 NP zueinander? 17:57.040 --> 18:01.440 Trivial ist, dass die Klasse P eine Teilmenge der Klasse NP ist. 18:02.280 --> 18:02.940 Das ist trivial. 18:04.180 --> 18:07.200 Wenn es eine deterministische Turingmaschine gibt, die polynomial 18:07.200 --> 18:10.720 beschränkt ist, um Sprache zu entscheiden, dann gibt es natürlich auch 18:10.720 --> 18:14.640 eine nicht deterministische Turingmaschine, die polynomial beschränkt 18:14.640 --> 18:14.860 ist. 18:15.940 --> 18:19.520 Was wir aber nicht wissen ist, ob das eine echte Teilmenge ist, ob P 18:19.520 --> 18:24.180 eine echte Teilmenge von NP ist oder ob P gleich NP ist. 18:25.460 --> 18:32.160 P gleich NP hieße, diese anscheinend deutlich größere Mächtigkeit 18:32.160 --> 18:35.480 einer nicht deterministischen Turingmaschine ist in Wirklichkeit gar 18:35.480 --> 18:36.540 nicht vorhanden. 18:37.760 --> 18:42.180 Bei endlichen Automaten wissen wir zumindest in Bezug auf, was 18:42.180 --> 18:45.320 überhaupt geht, sind die Modelle gleichmäßig. 18:45.760 --> 18:48.880 Und das ist nebenbei bemerkt bei Turingmaschinen genauso. 18:49.360 --> 18:52.360 Das werden wir später ein kleines bisschen mehr vertiefen oder 18:52.360 --> 18:54.680 vielleicht werden sie es in der Übung etwas mehr vertiefen. 18:54.820 --> 18:59.080 Also Berechenbarkeit, da ist Determinismus, Nicht-Determinismus oder 18:59.080 --> 19:00.940 da bringt der Nicht-Determinismus nicht mehr. 19:01.540 --> 19:03.980 Aber jetzt geht es hier um Laufzeit, um den Aufwand. 19:05.420 --> 19:10.680 Und da ist doch die Vermutung, dass eine nicht deterministische 19:10.680 --> 19:16.100 Turingmaschine doch deutlich mehr kann in der gleichen Laufzeit wie 19:16.100 --> 19:21.260 eine P ungleich NP ist. 19:21.740 --> 19:24.740 Aber die Frage ist, wie kann man das jetzt weiter eingrenzen? 19:26.020 --> 19:29.720 Also wenn P ungleich NP ist, dann gibt es irgendwelche Probleme, die 19:29.720 --> 19:33.880 sind in NP, aber nicht in P. Die würden wir gerne identifizieren. 19:34.280 --> 19:39.600 Um das hier zu beweisen, wäre das allemal gut, wenn wir so ein Problem 19:40.180 --> 19:44.520 identifizieren würden und beweisen könnten, das ist nicht in P. Ein 19:44.520 --> 19:47.500 Problem aus NP, das wir zeigen können, ist nicht in NP. 19:47.800 --> 19:53.200 Aber welches sind denn die Kandidaten, die sozusagen P und NP scharf 19:53.200 --> 19:53.720 trennen? 19:55.740 --> 19:59.060 Die Kandidaten sind irgendwie die, die am schwersten sind. 19:59.200 --> 20:02.020 Also die Probleme in NP, die am schwersten sind. 20:02.300 --> 20:06.440 Die zwar in NP liegen, aber irgendwie schwerer sind, mindestens 20:06.440 --> 20:08.880 genauso schwer wie alle anderen. 20:09.420 --> 20:12.000 Und das wollen wir jetzt formalisieren, was das heißt und dann auch 20:12.000 --> 20:14.760 ein erstes Problem dieser Art identifizieren. 20:16.060 --> 20:19.600 Also wir betrachten Probleme, die zu den schwersten Problemen in NP 20:19.600 --> 20:26.320 gehören und am schwersten heißt, also folgendermaßen gemeint jetzt 20:26.320 --> 20:32.840 erstmal, wenn so ein schwerstes Problem in NP trotzdem in P liegt, 20:33.520 --> 20:37.500 dann sollen wir dann den Schluss ziehen können, dann ist P gleich NP. 20:38.240 --> 20:41.700 Wenn selbst so ein schwerstes in P ist, okay, dann haben wir doch 20:41.700 --> 20:47.200 keinen Unterschied zwischen Problemen in NP und Problemen in P. Also 20:47.200 --> 20:49.340 Kandidaten, um P und NP zu trennen. 20:49.520 --> 20:53.580 Die Frage ist, wie kann man die formal sozusagen charakterisieren, 20:53.680 --> 20:55.900 diese Kandidaten, um P und NP zu trennen. 20:58.810 --> 21:01.370 Diese Kandidaten, die werden NP-vollständig heißen. 21:01.490 --> 21:03.930 Also die Definition, die wir jetzt verstehen müssen, ist die 21:03.930 --> 21:05.850 Definition der NP-Vollständigkeit. 21:10.130 --> 21:15.810 Dazu brauchen wir den Begriff einer polynomialen Transformation und 21:15.810 --> 21:19.010 wir definieren jetzt NP-Vollständigkeit oder Klasse der NP 21:19.010 --> 21:23.230 -Vollständigen Sprachen wieder auf der Ebene der Sprachen, obwohl wir 21:23.230 --> 21:24.690 im Hintergrund Probleme haben. 21:25.710 --> 21:28.010 Was ist eine polynomiale Transformation? 21:28.370 --> 21:36.170 Das ist eine Funktion, die Worte über einem Alphabet, Worte über einem 21:36.170 --> 21:40.730 anderen Alphabet zuordnet, in einer ganz bestimmten Weise. 21:41.830 --> 21:46.430 Eine polynomiale Transformation einer Sprache L1 über dem Alphabet 21:46.430 --> 21:52.030 Sigma 1 in eine Sprache L2 über einem anderen Alphabet Sigma 2. 21:52.550 --> 21:56.250 Das ist eine Funktion von Sigma 1-Stern nach Sigma 2-Stern mit 21:56.250 --> 21:57.490 folgenden Eigenschaften. 21:58.010 --> 21:59.190 Zwei Eigenschaften. 21:59.450 --> 22:04.230 Das erste, es existiert eine polynomiale deterministische Turing 22:04.230 --> 22:06.230 -Maschine, die F berechnen kann. 22:06.750 --> 22:11.470 Also das heißt, nicht mehr als um für jeden Eingang, also für jedes X, 22:11.550 --> 22:15.950 F von X zu berechnen, brauchen wir nur polynomiale Zeit in unserem 22:15.950 --> 22:21.770 ganz normalen Verständnis von Aufzeit einer Berechnung. 22:22.030 --> 22:28.630 Und das zweite entscheidende ist, für alle Worte aus Sigma 1-Stern 22:28.630 --> 22:37.210 gilt, wenn das Wort in der Sprache L1 ist, dann bildet F dieses Wort 22:37.210 --> 22:42.670 auf ein Wort aus der Sprache L2 ab und umgekehrt. 22:42.690 --> 22:48.550 Also Worte aus L1 werden genau auf die Worte aus L2 abgebildet. 22:49.910 --> 22:55.510 Also so eine polynomiale Transformation, das ist eine Funktion, die 22:55.510 --> 22:59.990 man in Polynomialzeit berechnen kann, die gerade die Worte der einen 22:59.990 --> 23:05.610 Sprache in Worte der anderen Sprache abbildet und umgekehrt. 23:06.770 --> 23:08.050 Es werden nur Worte 23:13.150 --> 23:18.070 aus L2 kommen, nur raus, wenn das Ausgangswort ein Wort aus L1 ist. 23:21.320 --> 23:26.520 Was wir dann schreiben ist, L1 ist polynomial transformierbar in L2. 23:27.240 --> 23:29.960 Das ist so ein rechtsoffenes Unendlich-Zeichen. 23:30.460 --> 23:35.140 Was man sich dahinter vorstellen kann ist, naja gut, das L1 ist 23:35.140 --> 23:36.940 mindestens so schwer wie das L2. 23:38.200 --> 23:41.800 L2 ist mindestens so schwer wie das L1, vielleicht sogar schwerer. 23:43.640 --> 23:47.960 Und jetzt heißt eine Sprache NP-vollständig, falls gilt, die Sprache 23:47.960 --> 23:55.220 ist in NP und für alle anderen Sprachen aus NP gilt, sie lassen sich 23:55.220 --> 23:58.840 polynomial in diese Sprache transformieren. 23:59.280 --> 24:00.380 Alle anderen Sprachen. 24:01.580 --> 24:07.700 Für alle anderen Sprachen gilt, ich kann so eine Funktion angeben, die 24:07.700 --> 24:13.420 zu brechen nur polynomiale Zeit erfordert und die so geartet ist, dass 24:13.420 --> 24:18.860 sie genau die Worte der einen Sprache in Worte einer Sprache L 24:18.860 --> 24:21.720 abbildet. 24:26.410 --> 24:29.930 Für Sprachen formuliert klingt das so ein bisschen abstrakt. 24:30.030 --> 24:34.410 Wir stellen uns jetzt diese Definition von polynomialer Transformation 24:34.410 --> 24:38.390 und NP-Vollständigkeit mal für Entscheidungsprobleme vor. 24:38.450 --> 24:40.110 Was das für Entscheidungsprobleme heißt. 24:40.610 --> 24:43.970 Auf der Ebene werden wir dann tatsächlich später auch immer arbeiten. 24:47.370 --> 24:51.770 Also wir formulieren polynomial transformierbar und NP-Vollständigkeit 24:51.770 --> 24:53.170 jetzt für Entscheidungsprobleme. 24:53.690 --> 24:56.970 Wir wissen ja, wie die Entscheidungsprobleme mit Sprachen zu tun 24:56.970 --> 24:57.250 haben. 25:00.070 --> 25:05.390 Ein Entscheidungsproblem P1 ist polynomial transformierbar in das 25:05.390 --> 25:07.370 Entscheidungsproblem P2. 25:08.270 --> 25:14.690 Wenn es eine Funktion gibt, die Instanzen von P1 abbildet auf 25:14.690 --> 25:18.430 Instanzen von P2 und die folgende zwei Eigenschaften hat. 25:18.750 --> 25:22.230 Erstmal, wir können die mit einem polynomialen Aufwand berechnen, 25:22.590 --> 25:23.230 diese Funktion. 25:24.670 --> 25:28.470 Und zweitens, das ist das Entscheidende, das gilt für alle Instanzen 25:28.470 --> 25:29.310 von P1. 25:30.050 --> 25:37.230 Wenn die Instanz Ja-Instanz ist, dann wird sie auf eine Ja-Instanz von 25:37.230 --> 25:39.870 P2 abgebildet und umgekehrt. 25:40.390 --> 25:45.190 Also genau die Ja-Instanzen von P1 werden durch diese polynomiale 25:45.190 --> 25:50.210 Transformation auf Ja-Instanzen von P2 abgebildet. 25:50.210 --> 25:55.330 Und dann schreiben wir P1 polynomial transformierbar auf P2. 25:56.890 --> 26:02.530 Was hilft uns das, wenn wir P1 polynomial auf P2 transformieren 26:02.530 --> 26:02.870 können? 26:04.050 --> 26:10.670 Angenommen, wir hätten einen ganz tollen Algorithmus, um P2 26:10.670 --> 26:13.370 entscheiden zu können. 26:24.040 --> 26:28.780 Wenn wir jetzt P1 polynomial transformieren können auf P2 und jetzt 26:28.780 --> 26:33.360 daran interessiert sind, für eine bestimmte Instanz von P1 zu 26:33.360 --> 26:35.140 entscheiden, ist das eine Ja-Instanz? 26:36.300 --> 26:38.200 Dann können wir folgendes machen. 26:39.720 --> 26:46.220 Wir transformieren die über die polynomiale Transformation in eine 26:46.220 --> 26:53.860 Instanz von P2, entscheiden dann mit unserem tollen Algorithmus für 26:53.860 --> 26:56.460 P2, ist das eine Ja-Instanz oder nicht? 26:57.880 --> 27:01.220 Und können aus der Antwort dann ableiten, ob unsere Ausgangsinstanz 27:01.220 --> 27:03.220 von P1 eine Ja-Instanz war oder nicht. 27:05.880 --> 27:16.760 Also wenn wir P2 polynomial entscheiden könnten, dann könnten wir dann 27:16.760 --> 27:18.560 auch P1 polynomial entscheiden. 27:21.980 --> 27:26.680 Aus dieser Überlegung wird dann auch klar, warum wir sozusagen die 27:26.680 --> 27:30.120 schwersten in NP gerade so definieren, wie es hier unten steht. 27:31.800 --> 27:33.880 Das sind diese NP-Vollständigen. 27:34.020 --> 27:36.900 Und wann ist ein Problem, ein Entscheidungsproblem NP-Vollständig? 27:37.120 --> 27:38.880 Na gut, erst mal, wenn es in NP liegt. 27:40.380 --> 27:45.520 Und wenn gilt, alle anderen Entscheidungsprobleme in NP lassen sich 27:45.520 --> 27:48.560 polynomial auf dieses transformieren. 27:49.200 --> 27:53.940 Das heißt also, mit dem super tollen Algorithmus von P könnte ich alle 27:53.940 --> 27:58.020 anderen Entscheidungsprobleme aus NP entscheiden. 27:59.720 --> 28:04.200 Also die Definition ist gerade so gewählt, dass tatsächlich gilt, wenn 28:04.200 --> 28:09.280 ich also das hier, dieses P, dieses NP-Vollständige Problem polynomial 28:09.280 --> 28:12.960 lösen könnte, dann könnte ich nach Definition auch alle anderen 28:12.960 --> 28:16.680 Entscheidungsprobleme in NP polynomial lösen. 28:16.880 --> 28:18.060 Dann wäre P gleich NP. 28:20.220 --> 28:24.900 Okay, jetzt müssen wir natürlich gucken, gibt es solche NP 28:24.900 --> 28:26.020 -Vollständigen Probleme? 28:28.540 --> 28:29.740 Welche sind das? 28:31.060 --> 28:33.760 Wie zeigt man, dass so ein Problem NP-Vollständig ist? 28:34.740 --> 28:37.560 Eine ganze Menge zu tun, für heute und später. 28:41.200 --> 28:45.300 Erst mal jetzt wieder zurück auf die Ebene unserer sauberen 28:45.300 --> 28:47.000 Definitionen, also Sprachebene. 28:47.360 --> 28:50.080 Das allererste, was man sich leicht klarmachen kann, ist, dass 28:50.080 --> 28:54.900 polynomiale Transformierbarkeit eine transitive Angelegenheit ist. 28:55.460 --> 29:02.400 Eine polynomiale Transformation von einer Sprache L1 in eine Sprache 29:02.400 --> 29:06.760 L2, ist ja so definiert, das ist einfach so eine Funktion, die 29:06.760 --> 29:11.140 irgendeinem Wort über dem Alphabet zu L1, ein Wort aus dem Alphabet 29:11.140 --> 29:16.100 von L2 zuordnet, polynomial berechnet werden kann und gerade die Worte 29:16.100 --> 29:19.160 aus L1 auf Worte aus L2 abbildet. 29:19.560 --> 29:21.700 Sowas kann man hintereinander ausführen. 29:22.280 --> 29:26.420 Wenn ich das von L1 nach L2 kann, mit einer ganz bestimmten 29:26.420 --> 29:31.020 polynomialen Transformation und von L2 nach L3 kann, mit einer ganz 29:31.020 --> 29:35.940 bestimmten polynomialen Transformation, dann kann ich das von L1 nach 29:35.940 --> 29:37.280 L3 auch machen. 29:39.180 --> 29:43.120 Die polynomiale Transformation, die mir das leistet, ist einfach die 29:43.120 --> 29:47.820 Hintereinanderausführung der polynomialen Transformationen von L1 nach 29:47.820 --> 29:49.160 L2 und L2 nach L3. 29:49.640 --> 29:50.480 Also das ist klar. 29:53.260 --> 29:55.900 Ganz klar, aber wichtig. 29:58.080 --> 30:04.760 Warum ist das wichtig, dass polynomiale Transformierbarkeit eine 30:04.760 --> 30:07.100 transitive Relation ist? 30:11.830 --> 30:18.330 Naja, weil ich dann folgern kann, wenn ich zwei Sprachen in NP habe. 30:18.990 --> 30:22.850 Die eine lässt sich in die andere polynomial transformieren und die 30:22.850 --> 30:24.030 ist NP-vollständig. 30:24.410 --> 30:27.450 Dann ist die andere Sprache auch NP-vollständig. 30:28.610 --> 30:35.510 Das ist eine deutliche Erleichterung für das, was wir immer mal machen 30:35.510 --> 30:35.870 wollen. 30:35.990 --> 30:39.250 Wir wollen dann später immer mal machen, dass wir für bestimmte 30:39.250 --> 30:43.910 Sprachen Probleme, Entscheidungsprobleme zeigen, dieses Problem ist NP 30:43.910 --> 30:44.610 -vollständig. 30:45.070 --> 30:49.230 Nach Definition müssten wir zeigen, alle anderen Probleme aus NP 30:49.230 --> 30:52.450 müssten sich polynomial auf dieses transformieren lassen. 30:53.670 --> 30:57.730 Alle anderen Probleme, das sind verdammt viele, unendlich viele. 30:58.670 --> 31:03.230 Mit diesem Korollar, was nur darauf basiert, dass polynomiale 31:03.230 --> 31:08.730 Transformierbarkeit transitiv ist, reicht es, wenn wir ein NP 31:08.730 --> 31:12.090 -vollständiges Problem, also ein Problem, von dem wir zu dem Zeitpunkt 31:12.090 --> 31:16.690 wissen, das ist NP-vollständig, polynomial transformieren auf dieses 31:16.690 --> 31:20.450 neue Problem, von dem wir beweisen wollen, das ist NP-vollständig. 31:21.970 --> 31:26.410 Um zu zeigen, dass ein Entscheidungsproblem NP-vollständig ist, ein 31:26.410 --> 31:29.750 Entscheidungsproblem Pi, brauchen wir in Zukunft nur folgendermaßen 31:29.750 --> 31:30.430 vorzugehen. 31:30.770 --> 31:33.250 Wir beweisen erstens, das Problem ist in NP. 31:33.810 --> 31:37.770 Wir werden sehr schnell merken, das ist so typischerweise der harmlose 31:37.770 --> 31:40.310 Teil des Beweises. 31:40.750 --> 31:45.790 Und dann zeigen wir in einem zweiten Schritt, für ein Problem, von dem 31:45.790 --> 31:50.050 wir schon wissen, es ist NP-vollständig, dass es polynomial 31:50.050 --> 31:51.690 transformierbar ist auf unseren Pi. 31:52.390 --> 31:56.610 Nur für ein NP-vollständiges Problem müssen wir so eine polynomial 31:56.610 --> 32:01.950 berechenbare Funktion f angeben, die gerade die Jahrbeispiele von Pi' 32:02.110 --> 32:04.970 genau auf die Jahrbeispiele auf Pi abbildet. 32:06.790 --> 32:09.430 Das Problem ist, irgendwann müssen wir mal anfangen. 32:10.170 --> 32:13.530 Irgendwann müssen wir mal ein erstes NP-vollständiges Problem haben, 32:13.710 --> 32:16.710 um für weitere beweisen zu können, sie sind NP-vollständig. 32:17.270 --> 32:21.090 Und dieses erste NP-vollständige Problem, das lernen wir heute kennen 32:21.090 --> 32:24.870 und für das zeigen wir heute eben auch, dass es NP-vollständig ist. 32:25.030 --> 32:31.450 Irgendwann muss man mal den harten Weg gehen und zeigen, alle anderen 32:31.450 --> 32:36.330 Probleme aus NP lassen sich polynomial auf dieses transformieren. 32:38.950 --> 32:41.970 Bisher wissen wir noch für kein einziges Problem, dass es NP 32:41.970 --> 32:42.910 -vollständig ist. 32:43.350 --> 32:45.890 Also wir wissen es natürlich, weil andere Leute uns gesagt haben, 32:45.970 --> 32:47.910 Travelling Salesman ist NP-vollständig und anderes. 32:47.990 --> 32:51.370 Aber hier in der Vorlesung haben wir noch von keinem einzigen, das 32:51.370 --> 32:52.970 wirklich nachweisen können. 32:53.210 --> 32:54.010 Also machen wir das heute. 32:55.090 --> 32:59.390 Und das erste NP-vollständige Problem, also tatsächlich auch das erste 32:59.390 --> 33:05.930 Problem, für das bewiesen wurde 1971 von Stephen Cook, dass es NP 33:05.930 --> 33:10.050 -vollständig ist, ist das Erfüllbarkeitsproblem SAT. 33:10.470 --> 33:16.010 Also SAT ist ganz wichtig, weil es das erste NP-vollständige Problem 33:16.010 --> 33:18.530 ist, aber auch aus vielen anderen Gründen. 33:18.970 --> 33:23.450 Das klingt sehr... Erfüllbarkeitsproblem klingt sehr abstrakt, aber 33:23.450 --> 33:30.710 das hat ganze Menge Anwendungen im Softwarebereich etwa. 33:33.290 --> 33:36.590 So, wie sieht das SAT-Problem aus? 33:36.590 --> 33:46.310 Das SAT-Problem, dazu gehören gute Variablen, U1 bis UM, die in 33:46.310 --> 33:48.730 unnegierter und negierter Form vorkommen können. 33:49.790 --> 33:53.830 Unnegierte Form schreiben wir so, einfach UI, und die negierte Form 33:53.830 --> 33:56.610 schreiben wir UI mit einem Strich oben drüber. 33:58.630 --> 34:01.910 Und diese Variablen in negierter und unnegierter Form nennt man auch 34:01.910 --> 34:02.510 Literale. 34:05.150 --> 34:08.150 Und eine Menge von Klauseln. 34:08.290 --> 34:11.490 Und eine Menge von Klauseln, das sind einfach Konstrukte über solchen 34:11.490 --> 34:15.510 Literalen, die so aussehen, sie sind einfach oder-Verbindungen von 34:15.510 --> 34:18.190 einer endlichen Menge von Literalen. 34:18.930 --> 34:25.310 Also eine Klausel sieht so aus, Y1 oder Y2 usw. 34:25.490 --> 34:26.410 oder Ys. 34:26.710 --> 34:31.630 Und das YI ist so ein Literal, also eine Variable in entweder 34:31.630 --> 34:33.550 unnegierter oder negierter Form. 34:34.210 --> 34:37.150 Und man könnte auch einfach wahr oder falsch noch dazunehmen. 34:38.770 --> 34:42.930 Und was uns immer interessiert ist, wenn wir so eine Instanz von SAT 34:42.930 --> 34:46.450 gegeben haben, also Menge von Variablen, Menge von Klauseln über 34:46.450 --> 34:52.230 dieser Variablenmenge, ob es eine Wahrheitsbelegung gibt für diese 34:52.230 --> 34:52.850 Instanz. 34:53.090 --> 34:59.370 Das heißt also, ob es eine Funktion gibt, die jedem, jeder Variable 34:59.370 --> 35:03.270 einen Wert, Wahrheitswert, wahr oder falsch zuordnet. 35:03.530 --> 35:09.410 Und die gerade so ist, dass alle diese Klauseln, die zur Instanz 35:09.410 --> 35:12.670 gehören, gleichzeitig wahr werden. 35:14.590 --> 35:20.850 Also das SAT-Problem folgendermaßen definiert, gegeben ist eine Menge 35:20.850 --> 35:24.990 von Variablen und eine Menge von Klauseln über diesen Variablen. 35:25.330 --> 35:29.810 Und die Frage ist, gibt es eine Wahrheitsbelegung der Variablen, jeder 35:29.810 --> 35:34.110 einzelne Variable wird wahr oder falsch zugeordnet, so dass für alle 35:34.110 --> 35:38.590 Klauseln gilt, sie werden gleichzeitig wahr, haben gleichzeitig den 35:38.590 --> 35:39.990 Wahrheitswert wahr. 35:41.970 --> 35:43.510 Schauen wir uns mal ein Beispiel an. 35:45.170 --> 35:46.890 Also hier, Beispiel. 35:47.250 --> 35:52.770 Unsere SAT-Instanz besteht aus zwei Variablen u1 und u2 und zwei 35:52.770 --> 35:53.550 Klauseln. 35:53.910 --> 35:59.450 Die eine ist u1 oder nicht u2 und die andere ist nicht u1 oder u2. 36:00.390 --> 36:06.150 Frage ist, ist diese Instanz eine Ja-Instanz oder eine Nein-Instanz 36:06.150 --> 36:06.770 für SAT? 36:07.810 --> 36:10.930 Ja-Instanz, wenn wir jetzt eine Wahrheitsbelegung für u1 und u2 36:10.930 --> 36:14.430 angeben können, die diese beiden Klauseln wahr macht. 36:14.910 --> 36:17.790 Wenn wir keine angeben könnten, dann wäre es eine Nein-Instanz, aber 36:17.790 --> 36:19.090 wir können hier eine angeben. 36:19.830 --> 36:27.550 Wenn wir u1 wahrsetzen und u2 wahrsetzen, dann wird diese erste 36:27.550 --> 36:33.830 Klausel erfüllt, über den Wahrheitswert von u1 und die zweite Klausel 36:33.830 --> 36:35.970 erfüllt durch den Wahrheitswert von u2. 36:36.390 --> 36:39.710 Das heißt also, das ist eine Wahrheitsbelegung der Variablenmenge, die 36:39.710 --> 36:41.790 alle Klauseln der Instanz wahr macht. 36:44.370 --> 36:46.670 Irgendwie noch mal zwei weitere Beispiele. 36:47.370 --> 36:53.350 Größere Beispiele, also Sie haben hier diese fünf Variablen a, b, c, 36:53.570 --> 36:57.470 d, e und Sie haben folgende Klauseln und diese Klauseln sehen also 36:57.470 --> 37:02.490 immer so aus, das sind einfach so ODA-Verbindungen von unigierten oder 37:02.490 --> 37:03.590 negierten Variablen. 37:05.530 --> 37:11.730 Die erste ist c oder nicht d, die zweite ist nicht a oder b oder nicht 37:11.730 --> 37:18.330 c oder d oder e und die dritte ist nicht c oder d. 37:19.550 --> 37:21.210 Hier steht, die wäre lösbar. 37:21.830 --> 37:26.250 Also es gibt eine Wahrheitsbelegung, die alle diese Klauseln wahr 37:26.250 --> 37:28.450 macht, eine Wahrheitsbelegung dieser Variablen. 37:29.050 --> 37:31.890 Jetzt muss ich mal hingucken, oder sieht irgendjemand von Ihnen, was 37:31.890 --> 37:32.470 das wäre? 37:42.420 --> 37:44.380 Ja, das ist ziemlich einfach eine zu sehen. 37:44.960 --> 37:49.640 Also ich sehe da c wahrzusetzen, würde ich immer diese Klausel wahr 37:49.640 --> 37:54.580 machen und wenn ich außerdem noch d auf wahr setze, dann wird diese 37:54.580 --> 37:58.380 Klausel, diese lange in der Mitte wahr und auch diese hintere wahr. 37:59.160 --> 38:04.900 Also alle Wahrheitsbelegungen, wo c und d wahrgesetzt werden, an den 38:04.900 --> 38:08.040 Variablen irgendwie wahr oder falsch gesetzt werden, ist eine 38:08.040 --> 38:09.620 erfüllende Wahrheitsbelegung. 38:11.120 --> 38:13.840 Und hier haben wir noch eine weitere Instanz von Satz. 38:14.520 --> 38:19.120 Die Variablen sind a, b, c, die Klauselmenge ist a oder b, nicht a, 38:19.960 --> 38:21.860 nicht b oder c, nicht c. 38:22.460 --> 38:26.940 Da kann man recht leicht argumentieren, dass die nicht erfüllbar ist, 38:27.340 --> 38:29.620 weil man einfach sehr schnell Widersprüche bekommt. 38:30.340 --> 38:34.380 Also um die zu erfüllen, müsste man a falsch setzen, weil wir hier 38:34.380 --> 38:36.840 eine Klausel haben, die heißt einfach nur nicht a. 38:37.760 --> 38:42.240 Damit nicht a wahr wird, muss a falsch gesetzt werden. 38:42.620 --> 38:46.060 Und hier hinten, die können wir auch nur wahr machen, das ist nicht c, 38:46.380 --> 38:48.020 indem wir c falsch setzen. 38:48.020 --> 38:54.420 So, wenn wir c falsch setzen, dann können wir die Klausel davor nur 38:54.420 --> 38:58.820 wahr machen, indem wir b falsch setzen, damit eben nicht b wahr wird. 38:59.880 --> 39:02.720 Dann ist aber klar, diese erste Klausel ist nicht mehr erfüllbar. 39:03.980 --> 39:08.220 Wegen dem hier müssen wir a falsch setzen und wegen dem hier, den 39:08.220 --> 39:11.580 beiden hier, müssen wir b falsch setzen, also a oder b kann nicht wahr 39:11.580 --> 39:12.180 werden. 39:14.040 --> 39:21.560 Okay, so, natürlich zu argumentieren, so eine konkrete Instanz ist 39:21.560 --> 39:26.680 nicht lösbar, ist ein bisschen aufwendiger, als zu argumentieren, so 39:26.680 --> 39:29.140 eine konkrete Instanz wie diese hier ist lösbar. 39:29.280 --> 39:31.360 Das, was ich da gemacht habe, ist genau das, was eine nicht 39:31.360 --> 39:33.320 -statementistische Turing-Maschine macht. 39:33.420 --> 39:36.760 Ich habe ihnen gesagt, ach, nehmen Sie doch folgende Belegung und dann 39:36.760 --> 39:40.000 gesagt, sehen Sie, und wenn Sie die nehmen, dann werden all diese 39:40.000 --> 39:41.040 Klauseln wahr. 39:41.640 --> 39:46.680 Und bei einer ziemlich großen oder schwierig aussehenden Instanz ist 39:46.680 --> 39:50.780 dieses, ach, nehmen Sie doch folgende Belegung, das ist eben dieses 39:50.780 --> 39:53.640 Orakel, vielleicht nicht so leicht zu bekommen. 39:54.700 --> 39:56.000 Darum geht es jetzt. 39:58.080 --> 40:05.680 So, wir zeigen jetzt, dieses Problem, Satz, Erfüllbarkeitsproblem, ist 40:05.680 --> 40:06.720 NP -vollständig. 40:07.740 --> 40:09.960 Die Frage ist, wie kann man das jetzt beweisen? 40:11.440 --> 40:16.340 Wir müssen den harten Weg gehen und dies beweisen nach Definition von 40:16.340 --> 40:17.660 NP -Vollständigkeit. 40:17.820 --> 40:22.140 Und nochmal, was heißt nach Definition, Sprache oder so ein 40:22.140 --> 40:24.140 Entscheidungsproblem ist NP-vollständig? 40:25.120 --> 40:30.180 Das heißt, wir können für jede beliebige andere Sprache oder jedes 40:30.180 --> 40:34.720 beliebige andere Entscheidungsproblem aus NP eine Transformation 40:34.720 --> 40:41.780 angeben, deren Berechnung nur polynomialen Aufwand erfordert und die 40:41.780 --> 40:50.060 gerade so geeignet ist, dass sie die Worte jeweils dieser anderen 40:50.060 --> 40:55.640 Sprache in Worte unserer Satzsprache abbildet. 40:55.640 --> 41:02.240 Oder eben jetzt auf Instanzebene, die genau die Ja-Instanzen eines 41:02.240 --> 41:09.060 anderen Problems aus NP auf Ja-Instanzen von Satz abbildet. 41:09.800 --> 41:14.000 Um das beweisen zu können, um diese polynomiale Transformation zu 41:14.000 --> 41:18.720 bauen, das muss ja so eine sehr generische Transformation sein, die es 41:18.720 --> 41:21.880 sozusagen für alle Entscheidungsprobleme oder alle Sprachen aus NP 41:21.880 --> 41:28.260 tut, dürfen wir nur das eine verwenden, dass wir eben jede einzelne 41:28.260 --> 41:36.120 Sprache aus NP in Polynomialzeit überführt in die Satzsprache, dass 41:36.120 --> 41:41.480 die Worte aus der Sprache in Worte aus Ja-Instanzen oder Codierungen 41:41.480 --> 41:44.060 von Ja-Instanzen von Satz abgebildet werden. 41:45.360 --> 41:49.440 Das zu konstruieren können wir jetzt nur verwenden, dass die Sprachen 41:49.440 --> 41:50.840 in NP liegen. 41:57.080 --> 42:00.180 Okay, aber jetzt nochmal zu unserem Schema. 42:00.720 --> 42:04.860 Es sind ja immer zwei Sachen zu beweisen, um zu zeigen, das 42:04.860 --> 42:10.080 Entscheidungsproblem ist NP-vollständig, dass es in NP liegt und dann 42:10.080 --> 42:13.600 eben, dass sich alle anderen darauf transformieren lassen, polynomial. 42:14.080 --> 42:15.720 Also das erste Mal, Satz ist in NP. 42:16.660 --> 42:20.900 Das habe ich Ihnen eben schon anhand der Instanzen im Prinzip, anhand 42:20.900 --> 42:23.860 der Beispielen erläutert, dass Satz in NP ist. 42:23.860 --> 42:29.400 Sie müssen nur für irgendeine Instanz von Satz und irgendeine 42:29.400 --> 42:35.940 vorgegebene Wahrheitsbelegung in Polynomialzeit überprüfen können, 42:36.180 --> 42:39.460 dass die Wahrheitsbelegung tatsächlich alle Klauseln wahrmacht. 42:41.560 --> 42:44.620 Also einfach einsetzen, in alle Klauseln nachgucken, fertig. 42:45.560 --> 42:49.420 Das geht in O von Anzahl der Variablen mal Anzahl der Klauseln. 42:50.340 --> 42:53.480 Und das Zweite, das ist das, was wir jetzt aufwendig beweisen. 42:55.080 --> 43:01.380 Für jede Sprache aus L ist L transformierbar auf die Sprache für Satz. 43:01.580 --> 43:06.420 Sprache für Satz nochmal, die Codierung der Ja-Instanzen von Satz mit 43:06.420 --> 43:08.520 Hilfe von einem sinnvollen Codierungsschema. 43:10.420 --> 43:11.980 Wie ich eben schon sagte, 43:17.750 --> 43:21.130 können wir dafür nur das verwenden, was wir hier unten haben, dass für 43:21.130 --> 43:25.510 jede dieser einzelnen Sprachen eine nicht deterministische polynomial 43:25.510 --> 43:27.770 beschränkte Turing-Maschine existiert. 43:30.230 --> 43:35.830 Wir müssen angeben, also für jede beliebige Sprache eine polynomiale 43:35.830 --> 43:42.190 Transformation F und ein L, wenn L die Sprache ist, die so ist, 43:45.420 --> 43:50.700 die X aus L werden genau auf Wörter der Sprache zu Satz abgebunden. 43:52.940 --> 43:56.440 Und wir können benutzen, dass es eine nicht deterministische Turing 43:56.440 --> 44:00.940 -Maschine M zu L gibt, die L in polynomialer Laufzeit erkennt. 44:01.900 --> 44:03.760 Da müssen wir genauer hingucken. 44:04.200 --> 44:05.180 Was heißt das denn? 44:05.220 --> 44:09.040 Es gibt eine nicht deterministische polynomiale Turing-Maschine zu L. 44:10.880 --> 44:13.720 Na gut, so eine Turing-Maschine, die sieht so aus, wie sie immer 44:13.720 --> 44:18.120 aussieht, Anzahl der Zustände, Eingabealphabet, Plank-Symbol, 44:18.520 --> 44:23.100 Bandalphabet, Anfangszustand, den nennen wir Q0, Übergangsfunktion, 44:23.240 --> 44:27.280 Delta, die beiden Stopp-Zustände, den akzeptierenden Qja und den nicht 44:27.280 --> 44:28.420 akzeptierenden Qnein. 44:29.980 --> 44:33.680 Und das zweite, was wir wissen, ist eben die Laufzeitfunktion zu 44:33.680 --> 44:38.380 dieser Turing-Maschine T von M ist polynomial beschränkt, also es gibt 44:38.380 --> 44:43.960 ein Polynom P, sodass T von M, Tm von n kleiner gleich P von n ist. 44:46.220 --> 44:52.480 OBDA nehmen wir an, das ist ein Polynom, was mindestens für n, 44:52.540 --> 44:55.200 mindestens n Wörter braucht. 44:58.210 --> 45:03.250 So, schauen wir uns also mal eine beliebige Instanz der Länge an. 45:05.730 --> 45:10.970 Das heißt dann also, für unsere Turing-Maschine M zu unserer Sprache 45:10.970 --> 45:17.390 L, bei einer akzeptierenden Berechnung für diese Eingabe ist die 45:17.390 --> 45:19.830 Anzahl der Berechnungsschritte beschränkt durch P von n. 45:23.100 --> 45:24.280 Was heißt das? 45:24.420 --> 45:27.780 Das heißt, wenn man sich anguckt, was auf dem Band der Turing-Maschine 45:27.780 --> 45:34.720 so passiert, dass höchstens die Zellen zwischen, in der Mitte ist die 45:34.720 --> 45:34.940 0. 45:35.080 --> 45:39.240 Zelle, dass nur die Zellen zwischen minus P von n. 45:39.300 --> 45:40.760 Zelle und P von n. 45:40.840 --> 45:45.360 Zelle überhaupt beteiligt sein können bei der Berechnung. 45:47.240 --> 45:53.760 Also nur das, was zwischen minus P von n und P von n plus 1, 1 für die 45:53.760 --> 45:54.180 0. 45:54.280 --> 45:59.380 Zelle, auf dem Band steht, hat überhaupt was mit der Berechnung zu 45:59.380 --> 45:59.640 tun. 46:02.260 --> 46:08.700 So, und außerdem wissen wir über unsere akzeptierende Berechnung zur 46:08.700 --> 46:16.260 beliebig vorgegebenen Sprache L aus NP, wie die deterministische Stufe 46:16.260 --> 46:16.840 aussieht. 46:19.380 --> 46:23.680 Nämlich in der deterministischen Stufe ist zu jedem Zeitpunkt klar, 46:24.060 --> 46:24.800 was Sache ist. 46:26.220 --> 46:31.020 Klar festgelegt, was der Bandinhalt all dieser beteiligten Zellen ist 46:31.020 --> 46:34.100 und wir brauchen tatsächlich nur noch von der Zelle minus P von n bis 46:34.100 --> 46:37.620 Zelle P von n plus 1 zu schauen. 46:38.540 --> 46:43.080 Das ist für jeden Zeitpunkt klar, in welchem Zustand die nicht 46:43.080 --> 46:44.760 -deterministische Turing-Maschine ist. 46:45.540 --> 46:48.880 Das ist für jeden Zeitpunkt klar, wo der Lese-Schreibkopf ist. 46:50.740 --> 46:54.800 Was wir jetzt machen müssen, ist eben diese deterministische 46:54.800 --> 47:00.060 Berechnung, die nur polynomiale Zeit braucht, vollständig beschreiben 47:00.060 --> 47:04.700 durch Variablen und Klauseln. 47:11.500 --> 47:14.900 So, und dafür führen wir jetzt bestimmte Variablen ein und die haben 47:14.900 --> 47:16.140 alle eine Bedeutung. 47:17.780 --> 47:22.820 Zunächst mal, wir gehen davon aus, unsere Zustandsmenge sieht so aus, 47:22.920 --> 47:29.480 das ist Q0 bis QR. 47:30.380 --> 47:36.460 Q0 ist der Anfangszustand, Q1 ist der akzeptierende Stopp-Zustand, Q2 47:36.460 --> 47:41.660 ist der nicht-akzeptierende Stopp-Zustand, also Qn, und dann haben wir 47:41.660 --> 47:42.820 noch Q3 bis QR. 47:44.440 --> 47:48.800 Und genauso nummerieren wir die Symbole des Bandalphabets systematisch 47:48.800 --> 47:49.200 durch. 47:50.480 --> 47:51.140 0. 47:51.300 --> 47:58.180 Symbol, S0, das ist das Plank-Symbol, und dann S1 bis SL sind die 47:58.180 --> 48:03.820 restlichen Symbole, vorausgesetzt unser Bandalphabet hat L plus 1 48:03.820 --> 48:04.480 Zeichen. 48:05.340 --> 48:08.160 So, und jetzt führen wir folgende Variablen ein. 48:08.160 --> 48:13.260 Variablen, die eine bestimmte Bedeutung haben, nämlich Variable wird 48:13.260 --> 48:21.200 wahrgesetzt, korrespondiert zu einer ganz bestimmten Situation, die in 48:21.200 --> 48:23.500 der Brechung der Turing-Maschine auftritt. 48:24.600 --> 48:29.640 Erstmal Variablen, die im Prinzip zu den Zuständen gehören, in denen 48:29.640 --> 48:31.100 die Turing-Maschine sein kann. 48:31.800 --> 48:37.080 Die heißen Q, Zustandsmenge Q, und sind von zwei Dingen abhängig, von 48:37.080 --> 48:43.220 dem Zeitpunkt und von dem Zustand. 48:44.140 --> 48:48.020 Wir haben P von N plus 1 Zeitpunkte in unserer Berechnung, und wir 48:48.020 --> 48:54.880 haben R plus 1 Zustände, das heißt, es gibt Variablen Q von I, K. 48:54.880 --> 49:04.640 Und Q von I, K ist wahr, hat für uns die Bedeutung zum Zeitpunkt I der 49:04.640 --> 49:04.920 Berechnung. 49:06.360 --> 49:09.020 Ich meine hier jetzt immer, wenn ich Berechnung sage, den 49:09.020 --> 49:13.360 deterministischen Anteil, deshalb steht hier genauer Überprüfungsphase 49:13.360 --> 49:14.660 der Turing-Maschine. 49:14.660 --> 49:19.760 Und Zeitpunkt I ist die Turing-Maschine im Zustand QK. 49:24.260 --> 49:27.160 Natürlich haben wir jetzt für alle möglichen Zeitpunkte, in denen die 49:27.160 --> 49:30.560 Turing -Maschine sein kann, und alle möglichen Zustände, so eine 49:30.560 --> 49:31.080 Variable. 49:33.580 --> 49:36.680 Wenn wir das einmal verstanden haben, für die Variablen, die zu den 49:36.680 --> 49:39.480 Zuständen gehören, dann können wir das für die anderen Variablen, die 49:39.480 --> 49:41.740 wir jetzt einführen, ein bisschen schneller machen. 49:44.020 --> 49:49.120 Was gehört denn noch zu einem bestimmten Schritt in der 49:49.120 --> 49:53.960 Überprüfungsphase, neben dem Zustand, in dem sich gerade die Turing 49:53.960 --> 49:55.060 -Maschine befindet? 49:55.580 --> 50:02.360 Naja, es gehört dazu, an welcher Stelle der Lese-Schreibkopf steht und 50:02.360 --> 50:06.620 was an einer bestimmten Position auf dem Band steht. 50:06.620 --> 50:07.540 Welches Symbol? 50:07.840 --> 50:08.400 Die beiden Dinge. 50:08.540 --> 50:10.300 Und dafür haben wir jeweils jetzt auch Variablen. 50:10.940 --> 50:19.740 Also, wir haben Variablen H, H wie Kopf, Head, abhängig von einem 50:19.740 --> 50:28.060 Zeitpunkt I, der zwischen 0 und p von n ist, und einer Position J, die 50:28.060 --> 50:33.040 zwischen minus p von n und plus p von n plus 1 ist, also die Position, 50:33.220 --> 50:39.280 die überhaupt relevant sind, und H von I, J war heißt, zum Zeitpunkt 50:39.280 --> 50:44.780 I, in der Überprüfungsphase, steht der Lese-Schreibkopf an Position J 50:44.780 --> 50:45.860 des Bandes. 50:48.820 --> 50:56.200 Und das dritte sind Variablen S, abhängig von I, I gehört wieder zu 50:56.200 --> 51:03.880 einem Zeitpunkt, J, J gehört wieder zu einer Position am Band, und K, 51:04.500 --> 51:12.060 K gehört zu einem der möglichen Bandsymbole, S, I, J, K ist wahr, hat 51:12.060 --> 51:16.820 die Bedeutung zum Zeitpunkt I der Überprüfungsphase, ist der 51:16.820 --> 51:22.020 Bandinhalt an der Position J gerade das Symbol S, K. 51:24.820 --> 51:30.920 Mit den Variablen können wir alle Situationen während der 51:30.920 --> 51:33.720 Überprüfungsphase beschreiben. 51:35.400 --> 51:40.280 Das, was zu einem bestimmten Zeitpunkt I der Überprüfungsphase gerade 51:40.280 --> 51:43.960 Sache ist, beschreiben wir, indem wir die genau dazugehörigen 51:43.960 --> 51:46.520 Variablen wahrsetzen. 51:49.280 --> 51:54.360 Jetzt bauen wir Klauseln, um tatsächlich das, was während der 51:54.360 --> 51:57.800 Überprüfungsphase passieren kann, vollständig zu beschreiben. 52:00.200 --> 52:04.220 Also wie die ganze Berechnung aussieht, vollständig zu beschreiben. 52:14.330 --> 52:16.970 Bevor wir das machen, schauen wir uns jetzt an, was wir mit diesen 52:16.970 --> 52:18.070 Variablen machen können. 52:19.510 --> 52:20.350 Also, 52:25.620 --> 52:29.300 wir können mit diesen Variablen eben jeden einzelnen Zeitpunkt 52:29.300 --> 52:29.800 beschreiben. 52:31.160 --> 52:33.120 Und wie sieht jetzt die Überprüfungsphase aus? 52:33.300 --> 52:41.480 Zum Zeitpunkt 0 sei der Bandinhalt einfach nur die Eingabe stehend auf 52:41.480 --> 52:42.800 den Stellen 1 bis N. 52:46.040 --> 52:52.000 Das Orakel B stehend auf den Stellen minus 1 bis minus Länge von W. 52:52.900 --> 52:57.320 Das Ganze spielt sich ab zwischen minus P von N und plus P von N plus 52:57.320 --> 52:57.820 1. 52:59.120 --> 53:00.640 Und ansonsten stehen da nur Planks. 53:07.750 --> 53:10.670 Wenn wir jetzt eine beliebige Wahrheitsbelegung dieser Variablen 53:10.670 --> 53:13.710 betrachten würden, irgendeine beliebige, dann muss sie nicht unbedingt 53:13.710 --> 53:18.150 etwas Sinnvolles in Bezug auf eine Berechnung ausdrücken. 53:18.870 --> 53:24.530 Denn zum Beispiel, wenn wir sowohl QIK als auch QIL wahrsetzen würden, 53:25.810 --> 53:29.290 dann kann das nie für eine Berechnung gelten. 53:29.290 --> 53:35.730 QIK heißt ja, zum i-ten Schritt ist die endliche Kontrolle im Zustand 53:35.730 --> 53:36.290 QK. 53:37.930 --> 53:41.550 Und QIL wahr heißt, im i-ten Schritt ist die endliche Kontrolle im 53:41.550 --> 53:42.450 Zustand QL. 53:43.330 --> 53:47.490 Wenn jetzt L und K verschieden sind, dann kann nicht gleichzeitig im i 53:47.490 --> 53:52.050 -ten Schritt die endliche Kontrolle im Zustand K und im Zustand QK und 53:52.050 --> 53:53.290 im Zustand QL sein. 53:54.330 --> 54:00.970 Irgendwie die Variablen mit wahr oder falsch belegen, führt uns nicht 54:00.970 --> 54:04.830 zu einer Beschreibung, was während einer Berechnung passieren kann. 54:08.040 --> 54:12.300 Das heißt also, wir müssen so eine Transformation zur Sprache L 54:12.300 --> 54:22.060 konstruieren, die eben jetzt Klauseln bildet, sodass äquivalent ist, 54:22.800 --> 54:28.800 wenn es für eine Eingabe X eine akzeptierende Berechnung gibt, deren 54:28.800 --> 54:34.040 Überprüfungsphase höchstens Pi von N Zeit braucht und deren Orakel 54:34.040 --> 54:39.560 auch höchstens Pi von N Länge hat, dann gibt es eine erfüllende 54:39.560 --> 54:43.000 Belegung der Satzinstanz und umgekehrt. 54:43.000 --> 54:44.540 Und wie machen wir das jetzt? 54:50.590 --> 54:56.590 Nochmal, ich muss jetzt erst mal folgern, was wir haben, wenn uns das 54:56.590 --> 54:57.050 gelingt. 54:57.670 --> 55:00.330 Wenn uns das gelingt, dann können wir Folgendes schließen. 55:00.570 --> 55:05.110 Also wenn wir so eine Transformation FL haben, dann können wir 55:05.110 --> 55:10.530 schließen, wenn X aus der Sprache ist, dann ist das äquivalent dazu, 55:10.610 --> 55:14.250 es gibt eine akzeptierende Berechnung bei Eingabe von X, 55:19.030 --> 55:23.350 die höchstens Pi von N Schritte benötigt, in der Überprüfungsphase und 55:23.350 --> 55:28.850 im Orakel der Länge P von N, höchstens Pi von N benutzt. 55:29.710 --> 55:33.150 Und das ist äquivalent dazu, dass es eine erfüllende Wahrheitsbelegung 55:33.150 --> 55:37.650 unserer durch FL von X angegebenen Menge von Klauseln gibt. 55:38.970 --> 55:42.330 Hiermit nur sichergestellt habe, wenn wir jetzt also diese Klauseln 55:42.330 --> 55:47.210 gebaut haben, oder eine Vorgehensweise wissen, wie wir diese Klauseln 55:47.210 --> 55:52.230 bauen, und diese Vorgehensweise auch polynomial beschränkt ist, dann 55:52.230 --> 55:53.770 sind wir fertig mit unserem Beweis. 55:55.610 --> 55:57.550 So, und jetzt geht es zum Klauselbauen. 56:00.690 --> 56:03.630 Noch ein paar Konventionen. 56:04.210 --> 56:09.330 Die Bewegungsrichtung des Lese-Schreibkopfes müssen wir irgendwie 56:09.330 --> 56:11.050 formal angeben. 56:11.050 --> 56:14.350 Die wird angegeben durch D, und D hat einen Wert. 56:15.210 --> 56:18.850 Minus 1 heißt, nur 1 nach links gehen, 0 heißt, der Lese-Schreibkopf 56:18.850 --> 56:21.750 bleibt, wo er ist, plus 1 heißt, geht 1 nach rechts. 56:23.810 --> 56:27.750 So, und dann bauen wir jetzt mit unseren Variablen Klauseln. 56:28.310 --> 56:33.230 Das sind sechs Gruppen von Klauseln, und jede Gruppe hat eine 56:33.230 --> 56:34.230 bestimmte Bedeutung. 56:35.450 --> 56:42.270 Die erste Gruppe, die stellt sicher, dass zum Zeitpunkt I die Turing 56:42.270 --> 56:45.210 -Maschine nur in genau einem Zustand ist. 56:45.410 --> 56:48.190 Das, was ich eben gesagt habe, diese Variablen, die für einen 56:48.190 --> 56:53.350 bestimmten Zeitpunkt I sagen, in welchem Zustand die Turing-Maschine 56:53.350 --> 56:57.690 ist, die können nicht für zwei verschiedene Zustände für den selben 56:57.690 --> 56:59.430 Zeitpunkt I bar sein. 56:59.430 --> 57:03.310 Das müssen wir hiermit sicherstellen, mit dieser Klauselgruppe, dass 57:03.310 --> 57:06.290 das bei einer Wahrheitsbelegung eben nicht passieren kann. 57:06.710 --> 57:08.770 Zwei dieser Variablen gleichzeitig wahr werden. 57:09.430 --> 57:14.970 Die zweite Klauselgruppe, die stellt einfach sicher in gleicher Weise, 57:15.070 --> 57:18.590 dass zu einem Zeitpunkt der Lese-Schreibkopf auch nur an einer 57:18.590 --> 57:19.830 Position sein kann. 57:21.350 --> 57:26.370 Die dritte Klauselgruppe stellt sicher, dass zu einem Zeitpunkt an 57:26.370 --> 57:33.990 einer ganz bestimmten Stelle des Bandes auch nur ein Symbol aus Gamma 57:33.990 --> 57:34.670 stehen kann. 57:36.870 --> 57:41.210 Die vierte Klauselgruppe, die stellt einfach sicher, dass die 57:41.210 --> 57:46.030 Anfangskonfiguration so ist, wie wir das per Konvention annehmen. 57:46.030 --> 57:51.230 Nämlich Festlegung der Anfangskonfiguration zum Zeitpunkt 0. 57:51.530 --> 57:56.110 Das heißt, die Turing-Maschine ist zum Zeitpunkt 0 im Startzustand Q0. 57:56.570 --> 57:59.770 Der Lese-Schreibkopf steht an Position 1 des Bandes. 58:00.150 --> 58:03.190 In den Zellen 1 bis N steht die Eingabe X. 58:04.770 --> 58:08.790 Das werden wir sicherstellen, dass das so ist durch die Klauseln in 58:08.790 --> 58:10.270 der Klauselgruppe G4. 58:11.270 --> 58:17.290 Die Klauselgruppe G5 stellt einfach sicher, dass wir nach spätestens P 58:17.290 --> 58:21.650 von N Berechnungsschritten im akzeptierenden Zustand sind. 58:23.910 --> 58:31.450 Und die Klauselgruppe G6, die ist jetzt sehr wichtig, die stellt 58:31.450 --> 58:37.190 sicher, dass die Übergänge so sind wie Delta, unsere 58:37.190 --> 58:39.570 Übergangsfunktion, das vorgibt. 58:39.570 --> 58:47.990 Nämlich, dass zu jedem Zeitpunkt I folgt die Konfiguration der Turing 58:47.990 --> 58:52.730 -Maschine zum darauffolgenden Zeitpunkt I plus 1 aus einer einzigen 58:52.730 --> 58:54.410 Anwendung von Delta. 59:00.000 --> 59:04.180 Und zwar eine Anwendung von Delta genau auf die Konfiguration, in der 59:04.180 --> 59:06.240 die Turing-Maschine zum Zeitpunkt I ist. 59:08.020 --> 59:11.980 Okay, jetzt gucken wir uns mal an, wie diese Klauseln aussehen müssen. 59:12.540 --> 59:16.580 Wenn die Klauselgruppe G1 verstanden hat, dann ist G2 und G3 auch ganz 59:16.580 --> 59:16.920 einfach. 59:17.020 --> 59:19.860 G4 und G5 sind ziemlich einfach, G6 ist nochmal ein bisschen 59:19.860 --> 59:20.360 schwieriger. 59:21.320 --> 59:26.420 So, G1, die Klauselgruppe 1, also die soll sicherstellen, dass zu 59:26.420 --> 59:30.320 einem einzigen Zeitpunkt I die Turing-Maschine auch nur in einem ganz 59:30.320 --> 59:33.560 bestimmten Zustand QJ ist. 59:33.560 --> 59:38.640 Also, zu jedem Zeitpunkt I ist die Turing-Maschine in mindestens einem 59:38.640 --> 59:41.360 Zustand, aber nicht in zwei verschiedenen. 59:42.520 --> 59:43.780 So kann man das übersetzen. 59:44.860 --> 59:49.000 Zu jedem Zeitpunkt I ist sie in genau einem Zustand, heißt, sie muss 59:49.000 --> 59:54.300 in irgendeinem Zustand sein, mindestens für einen Zustand ist die 59:54.300 --> 59:59.180 entsprechende Variable wahr, aber sie ist nicht für mehr als einen 59:59.180 --> 01:00:00.020 Zustand wahr. 01:00:01.020 --> 01:00:10.200 Um auszudrücken durch Klauseln, dass sie zum Zeitpunkt I in mindestens 01:00:10.200 --> 01:00:18.680 einem Zustand QR ist, muss man einfach sicher gehen, dass folgendes 01:00:18.680 --> 01:00:19.300 wahr wird. 01:00:19.860 --> 01:00:33.320 QI0 oder QI1 oder QIR, natürlich für jeden Zeitpunkt I zwischen 0 und 01:00:33.320 --> 01:00:34.140 P von Endpunkt. 01:00:35.580 --> 01:00:40.680 Wir haben die Zustände Q0 bis QR in unserer Turing-Maschine. 01:00:41.550 --> 01:00:49.540 Wenn wir sicherstellen, dass die Formel QI0 oder QI1 oder QIR für 01:00:49.540 --> 01:00:56.060 jeden Zeitpunkt I wahr wird, dann haben wir sichergestellt, zu jedem 01:00:56.060 --> 01:00:59.180 Zeitpunkt I ist die Turing-Maschine in mindestens einem Zustand. 01:00:59.440 --> 01:01:02.940 Aber es könnte jetzt natürlich sein, dass diese Formel wahr wird, weil 01:01:02.940 --> 01:01:06.780 mehrere dieser QIJ gleichzeitig wahr werden. 01:01:06.780 --> 01:01:11.980 Und das wäre wieder Widerspruch zu der Art und Weise, wie eine Turing 01:01:11.980 --> 01:01:13.340 -Maschinen -Berechnung aussieht. 01:01:13.780 --> 01:01:19.560 Das heißt, wir brauchen jetzt noch eine zweite Klauselgruppe, die 01:01:19.560 --> 01:01:23.180 sicherstellt, dass zum Zeitpunkt I die Turing-Maschine nicht 01:01:23.180 --> 01:01:30.740 gleichzeitig in einem Zustand QL und einem Zustand QJ und einem 01:01:30.740 --> 01:01:32.120 Zustand QJ' ist. 01:01:32.930 --> 01:01:36.880 Wie stellen wir sicher, indem wir sagen, auf jeden Fall müssen für 01:01:36.880 --> 01:01:47.720 alle Paare JJ' gehören zu Zuständen, nicht QIJ oder nicht QIJ' wahr 01:01:47.720 --> 01:01:48.000 werden. 01:02:04.260 --> 01:02:05.120 Wo kommt das her? 01:02:08.920 --> 01:02:13.920 Was wir sicherstellen müssen für jedes Paar von Zuständen J und J', 01:02:15.380 --> 01:02:21.120 dass es nicht gleichzeitig war QIJ und QIJ'. 01:02:21.120 --> 01:02:26.920 Die Formel nicht QIJ und QIJ'. 01:02:28.460 --> 01:02:31.760 Unsere Formeln, unsere Klauseln sehen aber anders aus. 01:02:31.900 --> 01:02:33.080 Das sind Oder-Verbindungen. 01:02:33.600 --> 01:02:38.960 Also rechnen wir das einfach um, dieses nicht in Klammer QIJ und QIJ'. 01:02:38.960 --> 01:02:44.120 Und dann kommt raus, nicht QIJ oder nicht QIJ'. 01:02:44.120 --> 01:02:50.760 Das war jetzt einfach nochmal Aussagenlogik, so wie wir sie hier jetzt 01:02:50.760 --> 01:02:53.240 brauchen, um unsere Klauseln aufzustellen. 01:02:54.020 --> 01:02:57.840 Okay, wenn wir jetzt das Prinzip verstanden haben für diese erste 01:02:57.840 --> 01:03:01.440 Klauselgruppe, die dafür sorgt, dass in unserer Beschreibung der 01:03:01.440 --> 01:03:05.660 Berechnung zu einem bestimmten Zeitpunkt die Turing-Maschine in nur 01:03:05.660 --> 01:03:09.160 genau einem Zustand ist, dann können wir jetzt die nächsten zwei 01:03:09.160 --> 01:03:12.200 Klauselgruppen direkt analog aufbauen. 01:03:12.940 --> 01:03:17.540 Die nächste Klauselgruppe 2, die soll ja sicherstellen, dass unsere 01:03:17.540 --> 01:03:21.880 Turing -Maschine zu einem Zeitpunkt I den Lese-Schreibkopf an genau 01:03:21.880 --> 01:03:26.040 einer Stelle hat und nicht an mehreren Stellen gleichzeitig. 01:03:26.240 --> 01:03:26.940 Das kann nicht sein. 01:03:27.880 --> 01:03:31.780 Also, zum Zeitpunkt I hat der Lese-Schreibkopf genau eine Position. 01:03:31.780 --> 01:03:36.740 Die Konstruktion der entsprechenden Klauseln ist völlig analog zu dem, 01:03:36.860 --> 01:03:37.520 was wir eben hatten. 01:03:38.040 --> 01:03:44.300 Einerseits Klauseln, die sicherstellen, dass zu jedem Zeitpunkt I der 01:03:44.300 --> 01:03:49.540 Lese -Schreibkopf in mindestens einer Position ist und dann Klauseln, 01:03:49.740 --> 01:03:54.880 die sicherstellen, dass aber nicht gleichzeitig für zwei Positionen 01:03:54.880 --> 01:03:59.920 die entsprechenden Variablen wahrheitswert wahrbekommen können. 01:04:00.620 --> 01:04:04.720 Das Erste, zum Zeitpunkt I hat der Lese-Schreibkopf mindestens eine 01:04:04.720 --> 01:04:05.140 Position. 01:04:05.400 --> 01:04:09.840 Das ist einfach wieder die Oder-Verbindung aller Variablen zum 01:04:09.840 --> 01:04:12.600 Zeitpunkt I und einer bestimmten Position. 01:04:14.000 --> 01:04:18.220 Und die Position, wo der Lese-Schreibkopf überhaupt nur hingelangt, 01:04:18.240 --> 01:04:24.340 während unserer durch P von N begrenzten Berechnung ist, minus P von N 01:04:24.340 --> 01:04:26.940 und P von N plus 1. 01:04:26.940 --> 01:04:31.320 Das heißt also, wir brauchen hier einfach für alle Zeitpunkte I und I 01:04:31.320 --> 01:04:36.180 ist wieder zwischen 0 und P von N die Oder-Verbindung der Variablen h 01:04:36.180 --> 01:04:41.680 i minus P von N bis h i P von N plus 1. 01:04:42.440 --> 01:04:45.560 Und analog zu dem, was wir eben gemacht haben, dann der zweite 01:04:45.560 --> 01:04:51.400 Schritt, dass wir ausschließen, dass h i j und h i j Strich 01:04:51.400 --> 01:04:52.800 gleichzeitig wahr werden. 01:04:52.800 --> 01:04:58.880 Für alle j j Strich jetzt Positionen, die infrage kommen, also j j 01:04:58.880 --> 01:05:02.300 Strich zwischen minus P von N und plus P von N plus 1. 01:05:02.940 --> 01:05:07.980 Naja gut, das sind diese Klauseln, nicht h i j oder nicht h i j 01:05:07.980 --> 01:05:08.340 Strich. 01:05:09.660 --> 01:05:12.720 Völlig analog zu dem, was wir im Schritt vorher gemacht haben. 01:05:13.520 --> 01:05:15.220 Und das dritte ist auch wieder völlig analog. 01:05:15.500 --> 01:05:19.060 Also die dritte Klauselgruppe, die ist ja dafür da, dass wir 01:05:19.060 --> 01:05:25.200 beschreiben in unserer Beschreibung der Berechnung der Turing-Maschine 01:05:26.740 --> 01:05:31.920 durch Klauseln, durch eine Satzinstanz, dass zu einem Zeitpunkt I an 01:05:31.920 --> 01:05:37.420 einer Stelle im Band nicht verschiedene Symbole stehen, aber ein 01:05:37.420 --> 01:05:38.760 Symbol auf jeden Fall da steht. 01:05:39.720 --> 01:05:46.360 Diese s i j k sind ja zuständig für das, was zum Zeitpunkt I an der 01:05:46.360 --> 01:05:55.620 Stelle j steht, nämlich da hinten k steht, also das Karte-Symbol des 01:05:55.620 --> 01:05:57.140 Bandalphabets. 01:06:00.640 --> 01:06:06.100 Für alle Zeitpunkte I und alle Positionen j muss eine dieser 01:06:06.100 --> 01:06:07.380 Möglichkeiten, das 0. 01:06:07.500 --> 01:06:08.520 Symbol oder das 1. 01:06:08.660 --> 01:06:13.040 Symbol oder das ältere Symbol des Bandalphabets steht da. 01:06:13.640 --> 01:06:17.800 Eine muss mindestens eintreten, dafür haben wir wieder die Klausel s i 01:06:17.800 --> 01:06:22.920 j 0 oder s i j 1 oder s i j l. 01:06:23.840 --> 01:06:30.000 Und andererseits darf aber auch nicht für zwei verschiedene s i j k 01:06:30.000 --> 01:06:34.860 und s i j k Strich eintreten, dass sie gleichzeitig wahr werden. 01:06:34.860 --> 01:06:42.080 Also brauchen wir all diese Klauseln nicht s i j k oder nicht s i j k 01:06:42.080 --> 01:06:46.140 Strich, für alle k, k Strich zwischen 0 und l. 01:06:49.480 --> 01:06:50.800 Vierte Klauseltruppe. 01:06:52.480 --> 01:06:57.300 Die vierte Klauseltruppe oder Klauselgruppe, die soll einfach die 01:06:57.300 --> 01:06:59.040 Anfangskonfiguration beschreiben. 01:07:01.680 --> 01:07:04.700 Die Anfangskonfiguration, die ist so am Anfang, ist die Turingmaschine 01:07:04.700 --> 01:07:05.780 im Zustand q 0. 01:07:06.800 --> 01:07:10.940 Das heißt also, zum Zeitpunkt 0 ist sie im Zustand q 0. 01:07:12.120 --> 01:07:17.420 Das stellen wir sicher, indem wir sicherstellen, die Variable q 0 0 01:07:17.420 --> 01:07:18.360 soll wahr werden. 01:07:18.780 --> 01:07:21.540 Dafür führen wir einfach die Klausel q 0 0 ein. 01:07:23.020 --> 01:07:27.180 Dann, der Leseschreibkopf steht an Position 1 des Bandes. 01:07:27.180 --> 01:07:29.880 Dafür sind die h Variablen zuständig. 01:07:30.260 --> 01:07:34.160 Zum Zeitpunkt 0 soll der Kopf an Stelle 1 stehen. 01:07:34.300 --> 01:07:38.720 Das heißt also, die Variable h von 0,1 muss wahr werden. 01:07:39.320 --> 01:07:41.180 Da führen wir die einfach als Klausel ein. 01:07:42.220 --> 01:07:45.900 Und als drittes, in den Zellen 1 bis n steht die Eingabe. 01:07:46.140 --> 01:07:50.540 Die Eingabe, das ist unser Wort x und das soll so aussehen, das ist 01:07:50.540 --> 01:07:52.980 irgend so ein s k 1 bis s k n. 01:07:54.200 --> 01:07:56.020 Wie gewährleisten wir das? 01:07:56.340 --> 01:08:01.000 Indem wir sicher gehen, dass die entsprechenden Variablen von unseren 01:08:01.000 --> 01:08:02.780 s Variablen wahr werden. 01:08:03.920 --> 01:08:07.640 Also, Zeitpunkt 0, das ist hier immer das erste. 01:08:08.980 --> 01:08:12.700 Das zweite gibt an, an welcher Position am Band wir stehen. 01:08:12.820 --> 01:08:16.080 Das dritte gibt an, was da für ein Symbol steht. 01:08:16.620 --> 01:08:19.780 Also, s 0 0 0 muss wahr werden. 01:08:19.780 --> 01:08:22.160 Zum Zeitpunkt 0 steht an der 0. 01:08:22.260 --> 01:08:25.620 Stelle nichts. 01:08:32.710 --> 01:08:37.930 Oder das ist ein leeres Blenksymbol. 01:08:38.650 --> 01:08:43.670 Und dann an der ersten Stelle soll ja das erste Symbol der Eingabe 01:08:43.670 --> 01:08:45.870 stehen, also s 0 1 k 1. 01:08:45.970 --> 01:08:48.850 An der zweiten Stelle das zweite Symbol der Eingabe und so weiter. 01:08:48.950 --> 01:08:53.630 An der enden Stelle das ende Symbol der Eingabe, also s 0 n k n. 01:08:53.630 --> 01:08:55.070 Muss wahr werden. 01:08:56.030 --> 01:08:59.750 Und an allen anderen Stellen soll ja per Festlegung wieder ein 01:08:59.750 --> 01:09:00.830 Blenksymbol stehen. 01:09:01.330 --> 01:09:08.670 Das heißt also, für s 0 n plus 1 0 bis s 0 p von n plus 1 0, das sind 01:09:08.670 --> 01:09:11.390 alle Positionen, die überhaupt nachher eine Rolle spielen werden 01:09:11.390 --> 01:09:14.310 möglicherweise, steht wieder das Blenksymbol. 01:09:16.870 --> 01:09:21.970 Okay, Klauselgruppe 5 soll einfach sicher stehen, dass wir spätestens 01:09:21.970 --> 01:09:26.870 nach p von n Berechnungsschritte im akzeptierenden Stoppzustand sind. 01:09:27.650 --> 01:09:31.310 Das ist wieder einfach, dafür sind ja unsere q-Variablen da. 01:09:32.030 --> 01:09:36.310 Wir müssen also sicher gehen, dass die q-Variable zu p von n, 01:09:36.310 --> 01:09:44.390 Zeitpunkt p von n, und Zustand qj, der erste, nachdem wir die Zustände 01:09:44.390 --> 01:09:46.770 durchnummeriert haben, wahr wird. 01:09:47.010 --> 01:09:50.650 Das heißt also, wir führen die Klausel q p von n,1 ein. 01:09:52.990 --> 01:09:55.490 So, und jetzt kommen die spannenden Klauseln. 01:09:55.990 --> 01:10:01.970 Jetzt müssen wir über Formeln oder Klauseln beschreiben, wie ein 01:10:01.970 --> 01:10:03.530 Übergang aussieht. 01:10:04.510 --> 01:10:07.450 Im dritten Zeitpunkt haben wir eine bestimmte Situation. 01:10:07.810 --> 01:10:12.030 Zum i plus ersten Zeitpunkt, also im nächsten Schritt, eine bestimmte 01:10:12.030 --> 01:10:12.530 Situation. 01:10:13.190 --> 01:10:16.890 Und wie wir von der einen zur anderen kommen, das gibt uns Delta vor. 01:10:17.630 --> 01:10:19.690 Und das müssen wir jetzt beschreiben durch Klauseln. 01:10:21.410 --> 01:10:25.810 Also zu jedem Zeitpunkt i folgt die Konfiguration von m zum Zeitpunkt 01:10:25.810 --> 01:10:26.750 i plus 1. 01:10:26.750 --> 01:10:31.230 Aus einer einzigen Anwendung der Übergangsfunktion Delta aus der 01:10:31.230 --> 01:10:34.770 Konfiguration von m zum Zeitpunkt i. 01:10:35.430 --> 01:10:38.810 Dafür haben wir jetzt zwei verschiedene Teilgruppen. 01:10:39.210 --> 01:10:42.170 Also diese Klauselgruppe 6 ist jetzt nochmal in zwei Teilgruppen 01:10:42.170 --> 01:10:42.890 aufgeteilt. 01:10:43.590 --> 01:10:49.550 Die erste Teilgruppe, E61, soll folgendes sicherstellen. 01:10:49.550 --> 01:10:56.290 Falls m zum Zeitpunkt i an der Position j das Symbol sk hat und der 01:10:56.290 --> 01:11:02.110 Lese -Schreibkopf gar nicht an der Position j steht, dann hat m auch 01:11:02.110 --> 01:11:06.350 zum Zeitpunkt i plus 1 an der Position j das Symbol sk. 01:11:07.350 --> 01:11:12.390 Die erste Klauselgruppe ist nur dafür da, sicherzustellen, dass alles 01:11:12.390 --> 01:11:20.950 gleich bleibt beim Übergang von Zeitpunkt i zur Situation i plus 1, 01:11:22.350 --> 01:11:26.010 womit im Moment der Lese-Schreibkopf gar nichts zu tun hat. 01:11:27.130 --> 01:11:30.870 Alle anderen Positionen auf dem Band bleiben unverändert. 01:11:30.870 --> 01:11:34.990 Dafür ist diese erste Gruppe da und die zweite Gruppe ist dafür da, 01:11:35.170 --> 01:11:38.350 genau die Veränderung an der Stelle, wo wir gerade sind, zu 01:11:38.350 --> 01:11:39.370 beschreiben. 01:11:39.470 --> 01:11:44.670 Der Wechsel von einer Konfiguration zur nächsten entsprechend Delta. 01:11:48.900 --> 01:11:53.020 Jetzt erstmal, dass überall anderswo, wenn der Lese-Schreibkopf an der 01:11:53.020 --> 01:11:55.400 Stelle j steht, überall anderswo nichts passiert. 01:11:56.740 --> 01:11:58.020 Das ist nicht so schwer. 01:11:59.100 --> 01:12:04.540 Falls m zum Zeitpunkt i an der Position j das Symbol sk hat und der 01:12:04.540 --> 01:12:09.320 Lese -Schreibkopf nicht an der Position j steht, dann soll m auch zum 01:12:09.320 --> 01:12:14.280 Zeitpunkt i plus 1 an Position j das Symbol sk haben. 01:12:15.620 --> 01:12:16.960 Wie können wir das beschreiben? 01:12:16.960 --> 01:12:22.100 Ja, diese erste Sache zum Zeitpunkt i ist an der Position j das Symbol 01:12:22.100 --> 01:12:22.660 sk. 01:12:24.800 --> 01:12:28.580 Würde entsprechen, die Variable sijk ist wahr. 01:12:31.040 --> 01:12:36.260 Und dann steht da und der Lese-Schreibkopf steht nicht an der Position 01:12:36.260 --> 01:12:36.760 j. 01:12:37.380 --> 01:12:41.580 Dem entspricht die Variable hij. 01:12:42.780 --> 01:12:47.220 Zum Zeitpunkt i steht der Lese-Schreibkopf an Position j, ist falsch. 01:12:47.820 --> 01:12:49.720 Also nicht hij ist wahr. 01:12:50.880 --> 01:13:01.620 Also wenn sijk wahr ist und nicht hij war es, dann soll zum Zeitpunkt 01:13:01.620 --> 01:13:04.940 i plus 1 an Position j das Symbol sk stehen. 01:13:05.660 --> 01:13:13.300 Dann soll Variable s von i plus 1,j,k wahr werden. 01:13:15.080 --> 01:13:18.440 Wir haben jetzt logisch einfach das beschrieben, was hier dick steht. 01:13:20.400 --> 01:13:22.740 Nur das sieht nicht so aus, wie es aussehen soll. 01:13:23.520 --> 01:13:26.420 Was wir so brauchen sind Klauseln und Klauseln sehen einfach so aus. 01:13:26.860 --> 01:13:30.060 Oder Verbindungen von Literalen oder Verbindungen von solchen 01:13:30.060 --> 01:13:32.220 Variablen in negierter oder unnegierter Form. 01:13:33.600 --> 01:13:36.340 Hier steht ein und und da steht eine Folgerung. 01:13:38.120 --> 01:13:44.100 Das hier kann man aber leicht umwandeln, äquivalent in diese Klausel 01:13:44.100 --> 01:13:44.340 hier. 01:13:44.940 --> 01:13:47.880 Das Ganze hier ist wahr, wenn die Klausel wahr ist. 01:13:48.020 --> 01:13:55.880 Die Klausel nicht sijk oder hij oder si plus 1,j,k. 01:13:56.540 --> 01:13:57.400 Sehen Sie das? 01:13:58.480 --> 01:13:59.440 Da frage ich mich. 01:14:08.910 --> 01:14:10.990 Wir haben, 01:14:17.260 --> 01:14:18.520 wie sah das aus? 01:14:22.100 --> 01:14:26.640 sijk und nicht hij. 01:14:31.940 --> 01:14:37.720 Das war es, dann soll si plus 1,j 01:14:42.160 --> 01:14:44.640 wahr sein. 01:14:46.200 --> 01:14:47.600 Das war es, 01:14:52.230 --> 01:14:53.890 das war es. 01:14:57.330 --> 01:15:01.310 Uns stören hier zwei Sachen, das und hier und die Folgerung da. 01:15:02.070 --> 01:15:08.910 Das ist wahr, das ist äquivalent dazu. 01:15:09.250 --> 01:15:10.750 Die Negation ist falsch. 01:15:10.750 --> 01:15:26.330 Also, si und nicht war nicht ist falsch. 01:15:28.450 --> 01:15:30.570 Das impliziert, dass es war. 01:15:38.890 --> 01:15:40.850 Das hier können wir umschreiben. 01:15:40.850 --> 01:15:55.910 Das ist genau dann der Fall, wenn also sijk negiert oder hij negiert. 01:15:58.850 --> 01:16:00.250 Falsch ist. 01:16:02.610 --> 01:16:04.090 Wann ist das wahr? 01:16:14.490 --> 01:16:15.970 Aber wann ist das wahr? 01:16:16.970 --> 01:16:20.330 Wenn das falsch ist, muss das wahr werden. 01:16:21.930 --> 01:16:33.510 Wenn wir fordern, dass nicht ist, wird wahr. 01:16:33.930 --> 01:16:45.070 Oder hij wahr wird oder das wahr wird. 01:16:54.460 --> 01:16:57.280 Das hier ist falsch, folgt das hier ist wahr. 01:16:59.980 --> 01:17:01.460 Ist äquivalent davon. 01:17:04.410 --> 01:17:07.190 Die oder-Verbindung von den dreien ist wahr. 01:17:07.370 --> 01:17:10.250 Also entweder ist das wahr oder das ist wahr oder das ist wahr. 01:17:11.990 --> 01:17:19.070 Das ist einfach nicht sijk oder hij oder si plus 1,jk. 01:17:19.070 --> 01:17:22.730 Das ist auch wieder ganz grundlegende Aussagenlogik. 01:17:22.950 --> 01:17:26.510 Haben Sie hoffentlich schon mal gesehen, haben wir uns jetzt nochmal 01:17:26.510 --> 01:17:30.890 klar gemacht, wie man also so eine Formulierung in so eine Klausel 01:17:30.890 --> 01:17:31.750 umwandeln kann. 01:17:32.390 --> 01:17:32.810 Äquivalent. 01:17:34.210 --> 01:17:35.510 Nichts anderes haben wir hier gemacht. 01:17:36.850 --> 01:17:40.090 Okay, wenn wir das verstanden haben, dann verstehen wir auch das, was 01:17:40.090 --> 01:17:41.110 als nächstes kommt. 01:17:43.390 --> 01:17:51.490 Die letzte Klauselgruppe, die Klauselgruppe B6-2, die sicherstellt, 01:17:51.970 --> 01:17:57.810 dass beim Wechsel von der Konfiguration zum Zeitpunkt i in die 01:17:57.810 --> 01:18:02.510 Konfiguration vom Zeitpunkt i plus 1 genau das passiert, was Delta 01:18:02.510 --> 01:18:02.990 sagt. 01:18:04.150 --> 01:18:07.230 Also der Wechsel von einer Konfiguration zur nächsten entspricht 01:18:07.230 --> 01:18:08.350 tatsächlich Delta. 01:18:08.350 --> 01:18:10.430 Dann gucken wir uns mal Delta an. 01:18:10.650 --> 01:18:17.030 Delta ist irgendwas, wenn wir im Zustand qk sind und an der Stelle, wo 01:18:17.030 --> 01:18:22.190 der lese Schreibkopf steht, das Symbol sm steht, dann sagt uns Delta, 01:18:22.310 --> 01:18:25.010 dann sollen wir danach im Zustand qk sein. 01:18:25.510 --> 01:18:30.690 An der Stelle, wo der lese Schreibkopf steht, steht jetzt smü und der 01:18:30.690 --> 01:18:32.950 lese Schreibkopf bewegt sich um d. 01:18:33.450 --> 01:18:35.630 Wir haben gesagt, d ist minus 1, 0 oder 1. 01:18:36.510 --> 01:18:38.350 Wie beschreiben wir alles das? 01:18:41.850 --> 01:18:46.370 Die Übergänge sind ja nur interessant für Zustände, die nicht 01:18:46.370 --> 01:18:47.590 Stoppzustände sind. 01:18:48.190 --> 01:18:53.550 Also erstmal obda sei qk kein Stoppzustand, also ohne qj und qn. 01:18:54.810 --> 01:18:58.910 Ansonsten würde man einfach sagen, na gut, das qk ist gleich dem qk 01:18:58.910 --> 01:19:02.130 und das sm ist gleich dem sm und das d ist gleich 0. 01:19:13.170 --> 01:19:21.630 Wenn zum Zeitpunkt i die Turing-Maschine im Zustand j ist, nein, der 01:19:21.630 --> 01:19:30.290 lese Schreibkopf an der Stelle j steht und zum Zeitpunkt i die Turing 01:19:30.290 --> 01:19:36.050 -Maschine im Zustand qk ist und zum Zeitpunkt i an der Stelle, wo der 01:19:36.050 --> 01:19:40.950 lese Schreibkopf steht, also an der Stelle j, sm steht, dann soll also 01:19:40.950 --> 01:19:47.030 entsprechend dieser Übergangsfunktion der lese Schreibkopf zum 01:19:47.030 --> 01:19:52.030 nächsten Zeitpunkt, i plus 1, an der Stelle j plus d stehen. 01:19:53.210 --> 01:19:56.870 Wir werten jetzt erstmal hier diese letzte Stelle aus, die uns sagt, 01:19:56.970 --> 01:19:58.690 wie der lese Schreibkopf sich bewegt. 01:19:59.410 --> 01:20:04.890 Und dieser Übergang Delta von qk, sm gleich Delta qkappa, smü, d 01:20:04.890 --> 01:20:07.490 bedeutet insbesondere, 01:20:11.620 --> 01:20:17.080 wenn zum Zeitpunkt i der lese Schreibkopf an der Stelle j steht, die 01:20:17.080 --> 01:20:23.060 Turing -Maschine im Zustand qk ist und an der Stelle j, sm steht, dann 01:20:23.060 --> 01:20:27.840 soll zum Zeitpunkt i plus 1 der lese Schreibkopf an der Stelle j plus 01:20:27.840 --> 01:20:28.320 d stehen. 01:20:29.500 --> 01:20:32.120 Aber hier dieser Übergang sagt ja noch mehr. 01:20:33.480 --> 01:20:37.240 Er sagt, wir gehen vom Zustand qk in den Zustand qkappa über. 01:20:37.800 --> 01:20:40.800 Dafür ist jetzt diese zweite Sorte von Klauseln da. 01:20:41.360 --> 01:20:46.200 Wenn zum Zeitpunkt i der lese Schreibkopf an der Stelle j steht und 01:20:46.200 --> 01:20:52.140 die Turing-Maschine zum Zeitpunkt i im Zustand qk ist und zum 01:20:52.140 --> 01:20:58.120 Zeitpunkt i an der Stelle j, sm steht, dann soll der Zustand zum 01:20:58.120 --> 01:21:01.540 Zeitpunkt i plus 1 gerade qkappa sein. 01:21:03.880 --> 01:21:10.920 Und das dritte, das wir also sm mit smü überschreiben, also wenn der 01:21:10.920 --> 01:21:14.960 lese Schreibkopf zum Zeitpunkt i an der Stelle j steht und die Turing 01:21:14.960 --> 01:21:21.120 -Maschine zum Zeitpunkt i im Zustand qk ist und das Symbol an der 01:21:21.120 --> 01:21:26.360 Stelle j zum Zeitpunkt i, sm ist, dann soll das Symbol zum Zeitpunkt i 01:21:26.360 --> 01:21:29.080 plus 1 an der Stelle j, smü sein. 01:21:29.740 --> 01:21:34.020 Das heißt also alles das, was hier Delta von qk, sm gleich qkappa, 01:21:34.140 --> 01:21:40.560 smü, d ausdrückt, haben wir hier durch diese drei logischen Formeln 01:21:40.560 --> 01:21:41.080 beschrieben. 01:21:41.080 --> 01:21:45.380 Die sind jetzt wie eben noch nicht in der Form, wie wir sie gerne 01:21:45.380 --> 01:21:45.760 hätten. 01:21:46.300 --> 01:21:49.660 Das sind jetzt so Folgerungen, wo hier so eine und-Verbindung von 01:21:49.660 --> 01:21:53.840 Variablen steht oder von Literalen steht und wir wollen aber eine oder 01:21:53.840 --> 01:21:55.180 -Verbindung von Literalen. 01:21:55.580 --> 01:21:59.660 Aber so wie eben, die sehen genauso aus wie die eben, so wie eben 01:21:59.660 --> 01:22:02.480 können wir die umformen in so entsprechende oder-Verbindungen. 01:22:02.820 --> 01:22:04.980 Da müssen wir jetzt gar nicht genauer hingucken. 01:22:05.200 --> 01:22:08.620 Aber wenn man das Prinzip einmal verstanden hat, klar, dass wir die so 01:22:08.620 --> 01:22:10.120 äquivalent ausdrücken können. 01:22:10.120 --> 01:22:17.440 Und wie diese i, j, k, l, mü, m und sonst was für einen Wertebereich 01:22:17.440 --> 01:22:19.120 haben, das wissen wir mittlerweile auch. 01:22:19.300 --> 01:22:23.000 i ist immer ein Zeitpunkt zwischen 0 und p von n, j ist immer eine 01:22:23.000 --> 01:22:28.160 Position zwischen minus p von n und pn plus 1, k ist immer ein Zustand 01:22:28.160 --> 01:22:33.100 zwischen q0 und qr und m ist immer ein Symbol zwischen s0 und s. 01:22:34.060 --> 01:22:42.140 Okay, jetzt haben wir also für eine beliebige Sprache aus np und die 01:22:42.140 --> 01:22:45.660 dazugehörige Berechnung der nicht-deterministischen Turing-Maschine 01:22:45.660 --> 01:22:52.340 eine Möglichkeit, eine SAT-Instanz alles auszudrücken, was in dieser 01:22:52.340 --> 01:22:53.220 Berechnung passiert. 01:22:54.040 --> 01:22:58.860 Und die SAT-Instanz ist genau so, dass wenn die Berechnung 01:22:58.860 --> 01:23:04.060 akzeptierend ist, also die Eingabe x aus der Sprache ist, dann können 01:23:04.060 --> 01:23:08.360 wir eine Wahrheitsbelegung finden, sodass alle diese Klauseln wahr 01:23:08.360 --> 01:23:08.740 werden. 01:23:09.440 --> 01:23:10.820 Das ist per Konstruktion. 01:23:13.140 --> 01:23:16.440 Und umgekehrt, wenn wir eine Wahrheitsbelegung haben für diese 01:23:16.440 --> 01:23:21.000 Klauseln, für diese Variablen, die alle Klauseln gleichzeitig wahr 01:23:21.000 --> 01:23:25.620 macht, dann induziert das per Konstruktion automatisch eine 01:23:25.620 --> 01:23:27.420 akzeptierende Berechnung x. 01:23:28.240 --> 01:23:32.320 Das heißt also, unsere Konstruktion ist genau so, wie sie sein soll. 01:23:33.160 --> 01:23:37.840 Das Einzige, was jetzt noch bleibt, ist zu beweisen, dass diese ganze 01:23:37.840 --> 01:23:46.100 Konstruktion, dieses fl, auch wirklich in Polynomialzeit mit einem 01:23:46.100 --> 01:23:50.900 polynomialen Algorithmus durchgeführt werden kann. 01:23:52.740 --> 01:23:59.480 Also von diesen verschiedenen Situationen aus der akzeptierenden 01:23:59.480 --> 01:24:03.260 Berechnung, die wir beschreiben müssen, diese Formeln bilden. 01:24:03.340 --> 01:24:07.180 Es ist insgesamt nur polynomial beschränkt durch die Länge der 01:24:07.180 --> 01:24:07.760 Eingabe. 01:24:08.680 --> 01:24:11.600 Wir haben hier eine ganze Menge Variablen eingeführt, eine ganze Menge 01:24:11.600 --> 01:24:12.640 Klauseln eingeführt. 01:24:13.000 --> 01:24:16.520 Wir müssen jetzt einfach eingucken und das alles bleibt innerhalb von 01:24:16.520 --> 01:24:18.820 polynomial in n. 01:24:20.240 --> 01:24:25.260 Und da ist jetzt ganz wichtig, dass diese nicht deterministische 01:24:25.260 --> 01:24:30.540 Berechnung, die da L in np ist, annehmen können, dass die polynomial 01:24:30.540 --> 01:24:31.380 beschränkt ist. 01:24:31.380 --> 01:24:36.200 Denn wir haben jetzt ganz vieles gemacht, wo irgendwie das p von n 01:24:36.200 --> 01:24:41.220 vorkommt, zum Beispiel die Anzahl der Positionen durch p von n oder 01:24:41.220 --> 01:24:43.280 ein Polynom in p von n beschränkt usw. 01:24:43.780 --> 01:24:46.580 Und das ist jetzt ziemlich langweilig, muss aber gemacht werden. 01:24:46.960 --> 01:24:49.960 Wir müssen die Anzahl der Literale in den Klauselgruppen abschätzen. 01:24:50.100 --> 01:24:53.240 Und da muss man jetzt alle Klauselgruppen durchgehen und einfach 01:24:53.240 --> 01:24:53.860 nachzählen. 01:24:53.940 --> 01:24:57.420 Also diese erste Klauselgruppe, die für die Zustände, in denen man 01:24:57.420 --> 01:25:00.380 verschiedenen Zeitpunkten sein kann, zuständig ist, muss man einfach 01:25:00.380 --> 01:25:08.720 nachgucken, diese Parameter i und j, in welchen Wertebereichen bewegen 01:25:08.720 --> 01:25:11.320 die sich, wie viele Möglichkeiten kommen da. 01:25:11.920 --> 01:25:16.420 Aber die bewegen sich alle in Wertebereichen, die von p von n abhängen 01:25:16.420 --> 01:25:21.520 oder eben sozusagen vorgegebenen Größen, die auch zur Eingabe gehören, 01:25:21.580 --> 01:25:24.240 wie die Anzahl der Zustände, die Anzahl der Symbole usw. 01:25:25.640 --> 01:25:28.980 Also für jedes einzelne dieser Klauselgruppen kann man eine 01:25:28.980 --> 01:25:31.940 Abschätzung machen, die polynomial beschränkt ist in n. 01:25:32.360 --> 01:25:34.380 Und da kommt dieses p von n oft vor. 01:25:34.540 --> 01:25:35.780 Und das ist hier das Entscheidende. 01:25:36.020 --> 01:25:39.620 Das geht natürlich ein, dass für unsere Sprache, von der wir 01:25:39.620 --> 01:25:43.860 ausgegangen sind, von der wir diese Klauseln, diese Satzinstanz 01:25:43.860 --> 01:25:47.980 konstruiert haben, dass es für die eine polynomial beschränkte, nicht 01:25:47.980 --> 01:25:50.480 deterministische, akzeptierende Berechnung gibt. 01:25:50.480 --> 01:25:54.320 Also wir gehen einfach nur die ganzen Klauselgruppen durch, gucken an, 01:25:54.400 --> 01:25:58.820 wie viele Literale kommen denn da insgesamt vor. 01:25:59.300 --> 01:26:03.200 Und da kommt dann immer hier so ein aufregender, langer Ausdruck, den 01:26:03.200 --> 01:26:05.100 man aber eigentlich nur hier ablesen kann. 01:26:13.900 --> 01:26:14.880 Und that's it. 01:26:14.960 --> 01:26:19.260 Hier sind sie alle nochmal zusammen beschrieben, wie groß also die 01:26:19.260 --> 01:26:20.460 Instanz wird. 01:26:20.460 --> 01:26:24.740 Die wird schon ziemlich groß, aber insgesamt ist sie immer noch 01:26:24.740 --> 01:26:27.260 beschränkt durch ein Polynom in n. 01:26:30.860 --> 01:26:32.940 Ja, was haben wir heute bewiesen? 01:26:33.200 --> 01:26:38.880 Das war jetzt schon sehr wichtig, auch wenn der Beweis, Satz ist np 01:26:38.880 --> 01:26:43.320 -vollständig, eine größere Konstruktion passt. 01:26:43.640 --> 01:26:46.420 Aber wir haben gezeigt, für ein erstes Problem, das 01:26:46.420 --> 01:26:50.880 Erfüllbarkeitsproblem, dass es np-vollständig ist, dass es in np liegt 01:26:50.880 --> 01:26:56.400 und dass sich alle anderen Sprachen aus np auf dieses Polynomial 01:26:56.400 --> 01:26:57.560 transformieren lassen. 01:26:58.260 --> 01:27:04.500 Und alle anderen Sprachen aus np lassen sich polynomial transformieren 01:27:04.500 --> 01:27:05.440 auf das. 01:27:05.840 --> 01:27:08.860 Das haben wir auf dem harten Weg gemacht, indem wir für jede dieser 01:27:08.860 --> 01:27:13.960 Sprachen sagen, naja gut, da gibt es eine nicht-deterministische 01:27:13.960 --> 01:27:18.540 Turing -Maschine, die die Sprache in Polynomialzeit entscheiden kann. 01:27:19.440 --> 01:27:23.020 Wir haben die entsprechende akzeptierende Berechnung für eine Instanz, 01:27:23.360 --> 01:27:27.440 für eine Eingabe aus der Sprache, wir haben uns genau angeguckt und 01:27:27.440 --> 01:27:31.240 wie können wir so eine akzeptierende Berechnung, alles was dazu 01:27:31.240 --> 01:27:35.880 gehört, durch Klauseln vollständig beschreiben. 01:27:35.880 --> 01:27:40.580 Wenn man einmal verstanden hat, wie man das macht, für einen 01:27:40.580 --> 01:27:42.580 bestimmten Aspekt, dann kann man es auch für den Rest. 01:27:44.560 --> 01:27:49.700 Die vollständige Beschreibung ist also tatsächlich so, dass dabei die 01:27:49.700 --> 01:27:54.220 Wörter aus der Ausgangssprache genau abgebildet werden auf erfüllbare 01:27:54.220 --> 01:27:55.860 Satzinstanzen. 01:27:57.560 --> 01:28:01.180 Und das Ganze hat nur polynomialen Aufwand, diese ganze Konstruktion, 01:28:01.340 --> 01:28:04.500 und da ist eben dieser zweite Punkt entscheidend, also der erste Punkt 01:28:04.500 --> 01:28:06.800 war jetzt, es gibt eine nicht-deterministische akzeptierende 01:28:06.800 --> 01:28:10.960 Berechnung, der zweite Punkt, und die ist polynomial beschränkt. 01:28:11.320 --> 01:28:16.000 Der Aufwand für diese akzeptierende Berechnung, der geht immer mal 01:28:16.000 --> 01:28:19.880 wieder ein in die Anzahl der Variablen, die Größe der Klauseln, die 01:28:19.880 --> 01:28:20.680 hier gebaut werden. 01:28:22.400 --> 01:28:23.480 Okay, das wäre es für heute.