WEBVTT 00:00:06.690 --> 00:00:17.961 Ich Begrüße sie zur Vorlesung theoretische Informatik, , Wir, Werden. Heute einen ganz wichtigen Satz der 00:00:17.961 --> 00:00:28.278 theoretischen Informatik beweisen den Satz von Google Das Ist ein klassiker der theoretischen Informatik Der 00:00:28.278 --> 00:00:39.809 spielt, eine ganz große Rolle im Zusammenhang mit der großen offenen Frage, ob die Komplexitätsklassen P und n p 00:00:39.809 --> 00:00:53.161 verschieden sind, um Sie daran zu erinnern, was eigentlich p und N P ist, gehe ich nochmal zurück in die Vorlesung am 00:00:53.161 --> 00:01:02.293 Dienstag, erstmal die Definition der Klasse P eigentlich ziemlich harmlos. Wir betrachten eine deterministische 00:01:02.293 --> 00:01:11.483 Touringmaschine, betrachten die Anzahl der Berechnungsschritte, die eine deterministische Touringmaschine bei einer 00:01:11.483 --> 00:01:27.567 Eingabe x macht n worst Case für die Eingabenlänge also unter allen Eingaben Der, länge n schauen wir an wieviele 00:01:27.567 --> 00:01:42.118 Berechnungsschritte werden bei Eingabe bei dieser Eingabe im Worst Case gemacht und sagen, die Klasse P ist gerade die 00:01:42.118 --> 00:01:52.074 Menge der Sprachen oder Probleme, wo die Zeitkomplexitätsfunktion einer deterministischen Touringmaschine Polynomial ist 00:01:52.074 --> 00:02:02.610 in der Eingabelänge Da Ist. Jetzt unabhängig ob die Eingabe aus der vorgegebenen Sprache ist beziehungsweise, ob 00:02:02.610 --> 00:02:11.011 die Eingabe ein Jahr Beispiel oder ein Nein Beispiel unseres Entscheidungsproblems ist, wird einfach für eine beliebige 00:02:11.011 --> 00:02:19.696 Eingabe geschaut. Wieviel Berechnungsschritte macht die deterministische Touringmaschine, bis sie ändert und für die 00:02:19.696 --> 00:02:29.957 Zeitkomplexitätsfunktion schauen wir einfach an wieviele Schritte sind das in Worst Case, gemessen in der Eingabel 00:02:29.957 --> 00:02:42.143 Länge, und wenn eben für jede Eingabe Über Dem alphabetischer sprache ist Polynomial ist oder eben wenn diese 00:02:42.143 --> 00:02:53.687 Zeitkomplexitätsfunktion beschränkt ist durch ein Polynomial in n, dann sagen wir das die Sprache oder das Problem ist 00:02:53.687 --> 00:03:12.115 in P. So die, frage ist Jetzt, was ist dann N, P, N, P ist die Klasse oder die Menge aller Sprachen oder Probleme 00:03:12.115 --> 00:03:21.800 es, für die es eine nichtdeterministische Touringmaschine gibt, deren Zeitkomplexitätsfunktion durch ein Polynom 00:03:21.800 --> 00:03:23.290 beschränkt ist. 00:03:23.800 --> 00:03:36.153 Also das sieht jetzt so ähnlich aus wie bei P, nur statt P steht da Np und statt deterministischer Touringmaschine steht 00:03:36.153 --> 00:03:46.154 da nicht deterministische Tugendmaschine, aber dahinter steht jetzt noch ein bisschen mehr, bei dem man aufpassen muss, 00:03:46.154 --> 00:03:54.389 nämlich die Arbeitsweise einer Einer Nichtdeterministischen touringmaschine macht Es ein bisschen ja schwieriger 00:03:54.389 --> 00:04:02.037 zu sagen, was ist denn eigentlich die Zeitkomplexitätsfunktion Denn Bei einer nichtdeterministischen 00:04:02.037 --> 00:04:12.037 Turingmaschine kann ja bei ein und derselben Eingabe die Berechnungen jeweils anders aussehen, dann muss man als 00:04:12.037 --> 00:04:20.273 allererstes Mal sich überlegen, was heißt denn eine, dass eine nichtdeterministische Touringmaschine eine Eingabe 00:04:20.273 --> 00:04:29.097 akzeptiert, und wir sagen, eine nichtdeterministische Tunmaschine akzeptiert eine Eingabe genau dann, wenn es eine 00:04:29.097 --> 00:04:39.000 Berechnung gibt, die bei dieser Eingabe in akzeptierenden Endzustand hält. Also es muss nur eine einzige geben und 00:04:39.000 --> 00:04:47.713 dementsprechend wird für die Laufzeitfunktion eben auch danach geschaut. Was braucht denn diese eine? ich sag' Mal, 00:04:47.713 --> 00:04:59.783 beste berechnung der Nichtdeterministischen Turingmaschine im positiven Fall also, wenn die Eingabe akzeptiert wird, das 00:04:59.783 --> 00:05:07.830 heißt die Zeitkomplexitätsfunktion für die nichtdeterministische Touringmaschine ist Folgendermaßen definiert. 00:05:08.509 --> 00:05:18.670 Das ist das Maximum. Hier steht Maximum wieder für den Worst Case von A Eins gehen wir gleich straff ein und Anzahl M. 00:05:19.600 --> 00:05:30.027 Es gibt eine Eingabe aus der vorgegebenen Sprache ell zur Touringmaschine mit Eingabelänge n, so dass die Zeit, die m 00:05:30.027 --> 00:05:41.497 benötigt, um x zu akzeptieren, gerade m ist ja also gerade m, die die Touringmaschine m adm Schritte macht, um x zu 00:05:41.497 --> 00:05:49.840 akzeptieren und bei der Definition von Zeit haben wir gesagt, die Zeit, die eine Nichtdeterministeturingmaschine M. 00:05:49.850 --> 00:05:59.277 Benötigt, um ein Wort X aus der Sprache der Thüringmaschine zu akzeptieren ist definiert als die Minimale In zahl Einen 00:05:59.277 --> 00:06:08.285 schritten Die die Touringmaschine macht bei Eingabe von x um in den akzeptierenden Endzustand zu kommen. Also da ist 00:06:08.285 --> 00:06:15.563 sozusagen Ein Unterschied, gegenüber der deterministischen Tumaschine, wo bei der Eingabe immer dasselbe läuft 00:06:15.563 --> 00:06:24.782 hier, schauen Sie sozusagen die positiven Fälle an, also die Eingaben, die auch wirklich akzeptiert werden, und für jede 00:06:24.782 --> 00:06:31.574 dieser Eingaben kann es jetzt die verschiedensten Berechnungen der nicht deterministischen Touringmaschine geben aber 00:06:31.574 --> 00:06:38.852 umzuschauen, welche Zeit ist relevant für die Laufzeit , Oder, Zeitkomplexitäts Funktion, Der, Nicht 00:06:38.852 --> 00:06:47.241 deterministischen Turniermaschine schaue ich mir sozusagen den besten Fall an, ja? also die Berechnung, die Ihnen 00:06:47.241 --> 00:06:55.756 akzeptieren in einen akzeptierten Endzustand führt oder den akzeptierten Endzustand führt mit Minimaler 00:06:55.756 --> 00:07:07.313 Berechnungslänge, Also Da will ich sie nur nochmal darauf hinweisen, dass es hier nicht so Ja vielleicht erstmal 00:07:07.313 --> 00:07:15.220 nicht so offensichtlich ist wie eigentlich die Laufzeit oder Zeitkomplexitätsfunktion Nicht Deterministischen 00:07:15.220 --> 00:07:27.384 tourismus Definiert Ist also zur Berechnung wird für jedes x aus der Sprache der Touringmaschine, der länge N die 00:07:27.384 --> 00:07:37.724 kürzeste akzeptierende Berechnung zugrunde gelegt und dann wieder für verschiedene Eingaben der länge n der Worst Case 00:07:37.724 --> 00:07:49.889 und diese eins hier brauchen wir nur für den Fall Dass Es, für eine bestimmte Eingabelänge überhaupt keine Eingabe 00:07:49.889 --> 00:08:04.487 gibt, die akzeptiert wird oder die in der Sprache l Ist ja Gut Also die Klasse n P ist die Menge aller 00:08:04.487 --> 00:08:13.002 Sprachen elf, für die es eine nicht deterministische Turmmaschine Gibt deren, laufzeit Oder Zeitkomplexitätsfunktionen 00:08:13.002 --> 00:08:25.167 Polynomial beschränkt ist also, dass P und N P in beiden Fällen geht es darum, ich sprachen sozusagen oder Probleme 00:08:25.167 --> 00:08:33.074 herzunehmen, Die polynomial polynomiell Beschränkt Ist also deren Zeitkomplexitätsfunktion Polynomielles aber in 00:08:33.074 --> 00:08:42.806 dem einen Fall jetzt um eine deterministische Touringmaschine und im anderen um eine Nicht-Deterministische tunnel 00:08:42.806 --> 00:08:52.930 Gut Jetzt ist eben unsere ganz große Frage wie verhalten sich diese beiden Klassen zueinander? 00:08:54.009 --> 00:09:03.518 eins ist natürlich klar die Klasse P ist eine Teilmenge der Klasse. Np also, wenn es eine deterministische 00:09:03.518 --> 00:09:12.661 Touringmaschine gibt Für Eine sprache die Polynomial, Polynomiell Beschränkt Ist dann gibt, es natürlich 00:09:12.661 --> 00:09:16.089 auch eine nichtdeterministische Turniermaschine Polynomiell beschränkt. 00:09:17.049 --> 00:09:27.089 Aber die nächste Frage ist ist P eine echte Teilmenge von Np, oder sind die beiden Klassen dann am Schluss doch gleich, 00:09:27.089 --> 00:09:38.497 also gibt es noch irgendwas in Np, was nicht in p liegt, das ist die große Frage, die Vermutung ist ja, da gibt es was 00:09:38.497 --> 00:09:47.168 ja Andersrum ausgedrückt Vermutung ist, dass P und Np verschieden sind, wenn man sich konkrete Probleme anschaut, in Np 00:09:47.168 --> 00:09:55.838 und den man bisher noch nicht weiß, ob sie in P sind, weil man bisher noch keinen deterministischen Polynomiellen 00:09:55.838 --> 00:10:04.965 Algorithmus zur Lösung des Problems hat Wenn Man, die sich genauer anguckt, dann sagt einem die Intuition oft ja 00:10:04.965 --> 00:10:13.635 Das muss, so sein dass die sozusagen außerhalb von P liegen ja, die sehen also teilweise wirklich, irgendwie 00:10:13.635 --> 00:10:23.674 schwerer aus als die Probleme in P Frage ist wie kann man diese ja schwersten Probleme in Np, die die Kandidaten sind 00:10:23.674 --> 00:10:30.520 nicht in Peking liegen, wenn P und Np verschieden sind, wie kann man die identifizieren? 00:10:31.100 --> 00:10:40.052 ja, das ist sozusagen eine geeignete Definition für ein Problem oder eine Sprache gehört zu den Schwersten, 00:10:40.052 --> 00:10:50.585 beispielsweise Sprachen in Np Sprache oder ein Problem ist ein Kandidat dafür, nicht im P zu sein, wenn sich rausstellt, 00:10:50.585 --> 00:11:02.171 dass Np und P verschieden sind, darum geht es heute also, solche Kandidaten zu identifizieren, die P und N P trennen und 00:11:02.171 --> 00:11:13.230 der Satz von Cook spielt da eine ganz entscheidende Rolle, weil der sozusagen der erste Satz ist, bei dem so ein 00:11:13.230 --> 00:11:22.182 Kandidat von Problem identifiziert wurde ja, die man sozusagen gleich geeignet definiert haben, was bedeutet ein Problem 00:11:22.182 --> 00:11:34.821 gehört zu den schwersten in Np, wenn man dann mit dem Satz von Cook zeigen, und das ist so eins das folgende Problem ist 00:11:34.821 --> 00:11:45.881 so eins so um diese schwersten Probleme in Np ja zu identifizieren, folgen wir von der Idee, das sollen Probleme sein, 00:11:45.881 --> 00:11:57.993 für die gilt, wenn von denen sogar eins in p liegt, dann muss das automatisch bedeuten, dass p gleich Np ist, das heißt 00:11:57.993 --> 00:12:09.895 also, wenn von den schwersten in n? p eins in p liegt also ersten in n? P dies so ein Eine Deterministische 00:12:09.895 --> 00:12:18.709 polynomial beschränkte Touringmaschine finden dann finden wir automatisch auch für alle anderen in Np eine Polynomie 00:12:18.709 --> 00:12:26.421 beschränkte deterministische Tonmaschine, dann können wir alle anderen mithilfe von, sag mal den Polynomiellen 00:12:26.421 --> 00:12:36.336 Algorithmus für das eine auch in Polynomialzeit lösen also Polynomial, das eine mit Pulli nur Polynomiellen aufwand in 00:12:36.336 --> 00:12:47.121 das andere zu überführen. Das ist sozusagen die Kernidee, um die schwersten Probleme in N? p zu definieren und deshalb 00:12:47.121 --> 00:12:57.688 definieren wir jetzt also eine polynomiale Transformation, die eine Sprache in andere überführt Eine Polynomiale 00:12:57.688 --> 00:13:11.556 transformation einer Sprache l Eins " über dem Alphabet Sigma Eins In eine Sprache l zwei über dem Elfabet Sigma 00:13:11.556 --> 00:13:25.425 zwei ist nichts anderes als eine Funktion, die worte aus Sigma eins Stern in Worte auf Sigma zwei Stern abbildet und 00:13:25.425 --> 00:13:35.331 folgende Eigenschaften hat Erstmal Können sie mit Pulymialen berechnen also es existiert eine polynomiale, 00:13:35.331 --> 00:13:47.218 deterministische Touringmaschine, die diese Funktion und zweitens gilt für jedes Wort aus Sigma eins Stern, das Wort ist 00:13:47.218 --> 00:14:02.407 aus unserer Sprache L Eins genau dann, wenn f von dem Wort also das Bild des Wortes in L zwei ist diese polynomiale 00:14:02.407 --> 00:14:14.294 Transformation, die soll ja dazu dienen, dass wir, wenn wir jetzt für l zwei etwa eine polynomiale, deterministische 00:14:14.294 --> 00:14:22.879 Touringmaschine hätten, die auch benutzen könnten, um L eins Polynomiell deterministisch zu entscheiden. 00:14:24.740 --> 00:14:33.575 Dafür muss es erstmal so sein, dass sozusagen den Aufwand von L? eins nach L? zwei zukommen, dass der nur Polynomial 00:14:33.575 --> 00:14:44.165 ist, und es muss aber auch so sein. Also die diese Transformation muss aber auch so sein, dass man dann tatsächlich mit 00:14:44.165 --> 00:14:51.748 einer deterministischen Polynomiellen Touringmaschine für l zwei auch l eins entscheiden können, deshalb muss es so 00:14:51.748 --> 00:15:02.649 sein, dass genau die Worte aus " L eins " auf Worte aus L zwei abgebildet werden, denn dann könnten wir folgendes machen 00:15:02.649 --> 00:15:10.232 wenn wir eine polynomiale Thüringmaschine für L zwei hätten, dann könnten wir damit auch polynomial deterministisch, 00:15:10.232 --> 00:15:19.712 also , L, Eins entscheiden indem wir, einfach eine Eingabe aus Sigma, ein Stern, für die uns interessiert, ist die 00:15:19.712 --> 00:15:31.244 in L. Eins hernehmen würden, da drauf f anwenden würden und dann auf f also Bild dieser Eingabe beschränkte 00:15:31.244 --> 00:15:40.644 deterministische tugenmaschine von L zwei anwenden würden, dass wir da insgesamt nur einen Aufwand betreiben, bleibt 00:15:40.644 --> 00:15:55.332 dann, und wir können gerade weil die Worte aus " L Eins " genau auf Wort aus L zwei abgebildet werden, dann auch l eins 00:15:55.332 --> 00:16:07.153 entscheiden. Also können Sie sich das so vorstellen und deshalb hier dieses Zeichen, dieses wie so ein unendlich 00:16:07.153 --> 00:16:18.461 Zeichen, was rechts offen ist, wenn Sie so eine polynomiale Transformation von L Eins in l zwei haben, dann können Sie 00:16:18.461 --> 00:16:30.602 das interpretieren als l zwei ist mindestens so schwer wie l eins oder l? eins ist nicht schwerer als l zwei, und wir 00:16:30.602 --> 00:16:41.828 sagen dann auch L eins ist polynomial transformierbar in L zwei oder auch L zwei ist Reduzierbar Auf l eins nämlich, das 00:16:41.828 --> 00:16:51.012 verwenden wir dann um sozusagen ja schwierigkeit Von problemen Zu beweisen also, ein Problem ist, gehört zu den 00:16:51.012 --> 00:17:01.217 schwersten, indem wir das zurückführen auf ein anderes, von dem wir schon wissen, es gehört zu den schwersten, das ist 00:17:01.217 --> 00:17:07.851 derselbe Mechanismus wie der Mechanismus, den wir für Nichtberechenbarkeit angewendet haben, also dieses 00:17:07.851 --> 00:17:16.525 Reduktionsprinzip definieren wir als erste in Np sozusagen den Begriff Np vollständig eine Sprache heißt Np vollständig, 00:17:16.525 --> 00:17:27.404 falls gilt die Sprache ist in N, P und alle anderen Sprachen, l Strich, aus n p? lassen sich polynomial transformieren 00:17:27.404 --> 00:17:38.378 auf L damit haben wir sozusagen, sag mal eine gute Definition dafür, Was die, schwersten sprachen in Np oder 00:17:38.378 --> 00:17:47.157 entsprechend die schwersten Probleme in Np sind nämlich diese Np vollständigen, es steht genau dasselbe nochmal 00:17:47.157 --> 00:17:57.034 formuliert für Probleme, denn wir werden dann relativ bald dazu übergehen, dass wir konkrete Probleme in Graphen, Oder 00:17:57.034 --> 00:18:06.361 Andere Betrachten und für die dann beweisen gegebenenfalls sie sind Np vollständig und das Sprachkonzept dann 00:18:06.361 --> 00:18:15.140 sozusagen in den Hintergrund Rückt Also wir, wissen ja jetzt schon , Sprachen, Und, Entscheidungsprobleme 00:18:15.140 --> 00:18:22.822 oder Entscheidungsprobleme können wir als Sprachen betrachten, indem wir einfach eine entsprechende Kodierung des 00:18:22.822 --> 00:18:28.789 Entscheidungsproblems betrachten. Und dann haben wir eben zu den Jahrbeispielen des Entscheidungsproblems gerade worte 00:18:28.789 --> 00:18:36.064 der entsprechenden Sprache, aber wir werden, wie gesagt, dann ab einem gewissen Punkt überhaupt nicht mehr bei Sprachen 00:18:36.064 --> 00:18:44.146 reden, sondern über Probleme und für die Probleme interessiert uns, gehören die zu den Schwersten aus Mp und deshalb das 00:18:44.146 --> 00:18:51.186 Ganze nochmal formuliert für Entscheidungsprobleme, also ein Entscheidungsproblem. P eins ist Polynomial Transformierbar 00:18:51.186 --> 00:19:04.854 in das Entscheidungsproblem Pi zwei, die Problembeispiele zu P eins abbildet auf Problembeispiele zu P zwei erstmal f 00:19:04.854 --> 00:19:17.004 ist durch einen polynomialen Algorithmus berechenbar, also die Konstruktion, die wir da anwenden, hat nur Polynomialen 00:19:17.004 --> 00:19:28.310 aufwand, gilt für alle Instanzen zum Entscheidungsproblem. P eins ". Die Instanz ist eine Jahrinstanz, genau dann, wenn 00:19:28.310 --> 00:19:37.746 deren Bild unter f Nejahr Instanz für p zwei ist, das ist also jetzt einfach nur das übersetzt, was wir eben für 00:19:37.746 --> 00:19:45.037 Sprachen haben in Entscheidungsproblemen und dann schreiben wir eben dieses p eins ist polynomial transformierbar auf p 00:19:45.037 --> 00:19:54.043 zwei und das Zeichen einfach, das Sie sich merken können , Das, Bedeutet, sowas wie p zwei ist mindestens so schwer 00:19:54.043 --> 00:19:55.329 wie Pi eins. 00:19:56.750 --> 00:20:07.050 Und dann sagen wir, ein Entscheidungsproblem heißt Np vollständig, wenn es erstens in Np ist und zweitens sich alle 00:20:07.050 --> 00:20:11.929 anderen Entscheidungsprobleme aus Np auf dieses Polynomial transformieren lassen. 00:20:12.509 --> 00:20:24.267 Also wenn dieses Entscheidungsproblem mindestens so schwer ist wie alle anderen in Np vielleicht noch einmal 00:20:24.267 --> 00:20:34.640 Entscheidungsproblem, Ist In npd es gibt eine nicht deterministische Touringmaschine wie mit polynomialen Aufwand dieses 00:20:34.640 --> 00:20:45.706 Entscheidungsproblem man entscheiden oder lösen kann, hören wir uns das jetzt zu einmal nochmal vor diese 00:20:45.706 --> 00:20:54.696 nichtdeterministische Tourmaschine läuft ja Folgendermaßen ersten Teil der Berechnung, der nicht deterministisch ist, 00:20:54.696 --> 00:21:06.453 wird irgendwas auf das Band geschrieben nach Konvention links von der Eingabe und dann folgt ein deterministischer 00:21:06.453 --> 00:21:16.827 deterministische Berechnungsphase, in dem sozusagen die Eingabe entschieden wird, eventuell unter Benutzung von dem, was 00:21:16.827 --> 00:21:28.277 in der ersten Phase auf das Band geschrieben wurde, wie kann man das interpretieren? bei einem Entscheidungsproblem kann 00:21:28.277 --> 00:21:36.139 man das Folgendermaßen sich vorstellen, stellen Sie sich nochmal wieder " Trippeling Selesman " vor, also gegeben irgend 00:21:36.139 --> 00:21:45.312 so ein Graf mit Kantengewichten, wir wollen in und unten ein Parameter K und sie wollen entscheiden, gibt es in dem 00:21:45.312 --> 00:21:53.612 Graph eine rundto Die, jeden Knoten genau einmal durchläuft, deren Länge Höchstens K ist, wenn sie sich zu diesem 00:21:53.612 --> 00:21:56.670 Problem eine nicht deterministische polynomiale Berechnung vorstellen. 00:21:57.799 --> 00:22:06.262 Wenn Sie sich aus Folgendermaßen vorstellen, nicht deterministischen Anteil der Berechnung wird einfach eine Permutation 00:22:06.262 --> 00:22:15.289 der Knotenmenge aufs Band geschrieben und in dem deterministischen Anteil der Berechnung wird überprüft, ob diese 00:22:15.289 --> 00:22:27.700 Permutation der Knotenmenge eine Tour der Länge kleiner gleich k ist, wir sagen ja, ein Problem ist in Np, wenn es für 00:22:27.700 --> 00:22:36.163 jedes Jahr Beispiel eine Berechnung der nicht deterministischen Touringmaschine gibt, die nur Polynomialen Aufwand hat 00:22:36.163 --> 00:22:47.446 Ein Jahr beispiel Für T s P haben, dann ist diese sozusagen minimale berechnung Einfach da wird die Permutation 00:22:47.446 --> 00:22:58.495 Hingeschrieben der aufwand Ist einfach Länge dieser Permutation. Ja, Graf hat n knoten, also n eine Verifikation ist 00:22:58.495 --> 00:23:09.588 diese Permutation oder Abfolge der Knoten tatsächlich eine Rundtour der Länge kleiner gleich K, natürlich Polynomial in 00:23:09.588 --> 00:23:23.944 , Größeres, graph und Dass eben diese sagen wir mal dieser Beleg ja, es gibt eine Tour der Länge kleiner gleich k 00:23:23.944 --> 00:23:34.384 in dieser nichtdeterministischen Basis der Berechnung Irgendwie Um himmelfeld das Kostet uns sozusagen nichts, da 00:23:34.384 --> 00:23:41.910 kostet nur soviel, wie es kostet, das da hinzuschreiben, ja? 00:23:42.369 --> 00:23:52.379 okay, , Was, Hier, dran jetzt irgendwie so ein bisschen störend ist Für Den fall dass Sie, für ein konkretes 00:23:52.379 --> 00:24:01.154 Problem, etwa Tsp, beweisen wollen, dass es endlich vollständig ist. Das ist, dass sie nach Definition für alle anderen 00:24:01.154 --> 00:24:12.227 Probleme aus Np zeigen müssen. Es gibt so eine polynomiale Transformation auf mein Problem auf ts? P, das ist, äh, tue 00:24:12.227 --> 00:24:25.636 mich viel, was man da an Aufwand betreiben müsste, ja, die Frage ist kommen wir da noch irgendwie Aus Der nummer 00:24:25.636 --> 00:24:37.159 nochmal Irgendwie raus, Ja, Es, das steckt in diesem harmlosen Lemma hier. Also hier steht jetzt nochmal wieder 00:24:37.159 --> 00:24:46.134 zurück auf Sprachebene, was polynomiale transformation heisst, wie eine polynomiale Transformation definiert ist und man 00:24:46.134 --> 00:24:53.912 kann eigentlich durch Hingucken nicht klar machen, dass zwei polynomiale Transformationen hintereinander ausgeführt, 00:24:53.912 --> 00:25:03.485 wieder eine polynomiale Transformation ist also Polynomiale, transformation ist was transitives also wenn l eins 00:25:03.485 --> 00:25:15.452 polynomial transformierbar auf L zwei ist und L zwei polynomial transformierbar auf L drei Dann ist, auch l eins 00:25:15.452 --> 00:25:25.623 polynomial transformierbar auf L drei ist offensichtlich, ja, ist aber wichtig oder sehr nützlich, wenn Sie zwei 00:25:25.623 --> 00:25:35.760 Sprachen, L. Eins und l? zwei aus n? P haben und l? Eins ist Polynomial transformierbar auf L zwei und l eins ist np 00:25:35.760 --> 00:25:44.505 vollständig, dann folgt dann auch L zwei ist n p vollständig, ja, denn was haben Sie denn l eins Mp vollständig ist, 00:25:44.505 --> 00:25:51.660 dann wissen Sie, nach Definitionen lassen sich alle anderen Sprachen aus Np Polynomial transformieren auf L Eins und 00:25:51.660 --> 00:26:00.051 dann lässt sich jetzt hier noch l eins polynomial transformieren auf l zwei, das heißt alle anderen Sprachen aus n? P 00:26:00.051 --> 00:26:08.678 lassen sich Polynomial transformieren auf l zwei, das heißt also, um für jetzt irgendeine Sprache L zu beweisen, sie ist 00:26:08.678 --> 00:26:16.012 Np vollständig, würde dann ja nur reichen, dass sie eine polynomiale Transformation von einem anderen, einer anderen 00:26:16.012 --> 00:26:25.071 Sprache, von der sie schon bewiesen haben, dass sie Np vollständig ist auf diese angeben können also nicht mehr für alle 00:26:25.071 --> 00:26:32.835 anderen Sprachen aus Np zeigen Sie es bei Ihnen nochmal Sie Sind, Polynomialtransformierbar auf meine Sprache L, 00:26:32.835 --> 00:26:40.169 sondern nur für eine andere Np vollständige Sprache müssen Sie zeigen, sie ist polynomialtransformierbar auf L, das 00:26:40.169 --> 00:26:47.502 heißt also unser Rezept sozusagen, um zu zeigen, jetzt wieder für ein Entscheidungsproblem Formuliert Dass ein, 00:26:47.502 --> 00:26:56.130 entscheidungsproblem pimp vollständig ist, wäre also wir zeigen, es ist in Np und das zweite für ein bekanntes Ende, ein 00:26:56.130 --> 00:27:04.757 py, vollständiges Problem also für Einzug, für das wir uns schon bewiesen haben es ist Fdp vollständig Können Wir 00:27:04.757 --> 00:27:12.953 eine polynome transformation Pi Angeben Jetzt fehlt uns nur der Anfang nicht, wir haben noch für kein 00:27:12.953 --> 00:27:21.581 einziges Problem bewiesen, dass es endlich vollständig ist und diesen Anfang, den leistet der Satz von Cook, den ich am 00:27:21.581 --> 00:27:30.208 Anfang Erwähnt Habe den werden, wir gleich beweisen also sozusagen, wir werden für ein erstes Problem, das ist das 00:27:30.208 --> 00:27:37.973 Erfüllbarkeitsproblem Satt beweisen, dass es irgendwie vollständig ist Ach Jetzt, mal auf dem harten Weg, in dem 00:27:37.973 --> 00:27:44.875 wir tatsächlich zeigen, alle anderen Entscheidungsprobleme aus Np lassen sich Polynomial auf das transformieren und ab 00:27:44.875 --> 00:27:53.503 da könnten wir dann Satt nehmen, um für weitere Probleme zu zeigen, sie sind Np vollständig, nein, indem wir diese 00:27:53.503 --> 00:28:01.267 weiteren sozusagen reduzieren auf Satz oder für die weiteren polynomiale Transformationen von Satz zu den weiteren " äh, 00:28:01.267 --> 00:28:11.262 angeben, ja, dann gucken wir uns mal Satt an, was ist das für ein Problem Erfüllbarkeitsproblem? also geht es um das 00:28:11.262 --> 00:28:22.412 Erfüllen von Logischen formeln Das problem Satt Satt steht für Satty Scibility, sieht Folgendermaßen aus. Wir haben eine 00:28:22.412 --> 00:28:35.026 Menge von Booleschen Variablen, U eins bis u M, die in unegierte oder negierter Form in Klauseln vorkommen und die 00:28:35.026 --> 00:28:45.748 Klauseln, die sind Ja Boolesche, ausdrücke Der Form , Oder, Verbindung von Variablen in negierte oder 00:28:45.748 --> 00:28:50.909 unegierter Form. Also wir haben Variablen, U eins bis U M. 00:28:51.019 --> 00:29:02.432 Die können in negierter oder unelegierter oder negierter Form vorkommen, so nennen wir die auch literale ja, und wir 00:29:02.432 --> 00:29:09.639 haben Klauseln und Klauseln bestehen einfach aus der oder Verbindung von Literalen. 00:29:11.410 --> 00:29:20.647 Und die Frage ist jetzt gibt es eine Wahrheitsbelegung der Variablen, so dass alle diese Klauseln gleichzeitig wahr 00:29:20.647 --> 00:29:29.885 werden, also gegeben eine Menge von variablen Ohne Menge c Von Klauseln über U existiert eine Wahrheitsbelegung 00:29:29.885 --> 00:29:39.123 der Variablen, so dass diese Klauseln alle gleichzeitig den Wahrheitswert wahr haben, gucken wir uns das mal ein 00:29:39.123 --> 00:29:48.874 Beispiel an, also meinetwegen unsere Variablenmenge besteht nur aus den Variablen " U eins " und U zwei, unsere 00:29:48.874 --> 00:29:59.580 Klauselmenge besteht nur aus diesen zwei Klauseln u eins oder nicht? U zwei, die erste Klausel und nicht u eins oder U 00:29:59.580 --> 00:30:10.410 zwei, die zweite Klausel Jetzt ist die frage sind diese Klauseln? u eins oder nicht? U zwei und u eins nicht U 00:30:10.410 --> 00:30:18.329 eins oder U zwei gleichzeitig Erfüllbar Also gibt es eine Wahrheitsbelegung, die, die beide gleichzeitig Schwarm 00:30:18.329 --> 00:30:28.576 macht, ja, die gibt es, das ist hier ganz offensichtlich, nämlich wenn wir einfach sowohl u eins als auch u zwei wahr 00:30:28.576 --> 00:30:38.824 setzen, ja, dann ist die erste Klausel erfüllt, weil U eins wahr ist und die zweite Klausel erfüllt, weil U zwei wahr 00:30:38.824 --> 00:30:39.289 ist. 00:30:40.250 --> 00:30:49.378 Oh, das Erfüllbarkeitsproblem oder Satt besteht also da drin, dass sie für beliebige Menge von Variablen und einer 00:30:49.378 --> 00:30:57.492 beliebigen Menge von Klauseln über dieser variablen Menge entscheiden können, ob es eine Wahrheitsbelegung der Variablen 00:30:57.492 --> 00:31:01.549 gibt, so dass alle Klauseln gleichzeitig erfüllt werden. 00:31:02.099 --> 00:31:10.039 Es sieht eigentlich relativ harmlos aus, ist aber offensichtlich nicht so harmlos. Einfach nochmal, dass sich das nur 00:31:10.039 --> 00:31:19.856 vor Augen führen zwei Beispiele hier zum Beispiel eines da haben Sie eins, zwei, fünf Variablen und hier diese 00:31:19.856 --> 00:31:33.289 Klauselmenge C, oder nicht D, nicht A oder B oder nicht C oder D oder E und nicht C oder D, das steht die ist erfüllbar 00:31:33.289 --> 00:31:43.603 lösbar, das ist eine Jahrinstanz, ja, , Schauen, Wir. Mal kurz nach Wie Machen wir das Ja Meinetwegen 00:31:43.603 --> 00:31:54.397 versuchen wir es mal so hier hinten , Versuchen, Wir, mal die wahr, zu machen, indem wir d gleich wahrsetzen, dann 00:31:54.397 --> 00:32:05.705 müssen wir, um die hier zu erfüllen, C wahr setzen, ja, und dann haben Sie auch schon die Mittlere erfüllt, weil, egal 00:32:05.705 --> 00:32:17.527 wie Sie, E und und B und a belegen, weil durch Wahrsetzen von D auch die Mittlere wahr geworden ist, haben wir ein 00:32:17.527 --> 00:32:28.321 Beispiel, das anscheinend nicht erfüllbar ist, also sie haben die Variablen A, B, C und die Klauselmenge A oder B nicht 00:32:28.321 --> 00:32:39.114 A, nicht B oder C, nicht C, fangen wir auch mal wieder hinten an uns klarzumachen, ob das tatsächlich eine nicht 00:32:39.114 --> 00:32:47.852 erfüllbare Klauselmenge ist Wenn Wir, die klauseln alle gleichzeitig wahr machen wollen, dann müssen wir hier 00:32:47.852 --> 00:33:00.188 hinten auf jeden Fall C falsch setzen, ja damit nicht C wahr wird, so wenn wir C falsch setzen, dann müssen wir um nicht 00:33:00.188 --> 00:33:12.010 B oder C wahr zu machen, nicht B falsch setzen Nicht B wahrsetzen also B falsch setzen, wenn wir B falsch setzen, 00:33:12.010 --> 00:33:21.776 können wir diese vordere Klausel nur wahr machen, indem wir a wahr setzen, den Wahrheitswert wahrgeben Dann Wird, 00:33:21.776 --> 00:33:32.765 aber die Klausel nicht a, okay? also tatsächlich so, dass das hier eine Instanz ist, die nicht erfüllt werden kann, für 00:33:32.765 --> 00:33:38.029 die es keine Wahrheitsbelegung gibt, die alle klauseln, gleichzeitig wahrmachen. 00:33:39.869 --> 00:33:55.182 So, und jetzt haben wir hier den Satz von Cook, der sagt einfach ist n p vollständig, tja, wieso? wie beweist man sowas 00:33:55.182 --> 00:34:05.724 erste Teil ist noch einfach, wir müssen zeigen, Satt ist in N? P, aber der zweite Teil, der ist der Aufwändige, wir 00:34:05.724 --> 00:34:12.099 müssen zeigen, alle anderen Entscheidungsprobleme aus Np lassen sich Polynomial auf Sat transformieren, oder wir gehen 00:34:12.099 --> 00:34:21.338 dann wieder über auf das Sprachkonzept. Wir betrachten die Sprache zu satt, unter einem sinnvollen Kodierungschema 00:34:21.338 --> 00:34:35.016 müssen zeigen, alle Sprachen l aus Np lassen sich Polynomial auf die Sprache transformieren zum ersten Teil Satt ist in 00:34:35.016 --> 00:34:46.976 n? P, da müssen wir uns einfach nur klar machen, das wird für eine beliebige Jahrinstanz von Satt, also eine beliebige 00:34:46.976 --> 00:34:55.982 Instanz von , Die, Erfüllbar, ist auch mit Polynomialem Aufwand für eine vorgegebene Wahrheitsbewegung Belegung der 00:34:55.982 --> 00:35:02.736 Variablen verifizieren können, dass diese Wahrheitsverbelegung tatsächlich alle klauseln, erfüllt uns die 00:35:02.736 --> 00:35:10.616 Wahrheitsbewilligung an, setzen die Variablen oder Literale in unseren Klauseln entsprechend diese Wahrheitsbewegung der 00:35:10.616 --> 00:35:21.873 Variablen war oder falsch und gucken nach, kommt da wahr oder falsch raus, weil jede einzelne Klausel, das ist ein 00:35:21.873 --> 00:35:33.129 Aufwand von , Ja, Anzahl, der Klauseln mal Anzahl der Variablen oder in U von Anzahl der Klausel mal einfach. 00:35:33.139 --> 00:35:46.639 Epija, also das ist ein Aufwand, der natürlich Polynomial ist in der Größe der Instanz, okay? also der erste Teil 00:35:46.639 --> 00:35:58.380 Klar, Und, jetzt zum zweiten Teil wir zeigen für alle Sprachen aus Np, dass sie sich polynomial transformieren lassen 00:35:58.380 --> 00:36:10.120 auf die Sprache Zusagt So, müssen wir zeigen für alle Sprachen aus np werden so eine polynomiale Transformation angeben, 00:36:10.120 --> 00:36:21.861 für die gilt für alle Eingaben aus Sigmar Stern, , Sigma, , Ist Das Alphabet zu vorgegebenen Sprache, dass 00:36:21.861 --> 00:36:36.906 wenn x aus der Sprache ist, dann ist das Bild von x in der Sprache zu l satt und umgekehrt. Also wir müssen für alle 00:36:36.906 --> 00:36:49.753 Sprachen L aus Np eine polygonale Transformation, wenn wir die mal Fl angeben, für die gilt, wenn x in l ist, dann ist f 00:36:49.753 --> 00:37:01.471 l von x in L? Sat, und wenn Fl von x in L. Satt ist, dann ist x in L, was können wir dafür benutzen? also wir müssen 00:37:01.471 --> 00:37:14.364 dieses Fl hier irgendwie bauen, das können wir dafür benutzen, wir können dafür nur benutzen, dass L in Np ist, das 00:37:14.364 --> 00:37:24.187 heißt, dass es zu L eine Nicht-Deterministische touringmaschine Gibt die, mit Polynomialem Aufwand l entscheiden kann, 00:37:24.187 --> 00:37:35.238 ja, dann nehmen wir uns halt diese Thüringmaschine her und gucken uns halt für beliebige Eingaben einer beliebigen 00:37:35.238 --> 00:37:46.290 Sprache l aus Np an, was diese Touringmaschine macht im Laufe der Polynomiellen Berechnung, die zum Akzeptieren der 00:37:46.290 --> 00:37:57.341 Eingabe führt , Und, Das was die, Touringmaschine da macht sozusagen darzustellen über Klauseln, ja, also mit Hilfe 00:37:57.341 --> 00:38:08.392 von Variablen und mit Hilfe von Klauseln versuchen wir das, was die Tuningmaschine da macht eindeutig zu beschreiben, 00:38:08.392 --> 00:38:19.443 und zwar so zu beschreiben, dass, wenn die Eingabe tatsächlich aus unserer Sprache ell ist diese Klauseln erfüllbar, 00:38:19.443 --> 00:38:31.108 sind die Tatsache, dass unsere Parallel in Np ist und damit insbesondere auch in Polynomieller Zeit, durch die eine 00:38:31.108 --> 00:38:40.931 Thüringmaschine entscheidbar ist, spielt dabei natürlich auch eine Rolle, nämlich das wird darin eingehen, dass unsere 00:38:40.931 --> 00:38:51.368 Konstruktion wort aus x auf Eine sattinstanz nur Polynomialen Aufwand erfordert ja, die Sattinstanz ist sozusagen 00:38:51.368 --> 00:39:04.875 nachher in der Größe Polynomiell, beschränkt durch die Eingabe, also das Wort aus L aus Zu Dem gehört und dass wir 00:39:04.875 --> 00:39:18.382 das so sagen können, liegt eben daran, dass wir wissen für so ein x aus l haben wir eine Polynomiell beschränkte nicht 00:39:18.382 --> 00:39:19.610 deterministische Turingmaschine. 00:39:19.739 --> 00:39:30.908 Ja, also m sei diese Tunmaschine üblich durch dieses Tuppel, gegeben mit , Zustandsmenge, Alphabet, Und, So weiter 00:39:30.908 --> 00:39:42.076 und so fort, Akzeptierenden, Endzustand, Ja, Nicht akzeptierten Endzustand q N wir wissen die Laufzeit oder 00:39:42.076 --> 00:39:49.710 Zeitkomplexitätsfunktion dieser Turingmaschine ist durch ein Polynom beschränkt. P von N. 00:39:52.019 --> 00:40:04.290 Jetzt betrachten wir also zu einer beliebigen Sprache aus Np eine beliebige Eingabe x der Länge n und schauen uns nach, 00:40:04.290 --> 00:40:10.193 was eine akzeptierende Berechnung Der Dazugehörigen Polynomiell Beschränkten Nicht-Determin-Maschine Eigentlich 00:40:10.193 --> 00:40:19.307 bei dieser eingabe Macht anzahl der Berechnungsschränke Schritte ist durch das Polynom P von N beschränkt. Dadurch 00:40:19.307 --> 00:40:31.727 können wir schon automatisch sagen, am Schluss kann nur die Stelle Minus P von n bis Plus P von n plus eins des 00:40:31.727 --> 00:40:43.113 Bandes, irgendwas enthalten ja in p von n Zeit, also am Anfang steht ja der Lesesschreibkopf an der Position Null in P 00:40:43.113 --> 00:40:55.016 von n Zeit kann der Maximal bis sozusagen P von n Schritte links davon gehen, oder p von n Schritte rechts davon gehen, 00:40:55.016 --> 00:41:06.919 das heißt also die Position Minus P von n bis plus p von n plus eins können maximal also maximal unter diesen Positionen 00:41:06.919 --> 00:41:16.752 auf dem Band kann irgendwas stehen am Schluss, der es schon mal gut und innerhalb der deterministischen Stufe der 00:41:16.752 --> 00:41:26.584 Berechnung ist genau festgelegt, was zu jedem Zeitpunkt los ist ja also insbesondere, was der Banterinhalt ist in den 00:41:26.584 --> 00:41:35.900 einzelnen Positionen, wo überhaupt, was anderes als Blink steht, das heißt also, es ist genau festgelegt, , Was, 00:41:35.900 --> 00:41:47.285 Der, jeweilige bandinhalt dieser Minus p von n bis plus p von n plus eins Positionen auf dem Band ist genauso ist 00:41:47.285 --> 00:41:56.083 jeweils festgelegt, in welchem Zustand sich die Turingmaschine Befindet und es ist jeweils festgelegt, wo der 00:41:56.083 --> 00:42:05.398 Leseschreibkopf Ist und, das ist jetzt auch der Ausgangspunkt zum Bauen unserer Sattinstanz, nämlich das ist zu einem 00:42:05.398 --> 00:42:14.196 Zeitpunkt I festgelegt, in welchem Zustand die Touringmaschine ist, das können wir durch eine Variable beschreiben die 00:42:14.196 --> 00:42:23.511 zu einem Zeitpunkt, Und Dem zustand genau dann wahr ist, wenn die Touring Maschinenberechnung Tatsächlich Zu 00:42:23.511 --> 00:42:32.309 Dem Zeitpunkt in dem vorgegebenen Zustand ist und genauso können wir durch Variablen die Position des Leseschreibkopf 00:42:32.309 --> 00:42:42.660 Beschreiben und durch variablen Die Bindbandinhalte Der Position minus P Von n bis p von n plus eins beschreiben, 00:42:42.660 --> 00:42:52.492 damit fangen wir jetzt mal an, indem wir also Variablen definieren, über denen dann unsere Klauseln ja aufgebaut werden, 00:42:52.492 --> 00:43:01.808 dafür müssen wir jetzt erstmal normieren wie unsere Zustände und unsere , Symbole, , Indiziert Sind Also wir 00:43:01.808 --> 00:43:12.158 sagen die Zustände aus Q, die seien durchnummeriert in von Q Null bis , Pu, Acht, , Endliche, Anzahl, von 00:43:12.158 --> 00:43:21.473 Zuständen meinetwegen R viele und wir sagen , Der Anfangszustand soll Q Null sein und Der Akzeptierende 00:43:21.473 --> 00:43:32.859 endzustand qj Das ist gerade der mit Index eins, das ist q eins und der Nicht Akzeptierende, endzustand q N, das 00:43:32.859 --> 00:43:43.209 sei gerade der Index Der Zustand mit Index zwei also q zwei und genauso nummerieren wir unsere , Symbole, 00:43:43.209 --> 00:43:54.349 Des, Bandalphabets durch Das, Sind, meinetwegen elf viele oder l plus eins, viele Also in, s null Bis. S l 00:43:54.349 --> 00:44:06.951 und s. Null ist genau das Blinksymbol so und dann bauen wir unsere Variablen auf die also jeweils Den eindeutig 00:44:06.951 --> 00:44:15.655 festgelegten zustand in dem sich die Touringmaschine zu einem bestimmten Zeitpunkt der deterministischen Berechnung 00:44:15.655 --> 00:44:25.169 befindet, beschreiben sollen. Das sind erstmal die Variablen, die zu den Zuständen der entdringlichen Kontrolle gehören. 00:44:25.179 --> 00:44:38.856 Wir nehmen nämlich , , P, Von, N, mal r Variablen von I Komma k? i steht halt für die verschiedenen Zeitpunkte 00:44:38.856 --> 00:44:47.334 unsere deterministischen Berechnungen und die deterministischen Berechnung ist ja in der Zeit beschränkt durch dieses 00:44:47.334 --> 00:44:59.768 Polynom P von N in Eingabegröße und K Ist zwischen null und acht für die r verschiedenen Zustände, oder plus eins 00:44:59.768 --> 00:45:10.506 verschiedenen Zustände, die die Tonmaschine kennt und Q I Komma k ist wahr würde heißen, zum Zeitpunkt I der 00:45:10.506 --> 00:45:18.984 Überprüfungsphase, also der deterministischen Phase der Berechnung ist die Touringmaschine genau im Zustand Qka 00:45:18.984 --> 00:45:28.592 Analog für Die position des Leseschreibkops Der, lese schreibkopf " Kann sich ja maximal befinden zwischen Position, 00:45:28.592 --> 00:45:41.383 Minus, P von N und p von n plus eins, ja? das heißt also, wir führen einen variablen H von I Komma J i steht wieder für 00:45:41.383 --> 00:45:50.408 einen Zeitpunkt ist also zwischen Null und P von N und J steht für eine Position, wo sich ja diese Schreibkopf während 00:45:50.408 --> 00:46:03.531 dieser deterministischen Phase befinden kann. Also J steht zwischen Minus P von N oder J ist Minus zwischen Minus P von 00:46:03.531 --> 00:46:20.798 N und p von n plus eins und paar von i Komma J war soll also bedeuten zum Zeitpunkt I steht der Leseschreibkopf An der 00:46:20.798 --> 00:46:35.303 position J und genauso jetzt für die Bandinhalte Also Für, den zeitpunkt i und eine Position j irgendwo auf dem 00:46:35.303 --> 00:46:50.499 Band, wo was stehen kann, was Unterschiedlich Von blenk ist Gibt Es mögliche symbole s Null bis Sl und die 00:46:50.499 --> 00:47:05.694 Variable Si I Komma J Komma ist wahr, bedeutet zum Zeitpunkt I steht an der Position J das Symbol Eska so , 00:47:05.694 --> 00:47:13.292 Akzeptierende Berechnung, unserer Deterministischen Nicht Deterministischen Türgenmaschine m Betrachten dann 00:47:13.292 --> 00:47:24.343 induziert die ja auf eine natürliche Weise eine Wahrheitsbelegung Denn wir, können während dem deterministischen 00:47:24.343 --> 00:47:35.940 Teil Der Berechnung eben Zu jedem Zeitpunkt nachgucken. Ja, in welchem Zustand ist denn die Turingmaschine und an 00:47:35.940 --> 00:47:45.589 welcher Position steht denn der Leseschreibkopf Und was steht denn an den einzelnen Positionen des Bandes, , Und, 00:47:45.589 --> 00:47:53.093 Für die entsprechenden Möglichkeiten dann die entsprechenden Variablen, Wahrsetzen und alle anderen Variablen falsch 00:47:53.093 --> 00:48:00.343 setzen. Ja, das heißt also so eine Berechnung induziert in kanonischer Weise eine Wahrheitsbelegung dieser variablen 00:48:00.343 --> 00:48:09.729 , , Damit, Muss, Man sich jetzt noch klar machen, dass In Die touringmaschine vor P von n Stop, wir 00:48:09.729 --> 00:48:19.115 sagen ja, also die Berechnung ist beschränkt durch P von N, aber kann ja sein, dass sie weniger lange braucht , 00:48:19.115 --> 00:48:26.712 Und, Sagen wir einfach danach bleibt Die Touringmaschine unverändert Also im selben Zustand und der Bandinhalt 00:48:26.712 --> 00:48:33.863 bleibt unverändert, dann können wir das wirklich auch für sämtliche dieser Variablen Ableiten wie die 00:48:33.863 --> 00:48:41.014 Wahrheitsbelegung ist die durch die Berechnung der Touringmaschine induziert wird Gut Jetzt müssen, wir noch 00:48:41.014 --> 00:48:50.847 weiter gehen und uns überlegen, naja, gut, wie geht das Ganze los und wie endet das ganze Zum Zeitpunkt null Der 00:48:50.847 --> 00:49:00.679 Überprüfungsphase steht die Eingabe an den Stellen eins bis n ja, die Eingabe hat ja länge n und das Orakel, das, was 00:49:00.679 --> 00:49:08.277 vorher in dieser nicht deterministischen Phase der Berechnung gemacht wurde, steht irgendwo links davon also an den 00:49:08.277 --> 00:49:15.875 Stellen Minus Eins bis Minus Länge des Orakels und wegen der polynomialen Beschränktheit unserer ganzen Berechnung ist 00:49:15.875 --> 00:49:24.367 also Länge, Des, Orakels natürlich Kleiner, gleich p von n und ansonsten stehen da überall Planks 00:49:24.367 --> 00:49:31.964 Umgekehrt Ist Es natürlich so also so eine Berechnung induziert also auf kanonische Weise eine Wahrheitsbelegung unserer 00:49:31.964 --> 00:49:38.221 eingeführten Variablen umgekehrt muss es natürlich nicht Sinn machen, wenn wir irgendeine Wahrheitsbelegung der 00:49:38.221 --> 00:49:45.819 Variablen nehmen also irgendwelche , Sätzen Da war, und irgendwelche falsch, dann muss das nicht zu einer 00:49:45.819 --> 00:49:53.864 Berechnung gehören, denn schon in dem Moment finden wir für einen Zeitpunkt für zwei Variablen oder für zwei 00:49:53.864 --> 00:50:01.015 verschiedene Zustände, sozusagen, sagen die entsprechende Variable ist wahr, man hat das nichts mehr mit einer 00:50:01.015 --> 00:50:10.165 Berechnung einer Turniermaschine zu tun? ja, also Wir Hatten, ja diese Variablen q I J für die 00:50:10.165 --> 00:50:20.030 Turingmaschine ist zum Zeitpunkt I im Zustand Qj Wenn wir, jetzt gleichzeitig für Kij und Ki sagen, wie sollen 00:50:20.030 --> 00:50:21.510 beide wahrgesetzt werden? 00:50:22.250 --> 00:50:31.627 J ungleich k und kann das nicht zu einer Brechung der Touringmaschine gehören deine Berechnung der Touringmaschine 00:50:31.627 --> 00:50:38.797 induziert eine Wahrheitsbelegung, , Eine Wahrheitsbelegung, muss Nicht unbedingt zu einer Berechnung der 00:50:38.797 --> 00:50:49.278 Tugenmaschine gehören so, jetzt müssen wir die Transformation F L so bauen, dass wir eben klauseln mit Hilfe dieser 00:50:49.278 --> 00:50:58.103 Variablen, die eine Sattinstanz bilden, die genau dann erfüllbar ist, wenn die zugehörige Berechnung der Touringmaschine 00:50:58.103 --> 00:51:06.929 eine akzeptierende Berechnung ist also die Eingabe, die zu dieser Berechnung gehört eine Eingabe aus unserer 00:51:06.929 --> 00:51:15.755 vorgegebenen Sprache aus Np, also konstruiere Transformation Fl, die Klauseln einführt, so dass äquivalent ist für 00:51:15.755 --> 00:51:24.580 Eingabe x gibt es eine akzeptierende Berechnung, deren Überprüfungsphase Höchstens P von n-zeit Benötigt und deren 00:51:24.580 --> 00:51:36.164 orakel Höchstens Länge P von n hat und es gibt eine erfüllende Belegung für die entsprechende Sattinstanz f l von x 00:51:36.164 --> 00:51:48.851 Wenn Wir, das haben dann können wir Folgendes folgern wenn x aus l ist, dann ist ja das äquivalent dazu, dass es 00:51:48.851 --> 00:52:00.452 eine Akzeptierende berechnung von E m bei Eingabe x gibt und da l noch Voraussetzung aus N? P ist, ist das 00:52:00.452 --> 00:52:09.178 Äquivalent dazu, dass es eine akzeptierende Berechnung von m bei Eingabe x gibt die Höchstens P von n Schritte in der 00:52:09.178 --> 00:52:13.749 Überprüfungsphase braucht und deren Orakel Höchstens Länge P von N hat. 00:52:14.170 --> 00:52:22.090 Und das ist dann äquivalent damit, dass es eine erfüllende Wahrheitsbelegung für die Klauselmenge Fl von x gibt. 00:52:22.440 --> 00:52:32.360 Wenn wir sozusagen so eine Konstruktion Fl angeben können, wie hier beschrieben, dann haben wir unseren Satz bewiesen 00:52:32.360 --> 00:52:43.384 ja, wir werden die Bewegung des Leseschreibkops Wieder durch so ein d darstellen wir eins nach links gehen, nimmt die 00:52:43.384 --> 00:52:55.509 den Wert Minus eins an, für eins nach rechts gehen nimmt die den Wert eins an und für Der Lesesschreibkopf bleibt 00:52:55.509 --> 00:53:07.083 An derselben Stelle nimmt die den Wert Null an Kommen Wir zur konstruktion der Klauseln und damit Sie sehen, wo 00:53:07.083 --> 00:53:17.004 das Ganze hinführt, denn das ist eine längerwierige , Konstruktion, hier Eine übersicht die Klauseln, die sind in 00:53:17.004 --> 00:53:25.272 Gruppen aufgeteilt und jede Gruppe ist verantwortlich für bestimmten , Eine Bestimmte Eigenschaft der 00:53:25.272 --> 00:53:35.193 Berechnung nämlich da gibt es Klauseln, die sind in der Klauselgruppe G eins, die sind dafür verantwortlich, dass 00:53:35.193 --> 00:53:44.562 während der Berechnung zu einem bestimmten Zeitpunkt die Touringmaschine tatsächlich nur in genau einem Zustand ist ja, 00:53:44.562 --> 00:53:53.932 und die Klauselgruppe G zwei ist dafür zuständig, dass zu einem bestimmten Zeitpunkt die Position des Leseschreibkops 00:53:53.932 --> 00:54:04.404 Eindeutig festgelegt ist und die Gruppe drei ist dafür zuständig, dass zu einem festen Zeitpunkt I auf den Positionen 00:54:04.404 --> 00:54:14.325 des Bandes eindeutig festgelegt sind also die Symbole aus im Bandalphabet für jede dieser Positionen zwischen Minus P 00:54:14.325 --> 00:54:26.451 von N und plus b von N plus eins eindeutig festgelegt ist einer Position, steht mehr als ein Symbol, dann müssen wir 00:54:26.451 --> 00:54:35.269 noch genau festlegen, wie die anfangskonfiguration Ist dafür ist die Klauselgruppe G vier Festlegung der Anfangskomben, 00:54:35.269 --> 00:54:46.292 , Konfiguration, Also, Was, Ist zum Zeitpunkt Null der Phase Naja Gut, da, ist die Tonmaschine im Zustand Ku 00:54:46.292 --> 00:54:58.969 Null, der lese Schreibkops steht an der Position Eins des Bandes und an den Zellen Eins Bis n steht die Eingabe x, 00:54:58.969 --> 00:55:10.543 die irgendwie die Form hat Ska Eins Bisskn und dann die Klauselgruppe G fünf, die ist für das Ende der ganzen 00:55:10.543 --> 00:55:19.362 Angelegenheit, , zuständig nämlich dass, zum Zeitpunkt p von N die Drühmmaschine Den akzeptierenden endzustand Coj 00:55:19.362 --> 00:55:29.283 erreicht hat und b sechs, und das ist die schwierigste klauselgruppe Ist dafür zuständig dass, wir tatsächlich vom 00:55:29.283 --> 00:55:38.653 Übergang, vom Zeitpunkt, beim Übergang vom Zeitpunkt i zum Zeitpunkt i plus eins, genau eine Anwendung der 00:55:38.653 --> 00:55:47.471 Übergangsfunktion Delta haben Am Schwierigsten zu Formalisierendes also g sechs steht dafür, dass zu jedem 00:55:47.471 --> 00:55:56.290 Zeitpunkt I die Konfiguration Der touringmaschine Im folgezeitpunkt Aus einer einzigen Anwendung von Delta auf die 00:55:56.290 --> 00:56:05.659 Situation zum Zeitpunkt I okay, also legen wir mal los, das ist jetzt nur noch Arbeit, ja? 00:56:06.449 --> 00:56:15.347 also das erste und das verstanden haben, dann werden wir das zweite und dritte und vierte und fünfte verstehen 00:56:15.347 --> 00:56:23.799 Also Es, geht darum dass zu einem bestimmten Zeitpunkt die Touringmaschinen nur in genau einem Zustand sein kann, das 00:56:23.799 --> 00:56:31.806 heißt sie ist in irgendeinem Zustand, aber auch nicht gleichzeitig in zwei Zuständen, das müssen wir durch logische 00:56:31.806 --> 00:56:38.924 formeln Ausdrücken die, so aussehen wie unsere Klauseln aussehen müssen, nämlich einfach nur oder Verbindung von 00:56:38.924 --> 00:56:48.266 Literalen ist die Variablen, die hier eine Rolle spielen sind gerade diese Q, I, J waren ja genau dafür zuständig 00:56:48.266 --> 00:56:54.159 Kij Steht dafür zum Zeitpunkt I ist die Turnmaschine im Zustand. 00:56:56.460 --> 00:57:05.792 Wir können ausdrücken, dass die Touringmaschine zum Zeitpunkt I in mindestens einem Zustand ist, indem wir sagen Q i 00:57:05.792 --> 00:57:17.632 Null oder Q i Eins, oder oder oder Pu Ir, also eins von denen muss wahr sein für i zwischen Null und P von N, also für 00:57:17.632 --> 00:57:27.280 jeden Zeitpunkt ja wohl gemerkt, dass hier steht für Q Nullzustand, Q Null und so weiter und das hier hinten, das r 00:57:27.280 --> 00:57:36.489 steht für Zustand, Qr, wir haben r plus eins verschiedene Zustände, so wenn die Klausel wahr wird, dann wissen wir also 00:57:36.489 --> 00:57:45.698 zum Zeitpunkt für jedes I, dass wir für jedes I zum Zeitpunkt I ist die Turingmaschine in mindestens einem Zustand soll 00:57:45.698 --> 00:57:54.469 aber nur in genau einem Zustand sein, das heißt also, wir brauchen auch noch Klauseln die Gewährleisten, dass nicht zwei 00:57:54.469 --> 00:58:05.871 dieser Q I J, also kein Q I J gleichzeitig wahr wird mit einem Qi, und dafür führen wir noch i j j Strich ein die, 00:58:05.871 --> 00:58:16.396 klauseln Nicht q I, J oder nicht Q I J Strich, das Heißt ja, nur es Kann nicht gleichzeitig sein Dass 00:58:16.396 --> 00:58:26.482 Q, i J und Cij Strich, beide wahr sind Okay So nach, dem Schema können wir jetzt genauso auch beschreiben, dass zu 00:58:26.482 --> 00:58:34.376 jedem Zeitpunkt der Leseschreibkopf Nur an genau einer Stelle ist wir beschreiben erstmal, dass er diese Schreibkopf an 00:58:34.376 --> 00:58:43.585 irgendeiner Stelle ist und dann das aber an mich, an zwei Stellen gleichzeitig ist es ist heißt also wieder, wir nehmen 00:58:43.585 --> 00:58:51.479 die Variablen her, die für Position des Jesus Schreibkopf zuständig sind, das sind diese variablen Haar , Und, 00:58:51.479 --> 00:59:00.249 Machen erstmal die oderverbindung Als dieser Variablen a zu einem Zeitpunkt i und das für alle Zeitpunkte I. 00:59:00.260 --> 00:59:08.639 Damit haben wir beschrieben, wenn die wahr werden, dann heißt es zu jedem Zeitpunkt ist die Der Leseschreibkopf 00:59:08.639 --> 00:59:17.019 der Trendmaschine An irgendeiner Position aber es könnte immernoch sein, dass er an zwei Positionen ist, was nicht zu 00:59:17.019 --> 00:59:24.075 einer ordnungsgemäßen Berechnung gehört, also müssen wir gleichzeitig noch Ausschließen Dass er, zum Zeitpunkt i 00:59:24.075 --> 00:59:33.431 an zwei Positionen ist, also führen wir außerdem noch die ganzen Klauseln, nicht Hi? j oder nicht, Hi? J Strich, für 00:59:33.431 --> 00:59:45.691 alle paare j strich ein und das für alle Zeitpunkte I selbe Schema wie eben bei Der Klauselgruppe eins Und auch 00:59:45.691 --> 00:59:56.836 bei der Klausel Gruppe drei sieht es genauso aus, also es folgt demselben Schema Klausel Gruppe drei ist ja dafür 00:59:56.836 --> 01:00:06.309 zuständig vollständig zu beschreiben, dass zu jedem Zeitpunkt an jeder Position des Bandes, der Bandinhalt eindeutig für 01:00:06.309 --> 01:00:18.568 den Brandel Inhalt zuständig sind diese s Variablen und nochmal so eine Variable Si J A steht für zum Zeitpunkt I steht 01:00:18.568 --> 01:00:31.385 an der Position J das Symbol Esk nun müssen wir für alle Zeitpunkte und alle Positionen erstmal sagen " Ja " zu dem 01:00:31.385 --> 01:00:40.858 entsprechenden Zeitpunkt an der entsprechenden Position, entweder das erste Symbol aus Gamma, oder das zweite Symbol aus 01:00:40.858 --> 01:00:52.003 Gamma, oder oder oder was sind diese Formeln hier, wenn so diese Formel wahr werden könnte, aber immernoch sein, dass 01:00:52.003 --> 01:01:00.919 das bedeutet an einer Position stehen zwei verschiedene Symbole, was nicht zu einer ordnungsgemäßen Berechnung gehört, 01:01:00.919 --> 01:01:11.507 das heißt also, das müssen wir wieder ausschließen, und es geht wieder nach demselben Prinzip wie bei den vorherigen 01:01:11.507 --> 01:01:23.767 Klauselgruppen und gleichzeitig muss gelten, gelten für alle i zwischen Null und P von N für alle J zwischen Minus P von 01:01:23.767 --> 01:01:37.698 m und plus p von n plus eins, und alle Paare Kk strich zwischen null Und l sij K, nicht wahr ist, oder Sijk Strich 01:01:37.698 --> 01:01:39.370 nicht, wahr okay? 01:01:40.110 --> 01:01:47.918 alte, Klausel Gruppe vier ist dafür zuständig, die anfangskonfiguration Zu beschreiben die, anfangskonfiguration ist die 01:01:47.918 --> 01:01:58.849 thüringungsmaschine ist am Anfang im Zustand Q Null, das heißt zum Zeitpunkt Null ist im Zustand Q Null, das heißt also 01:01:58.849 --> 01:02:10.301 die Variable Q Null muss auf jeden Fall wahr und der Schreibkopf steht An der Stelle eins des Bandes, das heißt 01:02:10.301 --> 01:02:23.315 die A Null komma Eins Muss auf jeden Fall wahr werden und in den Stellen Eins bis n steht die Eingabe x, das 01:02:23.315 --> 01:02:33.726 ist das Wort Ska Eins Bisskn nach dem, was wir uns vorgegeben haben, , Dementsprechen, Müssen also die Variablen s 01:02:33.726 --> 01:02:43.616 Null Null, also Null für Zeitpunkt, Null die zweite Null für Position Null enthält , Blenksymbol, Und, Dann, Genau 01:02:43.616 --> 01:02:56.630 und dann ab , Position, Eins, Also Zu s Null Eins enthält Ska Eins und so weiter bis S Null N enthält Ska N , 01:02:56.630 --> 01:03:09.328 Und, Alle anderen positionen enthalten wieder ein plenk Also, für s Null n plus eins bis s. Null P von N plus eins muss 01:03:09.328 --> 01:03:20.874 die dritte Position wieder null sein so und am Ende der Berechnung muss qj erreicht sein, das heißt also für den 01:03:20.874 --> 01:03:34.070 Zeitpunkt P N wir wissen ja Spätestens zum Zeitpunkt P N ist die Berechnung zu Ende muss der Zustand uj sein und Kuj war 01:03:34.070 --> 01:03:47.266 ja gerade als q eins gesetzt, das heißt also die Variable P von n eins muss auf jeden Fall wahr sein, so, und jetzt 01:03:47.266 --> 01:03:56.063 kommen wir zu dem nochmal ein bisschen schwierigeren, teil Jetzt, müssen wir sozusagen die Übergänge der 01:03:56.063 --> 01:04:04.860 Überprüfungsphase Von einem Zeitpunkt Zum nächsten durch Formeln beschreiben also es muss gelten zu jedem 01:04:04.860 --> 01:04:14.244 Zeitpunkt. Je folgt die Konfiguration Der touringmaschine Zum folgezeitpunkt I plus eins aus genau einer einzigen 01:04:14.244 --> 01:04:25.422 Anwendung der Übergangsfunktion Delta auf die von Konfiguration Von m zum zeitpunkt I das müssen wir durch Formeln aus 01:04:25.422 --> 01:04:36.012 und dafür benutzen wir zwei Gruppen von Formeln oder Klauseln Gruppe sagt, ist dafür zuständig, dass folgendes 01:04:36.012 --> 01:04:47.190 Gewährleistet Ist wenn die, Thüringmaschine zum Zeitpunkt i an der Position J das Symbol es K hat und der 01:04:47.190 --> 01:05:00.133 Leseschreibkopf An der position J steht dann hat m auch zum Zeitpunkt i plus eins an Position J nochmal, und der diese 01:05:00.133 --> 01:05:11.312 Schreibkopf nicht an Positionen J steht also, wenn an Position J das Symbol Esk steht und der Lesesschreibkopf irgendwo 01:05:11.312 --> 01:05:23.666 anders steht, dann ist auch zum nächsten Zeitpunkt an der Position J das Esk, denn das wird ja nur der Bankinhalt 01:05:23.666 --> 01:05:32.491 möglicherweise geändert an der Position, wo der Leseschreibkopf Ist an allen anderen Positionen bleibt alles 01:05:32.491 --> 01:05:41.674 unverändert. Ja, das heißt also, wir brauchen Formeln, die gewährleisten, dass falls die Touringmaschine m zum Zeitpunkt 01:05:41.674 --> 01:05:53.477 I an der Position J das Symbol Sk hat und der Leseschreibkopf Nicht an der position J ist dann hat die Thüringmaschine 01:05:53.477 --> 01:06:04.207 auch zum Zeitpunkt i plus eins an der Position J, das Symbol Ska und die zweite Klauselgruppe ist dafür zuständig, 01:06:04.207 --> 01:06:13.541 tatsächlich den Übergang zu machen. Also das, was sozusagen passiert, wenn zum Zeitpunkt I die Thüringmaschine im 01:06:13.541 --> 01:06:25.262 Zustand Kukar ist und der lese Schreibkopf an der Position Ij. Und da ein bestimmtes Symbol ist und für diese Situation 01:06:25.262 --> 01:06:35.962 Delta sagt der Folgezustand ist an der Position J steht danach folgendes Symbol und der Leseschreibkopf Steht danach ja 01:06:35.962 --> 01:06:46.663 entweder an derselben Stelle oder eins rechts, oder eins links, das sozusagen auszudrücken, so gehen wir zu der ersten 01:06:46.663 --> 01:06:57.364 Klauselgruppe Die ist, ja dafür zuständig dass an den Stellen, wo der Leseschreibkopf Nicht zum zustand zum 01:06:57.364 --> 01:07:08.628 Zeitpunkt auch nichts passiert ja also falls m zum Zeitpunkt i an der Position J das Symbolsk hat und der 01:07:08.628 --> 01:07:19.893 Lesesschreibkopf irgendwo anders ist, dann muss das Symbol Esk auch zum Zeitpunkt i plus eins an der Stelle , J 01:07:19.893 --> 01:07:32.283 Stehen was heißt, das das heißt Sij K und gleichzeitig nicht hij, dann muss si plus eins, Jk erfüllt sein Also 01:07:32.283 --> 01:07:45.237 Sij, k Erfüllt heißt zum Zeitpunkt i steht an der J ist Stelle J das Symbol ist und gleichzeitig soll Kij nicht stimmen, 01:07:45.237 --> 01:07:57.064 das heißt also, ähm, der Lesesschreibkopf ist zum Zeitpunkt I nicht an der Stelle J, dann soll danach auch zum Zeitpunkt 01:07:57.064 --> 01:08:08.420 i plus eins An Der stelle j Das Symbolsk sein. Wir haben also hier eine Formel, die genau beschreibt, was erfüllt 01:08:08.420 --> 01:08:19.168 sein muss, ja für diese Klauselgruppe G Eins die Formel sieht aber noch nicht so aus, wie wir da haben wollen, das ist 01:08:19.168 --> 01:08:27.113 nicht eine Oderverbindung von literalen , Wir, Müssen, diese folgerung jetzt noch als oder Verbindung von literalen 01:08:27.113 --> 01:08:37.394 Ausdrücken und diese Formel ist ja genau dann wahr, wenn entweder das nicht wahr ist oder das nicht wahr ist, oder das 01:08:37.394 --> 01:08:48.609 wahr ist, und wenn es sie war, wenn entweder die beiden wahr sind und das wahr ist, oder eins von den beiden nicht gilt, 01:08:48.609 --> 01:08:57.488 dann ist diese Folgerung wahr, und das ist, anders ausgedrückt, nichts anderes als die Osterverbindung von sij k negiert 01:08:57.488 --> 01:09:00.759 und Aij und si plus eins, Jk. 01:09:01.710 --> 01:09:11.272 Das war jetzt der einzige Schritt, wo wir ein bisschen mehr Logik anwenden müssen als einfach nur was beschreiben, durch 01:09:11.272 --> 01:09:20.357 Variablen Also oder, verbindung von Variablen ja, wir überlegen uns diese Aussage hier, wie kann man die durch 01:09:20.357 --> 01:09:30.322 eine Formel ausdrücken die entsprechende Formel ist , Sij, K, Und, nicht hi j daraus folgt Si plus eins, Jk. Und 01:09:30.322 --> 01:09:37.559 dann das hier als oder Verbindung von Literalen ausdrücken. Dafür muss man einfach überlegen, wann ist dies hier wahr? 01:09:37.569 --> 01:09:49.771 das ist genau dann war, wenn entweder das nicht wahr ist oder das nicht weiß, oder das weiß, und mit der zweiten 01:09:49.771 --> 01:09:59.755 Klauselgruppe geht es dann wieder nach dem selben Schema, die zweite Klauselgruppe, die soll ja jetzt tatsächlich die 01:09:59.755 --> 01:10:09.184 Übergangsfunktion beschreiben , Delta, Von, Der situation zu Ringmaschine Ist im zustand Koka Und Liest 01:10:09.184 --> 01:10:20.276 Der Lese schreibkopf liest esm ist danach Institute im Zustand Q Kapa An Der stelle wo Der, Leseschreibkopf Gerade 01:10:20.276 --> 01:10:31.695 war steht, jetzt Smü Und. Danach steht der Leseschreibkopf An der aktuellen position Plus d ja, deshalb haben wir d als 01:10:31.695 --> 01:10:41.409 Minus Eins, Null oder Eins gesetzt, irgendein Zustand, der nicht Endzustand ist Ansonsten Ist, sowieso klar was 01:10:41.409 --> 01:10:54.362 hier steht, dann ist nämlich Pu Kapa gleich Q, K und S, My gleich Sm und d gleich Null für all die anderen situation 01:10:54.362 --> 01:11:05.156 müssen wir also folgendes haben, um das hier zu beschreiben, diesen Schreibkopf steht zum Zeitpunkt I an der Stelle J 01:11:05.156 --> 01:11:17.030 und die Touringmaschine ist zum Zeitpunkt I Im Zustand qk Und An Der Zum Zeitpunkt I steht an der 01:11:17.030 --> 01:11:29.443 Stelle J, dann muss zum Zeitpunkt i plus eins Elise Schreibkopf an der Stelle j plus d stehen, ja, das ist jetzt erstmal 01:11:29.443 --> 01:11:39.158 das hier realisiert und zusätzlich, wenn der Lesesschreibkopf zum Zeitpunkt I an der Stelle J steht und die 01:11:39.158 --> 01:11:52.650 Turinmaschine zum Zeitpunkt I im Zustand Q K ist und an der Stelle I an der Stelle J zum Zeitpunkt I Sm steht, dann muss 01:11:52.650 --> 01:12:03.984 Vitamine Zum Zeitpunkt i Plus eins im Zustand Qkapa sein, das ist sozusagen das hier realisiert und das dritte Pij 01:12:03.984 --> 01:12:17.828 und Q, I, K und Si, J M gilt, dann muss si plus eins j Mü. Gelten. Also dann soll danach an der Stelle J, dass es Müh 01:12:17.828 --> 01:12:26.390 stehen, also diese drei Folgerungen müssen alle drei gleichzeitig wahr werden, und da wissen wir jetzt, wie wir so eine 01:12:26.390 --> 01:12:34.096 Folgerung in eine oder Verbindung übersetzen, indem wir das vordere negieren und mit dem hinteren Veruddern Das 01:12:34.096 --> 01:12:43.925 Heißt, also für diese erste Folgerung bekommen wir die Klausel nicht Hi oder nicht Ku I K oder nicht? Sij M oder Aij 01:12:43.925 --> 01:12:52.772 plus hi plus eins j plus d und genauso für die zweite Folgerung kriegen wir diese Oderverbindung und für die dritte 01:12:52.772 --> 01:13:02.369 Folgerung, diese Oderverbindung und all diese Klauseln kriegen wir sozusagen für alle I. Ignore , Time, , 01:13:02.369 --> 01:13:23.334 Segment, , In, , Scoring, Zustände Und Für alle m zwischen Null und l? m steht ja immer für den Index des 01:13:23.334 --> 01:13:36.225 Symbols, das an einer bestimmten Stelle steht unsere Konstruktion f? l bildet jetzt einfach die Eingabe ab unter 01:13:36.225 --> 01:13:43.742 Benutzung der Überprüfungsphase unserer Nicht deterministischen touringmaschine bei Eingabe x auf diese 01:13:43.742 --> 01:13:57.619 Klauselmenge, ja, das sind die Klauseln zu g eins und die Klauseln zu g zwei und so weiter und so fort, und die müssen 01:13:57.619 --> 01:14:09.761 alle gleichzeitig wahr werden, wenn Oder erfüllbar sein wenn das, x aus der Sprache ist Jetzt Ist, es aber 01:14:09.761 --> 01:14:21.903 so dass Wenn X, aus der Sprache ist dann sind halt gerade genau die Klauseln erfüllbar, denn so sind sie 01:14:21.903 --> 01:14:30.576 Konstruiert und andererseits, wenn die Klauseln alle erfüllbar sind, dann können wir an der entsprechenden 01:14:30.576 --> 01:14:39.249 Wahrheitsbelegung genau ablesen, welche Berechnung die Thuringmaschine macht, und das ist dann eine nach Konstruktion 01:14:39.249 --> 01:14:51.969 der Klausel, die in In Einen akzeptierenden endzustand führt also die in Das heißt, also unser f l ist so, 01:14:51.969 --> 01:15:04.690 dass tatsächlich x in l genau dann, wenn f l von x entsprechende Sattinstanz, so, und jetzt müssen wir noch gucken, ob 01:15:04.690 --> 01:15:15.097 diese ganze Aktion Polynomial ist also nur Polynomiellen aufwand in der Eingabegröße, also der Länge der Eingabe, also 01:15:15.097 --> 01:15:25.070 diesem n, dafür müssen wir uns die ganzen Variablen angucken. Wie viele sind das denn und wieviel Klauseln sind das und 01:15:25.070 --> 01:15:32.671 so weiter, das ist ziemlich langweilig. Gehen wir einfach mal kurz durch, ähm, zu jedem Zeitpunkt I sm in mindestens 01:15:32.671 --> 01:15:42.846 einem Zustand. Wir haben also die all diese Klauseln für alle i zwischen , Null, Und, P von n und wir haben alle 01:15:42.846 --> 01:15:53.147 diese Klauseln Für Alle i zwischen Null und P von N und J Strich zwischen null und r und das ganze 01:15:53.147 --> 01:16:04.345 abschätzen, das sind also so viele Klauseln oder p von n plus eins mal r plus eins, oder so viele literale p von n plus 01:16:04.345 --> 01:16:16.886 eins mal r plus eins plus p von n plus eins mal ein halb mal r mal r plus eins, ja, das ist Polynomial in n , Und, 01:16:16.886 --> 01:16:24.501 Dasselbe für diese ganzen Klauseln für die Position des Leseschreibkops Müssen sie Uns einfach angucken in welchen 01:16:24.501 --> 01:16:32.789 Indexbereichen Bewegen Sich die ij die wir hier betrachten, das ist hier ganz genauso. Die Eas stehen für 01:16:32.789 --> 01:16:40.637 Zeitpunkt und eine Penn, nur p von n verschiedene Zeitpunkte, , Und, Die j strich Bewegen Sich ja zwischen 01:16:40.637 --> 01:16:48.484 den möglichen Positionen, und deshalb war es jetzt wichtig, dass wir am Anfang gesagt haben, innerhalb von P von Endzeit 01:16:48.484 --> 01:16:57.117 kann Höchstens Position Minus P von n bis Position plus p von n plus eins beschrieben werden, das heißt also, das Ganze 01:16:57.117 --> 01:17:05.707 bewegt sich innerhalb von irgendwas, was abhängig ist von dem P von N, das kann man so hinschreiben. Ja, also auch 01:17:05.707 --> 01:17:15.820 wieder Polynomial in N, das dritte für die Bandinhalte, da sind sozusagen die Ijk, die hier eine Rolle spielen wieder 01:17:15.820 --> 01:17:26.439 die Zeitpunkte I innerhalb von P von N Die Position j Ist innerhalb von p von N sozusagen anzahlmäßig 01:17:26.439 --> 01:17:36.047 Größenordnungsmäßig und, die kk strich das sind höchstens So viele wie wir Symbole haben Das Heißt, also als 01:17:36.047 --> 01:17:47.677 Abschätzung hier kriegt man diese Formel, die auch wieder abhängig ist von P von N und damit von N gäbe für die vierte 01:17:47.677 --> 01:17:57.285 Klauselgruppe Ich Gehe da jetzt gar nicht im Detail ein, das, was hier einfach nur essentiell ist die 01:17:57.285 --> 01:18:03.353 Voraussetzung, dass unsere nichtdeterministische Touringmaschine nur Polynomialen Aufwand hat also, dass deren 01:18:03.353 --> 01:18:11.444 Zeitkomplexitätsfunktion beschränkt ist durch dieses Polynom P von N, das entscheidet hier alles, das entscheidet hier, 01:18:11.444 --> 01:18:21.052 dass auch das, was wir da nachher als Stadtinstanz kriegen zwar ziemlich bombastisch, ist viele, viele Klauseln, aber in 01:18:21.052 --> 01:18:31.671 der Größe nur abhängig von P von N und natürlich von der Anzahl der Symbolen, der Anzahl, , , Der, Zustände, 01:18:31.671 --> 01:18:35.200 Aber das sind sozusagen Konstanten. 01:18:46.310 --> 01:18:59.704 Und dann kriegt man also diese riesen Formeln für jede der Klauselngruppen, also wie viele Literale sind jeweils in der 01:18:59.704 --> 01:19:13.959 Klauselgruppe G eins G zwei G drei G vier, die fünf ist tatsächlich Bescheiden, da ist nur eine drin und geh sechs und 01:19:13.959 --> 01:19:28.213 man sieht das in alles , , Terme, Die, Irgendwie, In, irgendwie Polynomiell in p von n sind und P von N ist 01:19:28.213 --> 01:19:39.368 wieder Polynomie in n, also insgesamt Polynomial, so alle weiteren , Faktoren, die Hier, vorkommen stehen für die 01:19:39.368 --> 01:19:50.524 Anzahl der Zustände und Anzahl der , Symbole, Aber, Das, sind Konstanten okay und damit haben wir unsere 01:19:50.524 --> 01:20:01.060 Konstruktion, also die angegebene Funktion Fl ist eine polynomiale Transformation von der vorgegebenen Sprache L aus n? 01:20:01.060 --> 01:20:16.063 P nach der Sprache zusat im sinne Dass, jedes Wort aus l auf eine erfüllbare Instanz von Satt abgebildet wird und jede 01:20:16.063 --> 01:20:29.703 Eingabe, die nicht wort aus ls auch auf eine nicht entfüllbarer Instanz von Satt abgebildet wird Ja was 01:20:29.703 --> 01:20:44.414 Haben wir also wir haben die Klassen P wir haben die Klasse N? P wir haben die Vermutung, dass n p ungleich p ist, wir 01:20:44.414 --> 01:20:54.623 versuchen jetzt sozusagen dem näher zu kommen, was das bedeutet, wenn tatsächlich n, p ungleich p ist, dann gibt es in 01:20:54.623 --> 01:21:05.319 Np irgendwelche Probleme, die nicht in P sind, bisher ist es niemand Gelungen zu beweisen, dass p ungleich n p ist, aber 01:21:05.319 --> 01:21:15.043 wir können zumindest versuchen zu identifizieren, welche Probleme in n p sind die Kandidaten dafür dann nicht zu p zu 01:21:15.043 --> 01:21:24.766 gehören, wenn p ungleich n p ist, dafür haben wir definiert, was die schwersten Probleme in Np sind nämlich diejenigen, 01:21:24.766 --> 01:21:33.517 mit denen wir, wenn wir dafür einen polynomialen Rhythmus hätten auch alle anderen Probleme aus Np in Polynomialzeit 01:21:33.517 --> 01:21:44.184 lösen könnten. Wenn ich jetzt von polynomialen Algorithmus spreche oder in Polynomialzeit lösen, dann meine ich damit 01:21:44.184 --> 01:21:49.349 durch einen richtigen deterministischen Algorithmus Wir haben. 01:21:50.100 --> 01:21:59.071 Uns dann überlegt dass es aber eigentlich reicht, um für ein konkretes Problem aus Np zu zeigen, dass es zu den 01:21:59.071 --> 01:22:08.042 schwersten in Np gehört Was Wir, einfach zeigen ein anderes, von dem wir schon wissen, dass es zu den schwersten 01:22:08.042 --> 01:22:17.013 in Denp gehört, lässt sich Polynomial auf das transformieren und wir haben mit dem Satz von Cook auch ein erstes solches 01:22:17.013 --> 01:22:24.702 Np vollständiges Problem identifiziert nämlich satt und was wir dann im nächsten schritt machen werden, ist, dass wir 01:22:24.702 --> 01:22:33.246 für konkrete Probleme zeigen, die sind Np vollständig erstmal, weil das dann interessant ist zu sehen, Aha, so was wie 01:22:33.246 --> 01:22:41.790 eine Clique größter Größe in einem Graph zu finden oder einen Graf mit einer minimalen anzahl Von haben sinnvoll zu 01:22:41.790 --> 01:22:50.761 Färben oder oder oder das sind tatsächlich ganz schwere Probleme, oder das sind welche, die zu den schwersten in den P 01:22:50.761 --> 01:23:00.159 gehören und um auch zu üben, wie beweist man denn sowas denn Wenn Man, an tatsächliche Probleme in, sagen wir mal, 01:23:00.159 --> 01:23:09.558 in der Anwendung denkt, dann kommt das ziemlich oft vor, dass man sieht, oh, das Problem, das scheint aber quer zu sein 01:23:09.558 --> 01:23:17.691 in dem Sinne, dass es vermutlich keinen polynomialen Algorithmus gibt. Und also oft ist das sozusagen das erste, was man 01:23:17.691 --> 01:23:25.393 sich überlegen muss, ja, ist das jetzt in P und ich bin nur nicht schlau genug, einen polynomialen Algorithmus zu 01:23:25.393 --> 01:23:31.555 finden, oder kann ich tatsächlich beweisen, dass das sehr unwahrscheinlich ist, das dafür einen polynomialen Algorithmus 01:23:31.555 --> 01:23:39.643 gibt, dem ich zeige das Problem ist Np vollständig Das Was wir, hier immer dann zugrunde legen, eigentlich oder im 01:23:39.643 --> 01:23:44.649 Hinterkopf haben, ist eben diese Vermutung, ja N p ist tatsächlich ungleich p. 01:23:44.810 --> 01:23:53.544 Ich habe eben gesagt, bisher hat das noch niemand beweisen können , Da, Gibt, es eine ganze Menge Leute, die das 01:23:53.544 --> 01:24:02.405 versuchen. Ja, , Und, Was interessanterweise halt viel öfter vorkommt ist, dass jemand sagt " Oh, ich habe 01:24:02.405 --> 01:24:12.326 bewiesen, dass p gleich n p ist, obwohl ja irgendwie die Mehrheit der Informatiker glaubt, dass P. Ungleich n. P ist, 01:24:12.326 --> 01:24:22.405 braucht man sich ja, aber warum werden mehr Beweise geführt? p gleich n? p als Beweise p ungleich n p Was Hat 01:24:22.405 --> 01:24:34.010 damit zu tun dass man, um zu beweisen, dass p gleich n p ist einen polynomialen Algorithmus angeben muss, um ein Np 01:24:34.010 --> 01:24:42.645 vollständiges Problem zu lösen. Und so gibt es also dann jede Menge, ich sage mal Artikel Die, geschrieben werden weil, 01:24:42.645 --> 01:24:49.161 jemand sagt hier, ich habe einen polynomialen Algorithmus für Treveling Selesmond gefunden oder für irgendein anderes, 01:24:49.161 --> 01:24:56.899 irgendwie vollständiges Problem zeigt sich dann Bisher War es immer so dass ich dann nachher, aber doch gezeigt 01:24:56.899 --> 01:25:05.230 hat, nein, der Algorithmus ist gar nicht Polynomial, oder der löst nicht das, okay, das wärst du heute.