Gut, ja wir fangen schon mal an. Gelbe Kreide haben wir ja dank der

freundlichen Dame da hinten. Mehr kommt gleich.

Ja, also wir hatten uns letztes Mal angesehen die grundlegenden Komplexitätsklassen und

uns am Ende überlegt ein paar offensichtliche Inklusionen und Gleichheiten zwischen diesen

Klassen. Wir enden mit ungefähr folgendem Bild. Also wir haben hier

als kleinste Klasse, die wir in Betracht ziehen und als übrigens auch beweisbar kleinste Klasse,

die es gibt, das ist uns aber zu schwierig, die Klasse der in logarithmischen Platz lösbaren

Probleme. Gut, die ist offensichtlich enthalten in der Klasse der in nicht-deterministisch

logarithmischen Platz lösbaren Probleme und sie ist ebenso offensichtlich enthalten

in der zugehörigen Komplementklasse. Weiterhin hatten wir uns überlegt, dass höchstens exponentiell

mehr Zeit verbraucht wird als Platz. Das war dieses Argument mit dem Zuständezählen.

Diese Zustände dürfen sich nicht wiederholen. Das heißt, hier haben wir eine Inklusion

in die Klasse P, der in deterministisch-polynomen-jahlerzeit lösbaren Probleme. Die wiederum, na, Quatsch.

Das kommt erst im nächsten. Diese Klasse ist gleich ihrer Co-Klasse natürlich wie alle

deterministischen Klassen. Sie ist offensichtlich enthalten in der entsprechenden nicht-deterministischen

Klasse, der auf nicht-deterministischen Maschinen in polynomialer Zeit lösbaren Problemen

und der zugehörigen Komplementklasse. Und wir haben hier über das gleiche Argument

wiederum Inklusion. Also auch auf einer nicht-deterministischen Maschine habe ich durch die Schranke auf den

Platz eine entsprechende exponentielle Schranke auf den Zeitverbrauch. Dann haben wir noch

eine offensichtliche Inklusion. Ich kann immer nur pro Schritt eine Zelle vollschreiben.

Das heißt, ich verbrauche immer höchstens so viel Platz wie Zeit. Das heißt, wenn ich

polynomial viel Zeit verbrauche, brauche ich erst recht nur polynomial viel Platz. Wiederum

offensichtliche Inklusion in die entsprechenden nicht-deterministischen Klassen und die gleichen

Inklusionen unter den nicht-deterministischen Klassen. Und wiederum nach demselben Argument

wie hier. Wir verbrauchen höchstens exponentiell mehr Zeit als Platz. Das heißt, P space ist

enthalten in x time. Natürlich geht das noch beliebig weiter und das spielt auch durchaus

eine Rolle. Also es besteht durchaus Interesse an beispielsweise doppelt exponentiell vollständigen

Problemen oder sowas. Aber wir hören jetzt mal für Zwecke dieser Veranstaltung bei x

time auf. Gut, das ist jetzt der Teil der Hierarchie, der offensichtlich ist. Und wir

werden zeigen, dass hier etliches kollabiert. Insbesondere werden wir zeigen, dass hier ein

vollständiger Kollaps nach P space eintritt. Das heißt, hier können wir einen eckigen

Kasten drum machen. Das ist eigentlich alles dasselbe. Und wir werden zeigen, dass diese

beiden Klassen zusammenfallen. Das Schlagwort ist nicht-deterministischer Platz ist Komplement

abgeschlossen. Also hinsichtlich Platz unterscheiden sich die nicht-deterministischen Klassen nicht

von den entsprechenden Co-Klassen. Und ab P space kollabiert das sogar ganz, dass das

nicht-deterministische mit dem deterministischen zusammenfällt. Wohlgemerkt aber eben nur im

Platz fallen. Das heißt, wir haben schon eine ziemliche Diskrepanz. Also hier haben wir

eben das berühmteste Problem der Kirchengeschichte. Also ist diese Inklusion echt oder nicht?

Während also hier die Frage schlicht und einfach seit langem beantwortet ist, sie ist

nicht echt. Ja, vielen Dank. Super. Ja, dann haben wir jetzt, ja. Gut. Ja, wir fangen an

jetzt diese Klassen in Detail zu analysieren. Das wird hauptsächlich dann nächste Woche

Hergurinen erledigen. Ich bin selber nächste Woche nicht da. Auf der Lix in New Orleans

bin ich. Wir treffen jetzt so ein paar Vorbereitungen, indem wir insbesondere dieses vielleicht nicht

ganz so gewohnte Konzept des logarithmischen Platzes noch einmal genauer ansehen. So, ein

Teil davon ist also dieses hier. Frisch abgeliefert, schon kaputt. Da kommen wir auch nur knapp

mit hin. Also die Klasse Logspace, die ich gelegentlich nur Logs schreiben werde, weil

sie in Indizes auftauchen wird und man möchte nicht gerne Indizes haben, die länger als

vier Zeichen sind. Logspace ist jetzt keine Klasse von Problemen, sondern von Funktionen.

Logspace ist die Klasse der in logarithmischen Platz berechenbaren Funktionen. Und intuitiv

kann man das folgendermaßen charakterisieren. Ich habe das letztes Mal schon, als wir das